Algorithms / Bit Count Power
Least You Need to Know: Set Bits, Powers of Two, and Lowest-Bit Tricks
Many classic bit problems rely on what happens to the **lowest set bit**. That viewpoint explains power-of-two checks, efficient bit counting, and several constant-time transformations that show up repeatedly in interviews.
The least you need to know
- A positive power of two has exactly one set bit.
- `x & (x - 1)` removes the lowest set bit of a positive integer.
- Repeating that operation counts set bits in time proportional to the number of ones.
- `x & -x` isolates the lowest set bit in two's-complement arithmetic.
- Bit tricks still require careful handling of zero and sign edge cases.
Key notation
popcount(x)
number of 1-bits in x
x & (x - 1)
clear the lowest set bit
x & -x
isolate the lowest set bit
Tiny worked example
- For `x = 12` (`1100` in binary), `x - 1 = 1011`.
- ANDing them gives `1000`, which cleared the lowest set bit.
- Repeating that step once per remaining 1-bit gives a fast popcount method.
- A positive number is a power of two exactly when that clearing step leaves zero.
Common mistakes
- Students often forget that zero is not a power of two.
- Students often apply `x & (x - 1)` without first checking positivity.
- Students often memorize the trick without understanding why the lowest set bit changes.
How to recognize this kind of problem
- The prompt asks whether a number is a power of two or how many 1-bits it has.
- The lowest set bit seems to be the only part that changes.
- A naive loop over all bit positions feels unnecessary.
Next recommended lesson
Continue through this topic with Least You Need to Know: Bit Reasoning Depth and Mixed Interview Drills.
Least You Need to Know: Bit Reasoning Depth and Mixed Interview DrillsRelated lessons
Keep going with nearby lessons in the same topic.