Problem

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

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
3

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

Constraints

  • 1 <= n <= 2^31 - 1

Solution

Method 1 – Bit Manipulation (XOR and Check)

Intuition

If a number has alternating bits, then XORing it with itself right-shifted by 1 will result in a sequence of 1s (i.e., all bits set to 1). For example, 101 (5) XOR 010 (2) = 111 (7). If the result is a sequence of 1s, then adding 1 to it will make it a power of two, so result & (result + 1) == 0.

Approach

  1. Compute x = n ^ (n >> 1).
  2. Check if x & (x + 1) == 0.
  3. Return true if so, else false.

Code

1
2
3
4
5
6
7

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

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

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

class Solution {
    fun hasAlternatingBits(n: Int): Boolean {
        val x = n xor (n shr 1)
        return (x and (x + 1)) == 0
    }
}
1
2
3
4

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

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

Complexity

  • ⏰ Time complexity: O(1) — Only a few bitwise operations.
  • 🧺 Space complexity: O(1) — No extra space used.