How to Check Binary Number with Alternating Bits?

Given an integer, check if its binary representation are containing the alternating bits. For example, 101, 10101, 1010 are binary numbers with alternative bits. But 1011, 1110 are not.

The straightforward C++ solution will be recording the previous bit and compare to current bit. Each iteration will shift the number one position to the right using >> operator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;
        while (n > 0) {
            int bit = n & 1;
            if (prev == bit) return false;
            n >>= 1;
            prev = bit;
        }
        return true;
    }
};

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;
        while (n > 0) {
            int bit = n & 1;
            if (prev == bit) return false;
            n >>= 1;
            prev = bit;
        }
        return true;
    }
};

Despite the while loop, the above actually is O(1) complexity because a integer is 32-bit or 64-bit and there is at most 32 or 64 loops regardless the input.

Bit Manipulation Alterativing Bits

The integer shifting one position to the right should become interleaving with the origin number. If we add these two numbers and it should become 1111.. all ones. Next, by adding one to it becomes 0 – and if we logic and these two numbers again, we will get zero.

1
2
3
4
5
6
7

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int m = n >> 1;
        return ((m + n) & (m + n + 1)) == 0;
    }
};

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int m = n >> 1;
        return ((m + n) & (m + n + 1)) == 0;
    }
};

This is O(1) and should be a little bit efficient than the first approach.

–EOF (The Ultimate Computing & Technology Blog) —