Binary Number with Alternating Bits

Problem Description

Given a positive integer n, determine whether its binary representation has alternating bits. In other words, check if every pair of adjacent bits is different.

Key Insights

• A number with alternating bits in binary will have no two consecutive bits that are the same.
• One efficient approach is to use bit manipulation:
  • Compute x = n XOR (n >> 1). For a number with alternating bits, x will be a sequence of 1's.
  • A sequence of consecutive 1's has the property that x & (x + 1) equals 0.
• This method avoids converting the integer to a string, keeping the solution efficient.

Space and Time Complexity

Time Complexity: O(1) - the number of operations is constant since the number of bits (at most 31) is fixed.
Space Complexity: O(1) - only a few extra variables are used.

Solution

We solve the problem by using bit manipulation. The steps are as follows:

1. Perform an XOR between n and n shifted right by 1 bit (n ^ (n >> 1)). This operation highlights transitions between bits.
2. Check if the resulting number is a sequence of all 1's. A number that is all 1's will satisfy the condition (x & (x + 1) == 0).
3. If the condition holds, the binary representation of n has alternating bits; otherwise, it does not.

This approach leverages understanding of bit properties and uses basic bitwise operators to achieve the solution in constant time and space.

Code Solutions