One bit on
Test for a power of two in one step with n & (n − 1). About 7 minutes.
Powers of two have a single 1
In binary, 1, 2, 4 and 8 are written 1, 10, 100 and 1000. Each power of two is one switch on and all the others off, like a single lit window in a dark building.
So "is it a power of two?" becomes "does it have exactly one 1 bit?". Counting bits would work, but there is a one-line trick.
16 is 10000: a single 1. Every power of two looks like this.
One less flips the tail
Subtract 1 from 1000 and you get 0111: the lowest 1 turns off and every 0 below it turns on, like an odometer rolling over.
Now AND the number with that result. Only bits that are on in both survive, and the lowest 1 is gone. If nothing is left, there was only one 1 to start with.
return n > 0 and n & (n - 1) == 0
What is 12 & 11 (1100 & 1011)?
- A8
- B0
- C15
Show the answer
8. 1100 & 1011 = 1000: the lowest 1 of 12 was cleared.
Power of two?
Return true if n is a power of two (1, 2, 4, 8, …).
n = 16 → true
−2^31 ≤ n ≤ 2^31 − 1