Binary Number with Alternating Bits: The XOR Trick

LeetCode Binary Number with Alternating Bits (Problem 693) asks: given a positive integer n, check whether it has alternating bits. In other words, no two adjacent bits in its binary representation should be the same.

For example, 5 in binary is 101. Every neighboring pair of bits differs, so the answer is true. But 7 in binary is 111, where consecutive bits repeat, so the answer is false.

The problem is simple to solve with a loop, but there is a constant-time bit trick that makes it elegant. Let's look at both and understand why the XOR approach works.

The problem

Given a positive integer n, return true if n has alternating bits, meaning no two adjacent bits are the same.

• n = 5 (binary 101) returns true
• n = 7 (binary 111) returns false
• n = 10 (binary 1010) returns true
• n = 11 (binary 1011) returns false

The approach

Here is the key observation: if the bits truly alternate, then shifting n right by one position produces a number where every bit is the opposite of the corresponding bit in n. When you XOR n with n >> 1, every bit position will produce a 1, because every pair of adjacent bits differs.

So for an alternating number, n ^ (n >> 1) gives you a number that is all 1s in binary, like 111 or 1111.

How do you check if a number is all 1s? A number with all bits set has the form 2^k - 1. Adding 1 to it produces a power of two. So you can check: is (result + 1) a power of two? And the classic power-of-two test is x & (x - 1) == 0. Equivalently, you can check result & (result + 1) == 0.

Putting it together: compute m = n ^ (n >> 1), then return m & (m + 1) == 0.

The code

def hasAlternatingBits(n: int) -> bool:
    m = n ^ (n >> 1)
    return m & (m + 1) == 0

1. Compute m = n ^ (n >> 1): XOR n with its right-shifted version. If bits alternate, every adjacent pair differs, so every XOR output bit is 1. The result m will be all 1s.
2. Check m & (m + 1) == 0: If m is all 1s (like 0111), then m + 1 is a power of two (like 1000). ANDing them gives 0. If m is not all 1s, this AND produces a nonzero value.
3. Return the boolean: True means alternating bits, false means at least one pair of adjacent identical bits exists.

You can also solve this with a simple loop that checks each adjacent pair:

def hasAlternatingBits(n: int) -> bool:
    prev = n & 1
    n >>= 1
    while n:
        curr = n & 1
        if curr == prev:
            return False
        prev = curr
        n >>= 1
    return True

The loop version is easier to read but less elegant. Both work, and interviewers will appreciate either one. The XOR version shows deeper bit manipulation fluency.

Complexity analysis

The XOR approach runs in constant time with constant space. No loops, no extra data structures. The loop approach is also technically O(1) for fixed-width integers (at most 32 iterations), but the XOR version is faster in practice.

Building blocks

XOR cancellation

XOR outputs 1 when two bits differ and 0 when they match. By XORing n with n >> 1, you are comparing every bit to its neighbor. This is the same principle behind XOR cancellation, where XOR detects and highlights differences between values.

The pattern appears frequently: Hamming distance uses XOR to find differing bits between two numbers, Single Number uses XOR to cancel duplicates, and this problem uses XOR to compare a number against a shifted copy of itself. Learning to reach for XOR whenever you need "where do these differ?" is one of the highest-leverage bit manipulation skills.

All-ones check

Testing whether a binary number is all 1s (2^k - 1) uses the same logic as the power-of-two test, shifted by one. If m is all 1s, then m + 1 is a power of two, and m & (m + 1) == 0. This tiny check lets you avoid looping through every bit to verify they are all set.

Edge cases

n = 1: Binary 1. A single bit trivially alternates (there are no adjacent pairs to violate). 1 ^ 0 = 1, and 1 & 2 = 0. Returns true.

n = 2: Binary 10. Two bits, and they differ. Returns true.

n = 3: Binary 11. Two adjacent 1s. 3 ^ 1 = 2 (binary 10), which is not all 1s. 2 & 3 = 2, not 0. Returns false.

n = 4: Binary 100. The trailing 00 has two adjacent 0s. 4 ^ 2 = 6 (binary 110), and 6 & 7 = 6, not 0. Returns false.

Large alternating number: Something like n = 1431655765 (binary 01010101...01 for 32 bits). The XOR trick handles this in three operations regardless of bit width.

Powers of two: Any power of two greater than 2 (like 4, 8, 16) has trailing zeros, which means consecutive identical bits. Returns false. Only n = 1 and n = 2 among powers of two return true.

From understanding to recall

The mental model here is two checks stacked together: "XOR with shifted self to get all 1s if alternating, then verify all 1s with the AND trick." That is the whole algorithm in one sentence.

If you can recall that sentence without thinking, the three-line implementation writes itself. Practice it a few times from a blank editor over the next week. By the third attempt, you should be writing the solution in under 30 seconds.

Spaced repetition locks in the connection between "alternating bits" and "XOR with shifted self." The first time you see this trick, it feels clever. The fifth time you recall it unprompted, it feels obvious. That is the goal.

Related posts

• Number of 1 Bits - Counting set bits with the n & (n-1) trick. The same bit-level thinking applies: isolate properties of binary representations using bitwise operations.
• Power of Two - Uses n & (n-1) == 0 to check for a single set bit. Alternating Bits reuses this idea to check for all set bits in the XOR result.
• Hamming Distance - XOR marks differing bit positions between two numbers. Alternating Bits applies the same XOR comparison, but between a number and its own shifted copy.