Skip to content

693. Binary Number with Alternating Bits

Description

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

 

Example 1:

Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101

Example 2:

Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.

Example 3:

Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.

 

Constraints:

  • 1 <= n <= 231 - 1

Solutions

Solution 1: Simulation

Thinking

Check that neighboring bits strictly alternate. A bit-by-bit scan is enough.

Read the lowest bit, shift, and fail if it equals the previous bit.

We cyclically right-shift \(n\) until it becomes \(0\), checking whether the binary bits of \(n\) appear alternately. If during the loop we find that \(0\) and \(1\) do not appear alternately, we directly return \(\textit{false}\). Otherwise, when the loop ends, we return \(\textit{true}\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = -1
        while n:
            curr = n & 1
            if prev == curr:
                return False
            prev = curr
            n >>= 1
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public boolean hasAlternatingBits(int n) {
        int prev = -1;
        while (n != 0) {
            int curr = n & 1;
            if (prev == curr) {
                return false;
            }
            prev = curr;
            n >>= 1;
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = -1;
        while (n) {
            int curr = n & 1;
            if (prev == curr) return false;
            prev = curr;
            n >>= 1;
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func hasAlternatingBits(n int) bool {
    prev := -1
    for n != 0 {
        curr := n & 1
        if prev == curr {
            return false
        }
        prev = curr
        n >>= 1
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function hasAlternatingBits(n: number): boolean {
    let prev = -1;

    while (n !== 0) {
        const curr = n & 1;
        if (prev === curr) {
            return false;
        }
        prev = curr;
        n >>= 1;
    }

    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn has_alternating_bits(mut n: i32) -> bool {
        let mut prev: i32 = -1;

        while n != 0 {
            let curr = n & 1;
            if prev == curr {
                return false;
            }
            prev = curr;
            n >>= 1;
        }

        true
    }
}

Solution 2: Bit Manipulation

Thinking

The scan is \(O(\log n)\). \(n\oplus(n\gg 1)\) becomes a run of ones iff bits alternate; then \(n\&(n+1)=0\) confirms it in constant time.

Assuming \(\text{01}\) appears alternately, we can convert all trailing bits to \(\text{1}\) through misaligned XOR. Adding \(\text{1}\) gives us a power of \(2\), which is a number \(n\) (where \(n\) has only one bit that is \(\text{1}\)). Then, using \(\text{n} \& (\text{n} + 1)\) can eliminate the last \(\text{1}\) bit.

At this point, check if it equals \(\text{0}\). If so, the assumption holds, and it is an alternating \(\text{01}\) sequence.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
4
class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        n ^= n >> 1
        return (n & (n + 1)) == 0

1
2
3
4
5
6
class Solution {
    public boolean hasAlternatingBits(int n) {
        n ^= (n >> 1);
        return (n & (n + 1)) == 0;
    }
}

1
2
3
4
5
6
7
class Solution {
public:
    bool hasAlternatingBits(int n) {
        n ^= (n >> 1);
        return (n & ((long) n + 1)) == 0;
    }
};

1
2
3
4
func hasAlternatingBits(n int) bool {
    n ^= (n >> 1)
    return (n & (n + 1)) == 0
}

1
2
3
4
function hasAlternatingBits(n: number): boolean {
    n ^= n >> 1;
    return (n & (n + 1)) === 0;
}

1
2
3
4
5
6
impl Solution {
    pub fn has_alternating_bits(n: i32) -> bool {
        let mut x = n ^ (n >> 1);
        (x & (x + 1)) == 0
    }
}

Comments