Computer Science
Is it a power of two?
How can a computer check whether a positive whole number is a power of two in a single step, without a loop?
- Hint 1Write 8, 16 and 20 in binary.
- Hint 2What happens to the binary digits when you subtract 1 from a power of two?
- A power of two in binary is a single 1 followed by zeros, such as 1000.
- Subtracting 1 turns it into all ones below that place: 1000 − 1 = 0111.
- So n AND (n − 1) is 0 exactly when n has a single 1 bit.
- Any other positive number keeps its highest 1 bit after the AND, so the result is not 0.
- Test: n > 0 and (n AND (n − 1)) = 0.
Where it lands: n > 0 and n AND (n − 1) equals 0.
The trap: Forgetting n = 0, which passes the AND test but is not a power of two.
What a tutor might ask next: How would you count the 1 bits in a number using the same trick?
Now do one out loud. In the interview you think aloud with a tutor. Try a Computer Science problem with hints, follow-ups and Mia's feedback on how you think.