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.
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 & -xisolates 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
Worked example
- For
x = 12(1100in 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 it
- 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.