Skip to content
Back to AlgorithmsAll lessons

Algorithms

Bit Manipulation

O(number of set bits) time for the counting trick — far fewer steps than checking every single bit position · O(1) space.

The idea, in plain English

Every number is stored as a row of on and off switches, called bits — this is binary, the number system computers use. Some tricks flip those switches directly instead of doing normal math. One handy trick, n & (n - 1), always turns off the rightmost switch that is on. Do that again and again, and you are counting how many switches were on. If a number has exactly one switch on, it is a power of two.

How it works

  1. 1To count 'set bits', the switches that are on: repeat n = n & (n - 1), which clears the lowest set bit each time. Count how many times you did this before n reached 0.
  2. 2To check if a number is a power of two: a power of two has exactly one set bit, so n & (n - 1) comes out to exactly 0 for it, and only for it, among positive numbers.
  3. 3Both tricks use the same operation, n & (n - 1). They just answer two different questions.

When you'd use it

Use these tricks when speed matters for counting or checking flags — feature flags packed into a single number, checking if a size works well as a power of two (like array capacities or hash table sizes), or anywhere bitwise math beats looping over digits.

Common beginner mistakes

  • Forgetting the n > 0 check before the power-of-two test. Without it, the trick wrongly calls 0 a power of two.
  • Assuming bit tricks behave the same way on negative numbers. Their underlying binary representation, called two's complement, works differently.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Set bits in 44: 3
Is 16 a power of two? yes
Is 18 a power of two? no

See it in motion

Watch the bits flipcount set bits · 194O(number of set bits) time for the counting trick — far fewer steps than checking every single bit position · O(1) space.

194 in binary is 11000010. We count its set bits by clearing the lowest one each step.

194
Value
0
Set bits
—
Power of 2?
0/5
Step
Set bit (1)Lowest set bit clearingResult after clearingUnset bit (0)

Not sure this is the right topic? See the learning paths → or where this leads →