Binary Number with Alternating Bits
Problem
Given a positive integer n, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
n = 5truedef has_alternating_bits(n):
x = n ^ (n >> 1)
return (x & (x + 1)) == 0function hasAlternatingBits(n) {
const x = n ^ (n >> 1);
return (x & (x + 1)) === 0;
}class Solution {
public boolean hasAlternatingBits(int n) {
int x = n ^ (n >> 1);
return (x & (x + 1)) == 0;
}
}bool hasAlternatingBits(int n) {
long x = n ^ (n >> 1);
return (x & (x + 1)) == 0;
}Explanation
We want to know if n's bits strictly alternate, like 101010. Instead of looping through bits, this solution uses a slick two-line bit trick that checks it in constant time.
The first step is x = n ^ (n >> 1). Shifting n right by one lines up each bit with its neighbour, and XOR produces a 1 wherever two adjacent bits differ. So if the bits truly alternate, every adjacent pair differs and x comes out as all 1s (something like 111...1).
The second step checks whether x is all 1s. A number that is all 1s is always one less than a power of two, and for such numbers x & (x + 1) equals 0 (adding 1 rolls it over to a single high bit that shares no bits with x). If any adjacent bits had matched, x would contain a 0 in the middle and this test would fail.
Example: n = 5 is 101. Then n >> 1 is 010, and 101 ^ 010 = 111 (all 1s). Since 111 & 1000 = 0, the answer is true — the bits alternate.