Binary Number with Alternating Bits

Binary Number with Alternating Bits

What is this problem about?

The "Binary Number with Alternating Bits interview question" asks you to verify a specific property of an integer's binary representation. A number has alternating bits if no two adjacent bits are the same. For example, 5 (101) and 10 (1010) have alternating bits, while 7 (111) and 11 (1011) do not.

Why is this asked in interviews?

Yahoo and Amazon use the "Binary Number with Alternating Bits coding problem" to see if a candidate can find clever shortcuts using bitwise arithmetic. While you can solve this by checking bits one by one, there is a very elegant solution using XOR and bitwise properties that demonstrates a deeper understanding of "Bit Manipulation interview pattern."

Algorithmic pattern used

There are two main ways to solve this:

1. Iterative Check: Repeatedly take n % 2 to get the last bit and compare it with the previous bit using n / 2.
2. The "XOR Trick" (Clever):
   • If you shift n by 1 (n >> 1) and XOR it with the original n (n ^ (n >> 1)), the result will be a string of all 1s if the bits were alternating.
   • To check if a number $x$ is all 1s, check if (x & (x + 1)) == 0.

Example explanation

$n = 5$ (Binary: 101)

1. $n \gg 1$ is 010 (2).
2. $5 ext{ XOR } 2$ is 111 (7).
3. $x = 7$. Check $x \& (x + 1)$: $7 ext{ AND } 8 = `0111 ext{ AND } 1000` = 0$.
4. Since the result is 0, the bits are alternating.

Common mistakes candidates make

• Looping too much: Not recognizing that bit manipulation can solve the problem in $O(1)$ time relative to the number of bits.
• Incorrect Bit Comparison: Getting the "previous bit" logic wrong in an iterative loop.
• Handling Zero: Forgetting to check if the input number is valid according to the problem constraints.

Interview preparation tip

Whenever you see a pattern in binary bits (like "all 1s" or "power of 2"), look for a bitwise formula. These are common "Bit Manipulation interview pattern" tricks that can save time and impress your interviewer.