Powers and Popcount

What is this?

Picture a row of light switches again. "Popcount" simply means counting how many switches are flipped on. And a "power of two" is a number whose row has exactly one switch on — like a single lit bulb in a dark hallway. These problems are about spotting that lone-light pattern and counting lit switches quickly.

💡 Fun fact: Counting set bits is so common that modern CPUs have a dedicated single instruction for it called POPCNT, and the operation traces back to the "side-counter" circuits in early IBM mainframes.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: a number is a power of two exactly when its binary form has a single set bit, and the trick n & (n-1) clears the lowest set bit. Counting how many times you can clear before reaching zero gives the popcount, and checking how many set bits remain tells you which power you're looking at.

The pattern

Two reflexes unlock this whole bucket. First, n & (n-1) flips off the rightmost 1: subtracting one turns the lowest set bit into zeros below it, and the AND keeps only the higher bits. Loop it and count iterations to get the number of set bits, touching the value once per set bit rather than once per bit.

Second, a power of two has exactly one set bit, so n > 0 && (n & (n-1)) == 0 settles "is this a power of two?" in one expression. Powers of four are a special case: they're powers of two whose single bit sits at an even position, which you verify with a fixed mask of the even bit positions. Powers of three don't have a clean binary signature — three is odd — so you either divide by three until you can't, or test divisibility against the largest power of three that fits the integer width.

The problems

• Number of 1 Bits — count set bits; loop n &= n-1 and tally, which runs in as many steps as there are ones.
• Power of Two — a single set bit; return n > 0 && (n & (n-1)) == 0.
• Power of Three — no tidy bit pattern; divide by three repeatedly or check divisibility by the max power of three.
• Power of Four — a single set bit at an even position; combine the power-of-two test with an even-position mask.

Key takeaways

1. n & (n-1) clears the lowest set bit — the workhorse for both counting bits and the power-of-two test.
2. Popcount via that trick costs one step per set bit, not one per bit width.
3. Power of two means exactly one set bit; power of four means that bit lands on an even position.
4. Power of three has no bit signature — fall back to division or a divisibility check.
5. Guard against n <= 0 before any single-bit test, since zero and negatives slip past a naive mask.