# Binary Number with Alternating Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-number-with-alternating-bits)
Canonical: https://scaleengineer.com/dsa/problems/binary-number-with-alternating-bits
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
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`

# Approaches
## Convert to String and Iterate
This approach converts the integer into its binary string representation. Then, it iterates through the string to check if any two adjacent characters (bits) are the same. If it finds such a pair, the number does not have alternating bits. If the entire string is traversed without finding such a pair, the bits are alternating.
**Time:** O(log n). The number of bits in `n` is proportional to log₂(n). Converting the number to a string and iterating through it both take time proportional to the number of bits. · **Space:** O(log n). We need to store the binary string representation of `n`, which requires space proportional to the number of bits.
**Pros:** Simple to understand and implement.; Leverages built-in language features for number-to-string conversion.
**Cons:** Less efficient in terms of both time and space compared to bit manipulation approaches.; Incurs overhead from string object creation and character access.
### Explanation
This is the most straightforward approach. We first convert the number into a sequence of characters representing its bits and then perform a simple linear scan to check for the alternating property.

```java
class Solution {
    public boolean hasAlternatingBits(int n) {
        String binaryString = Integer.toBinaryString(n);
        for (int i = 1; i < binaryString.length(); i++) {
            if (binaryString.charAt(i) == binaryString.charAt(i - 1)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Convert the input integer `n` to its binary string representation using `Integer.toBinaryString(n)`.
- Loop through the binary string from the second character (index 1) to the end.
- In each iteration, compare the current character `s.charAt(i)` with the previous character `s.charAt(i-1)`.
- If `s.charAt(i) == s.charAt(i-1)`, it means two adjacent bits are the same. Return `false` immediately.
- If the loop completes without returning, it means all adjacent bits were different. Return `true`.

## Iterative Bit Manipulation
This method avoids the overhead of string conversion by directly examining the bits of the integer. It iteratively checks the last bit, then right-shifts the number to examine the next bit, comparing each new bit with the previous one.
**Time:** O(log n). The loop runs once for each bit in the number `n`. The number of bits is approximately log₂(n). · **Space:** O(1). This approach uses only a few variables to store the current and last bits, resulting in constant extra space.
**Pros:** More efficient than the string conversion method, especially in terms of space.; Works directly with the integer representation, avoiding string overhead.
**Cons:** Still requires a loop, making it less efficient than a purely bitwise constant-time solution.
### Explanation
By working directly with the integer's binary representation, we can achieve better performance, especially in terms of space. We use bitwise operators (`&` and `>>`) to inspect each bit one by one from right to left.

```java
class Solution {
    public boolean hasAlternatingBits(int n) {
        int lastBit = n & 1;
        n >>= 1;
        while (n > 0) {
            int currentBit = n & 1;
            if (currentBit == lastBit) {
                return false;
            }
            lastBit = currentBit;
            n >>= 1;
        }
        return true;
    }
}
```
### Algorithm
- Extract the least significant bit (LSB) of `n` using a bitwise AND operation (`n & 1`). Store this as `lastBit`.
- Right-shift `n` by one position (`n >>= 1`) to discard the LSB.
- Enter a loop that continues as long as `n` is greater than 0.
- Inside the loop, extract the new LSB (`currentBit = n & 1`).
- Compare `currentBit` with `lastBit`. If they are equal, return `false`.
- Update `lastBit` to `currentBit` for the next iteration.
- Right-shift `n` by one again (`n >>= 1`).
- If the loop finishes, it means all adjacent bits were alternating, so return `true`.

## Bitwise XOR Trick
This is a highly efficient, constant-time solution that uses a clever bitwise trick. If a number `n` has alternating bits (e.g., `1010`), then `n` XORed with `n` right-shifted by one (`n >> 1`) results in a number with all ones (e.g., `1010 ^ 0101 = 1111`). A number made of all ones (like `1, 3, 7, 15, ...`) has the property that when you add 1 to it, you get a power of two. We can check if a number `y` is a power of two by testing if `(y & (y-1)) == 0`.
**Time:** O(1). This approach consists of a fixed number of bitwise operations, regardless of the size of the input integer `n`. · **Space:** O(1). No extra space is used besides a single variable to store the intermediate result.
**Pros:** Extremely efficient, providing a constant-time solution.; Demonstrates a deep understanding of bitwise operations.
**Cons:** The logic is less intuitive and harder to come up with compared to the iterative approaches.
### Explanation
This approach leverages properties of bitwise operations to solve the problem in constant time. The key insight is that for a number with alternating bits like `n = 101010`, the expression `n ^ (n >> 1)` will result in a number with all bits set to 1, like `111111`. A number with all bits set to 1 is always one less than a power of two. We can check if a number `k` is a power of two by the property `(k & (k - 1)) == 0`. Combining these facts gives us a concise and fast solution.

```java
class Solution {
    public boolean hasAlternatingBits(int n) {
        // n =         101010
        // n >> 1 =    010101
        // n ^(n>>1) = 111111 (let this be x)
        // x is of the form 2^k - 1. So x+1 is a power of 2.
        // A number is a power of 2 if (num & (num - 1)) == 0.
        // So, we check if ((x+1) & x) == 0.
        long x = n ^ (n >> 1);
        // Use long for x to handle the edge case where n has 31 bits
        // and x becomes 2^31 - 1. x+1 would overflow an int.
        return (x & (x + 1)) == 0;
    }
}
```
### Algorithm
- Create a new number `x` by performing a bitwise XOR between `n` and `n` right-shifted by one: `x = n ^ (n >> 1)`.
- If `n` has alternating bits, `x` will be a number where all bits up to the most significant bit of `n` are set to 1 (e.g., `...001111`).
- A number of the form `...001111` is one less than a power of two. For example, `7` (`0111`) is one less than `8` (`1000`).
- Therefore, `x + 1` should be a power of two.
- A positive number `y` is a power of two if and only if `(y & (y - 1)) == 0`.
- So, we check if `((x + 1) & x) == 0`. If this condition is true, the bits are alternating; otherwise, they are not.

# Solutions
### Java

```java
class Solution {
public
  boolean hasAlternatingBits(int n) {
    n ^= (n >> 1);
    return (n & (n + 1)) == 0;
  }
}

```

### CPP

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

```

### Python

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

```