The question: "Given a 32-bit unsigned integer, how do you count how many 1s are in it ?" is one of favorite interview quizzes. Naturally, the candidate is expected to code the "trivial" solution correctly - shifting right 32 times, counting when 1 "was shifted", etc. There are other techniques of doing it, up to a constant-time cool bit-fiddling trick. This is a nice topic, I think I should write an article about it once...

Anyway, lately I've heard of a new tehcnique to do it, which is also very cool, and has a curious complexity bound. It's O(b) where 'b' is the actual number of 1s in the given number.

Consider an unsigned integer `num`

. What is: `num & (num - 1)`

? Without trying a lot, it's hard to come up with the answer. What it actually does, is "clear the rightmost 1 in the bit representation of `num`

". Weird, huh ? It is rather simple to prove, though:

Consider a `num`

whose lsb (rightmost bit) is 1 (i.e. an odd number). `num - 1`

is then the same number with that rightmost 1 becoming 0. So, obviously `num & (num - 1)`

is "`num`

with the rightmost bit cleared". So far so good.

Now lets consider even numbers (lsb = 0). Lets even generalize: `num`

's binary representation ends with 10...0 (1 and, say, N 0s). Clearly, for such a number, `num - 1`

ends with 01...1 (0 and N 1s). So, `num & (num - 1)`

again cleared that rightmost 1.

Only one special case left: whe "all 0" number. But since `num`

is 0, whatever it is &-ed with, the result is 0.

Thus we have proved that for each `num`

, `num & (num - 1)`

clears its rightmost 1. So, the code for counting the amount of 1s is:

unsigned count_ones(unsigned num) { unsigned count = 0; while (num) { num &= num - 1; ++count; } return count; }

On each iteration, the rightmost 1 of `num`

is cleared. `count`

takes notice of how many times it happens until `num`

becomes 0. If `num`

has five 1 bits, the loop will iterate 5 times, etc.

**An additional piece of trivia:** `num & (num - 1)`

can be useful for another "binary trick". How would you quickly check if a number is a power of 2 ? Answer: If `num & (num - 1)`

is 0, `num`

is a power of 2. Powers of 2 have a single 1 in their binary representation, so the `num & (num - 1)`

operation clears it and leaves 0 as the result. For all other numbers it won't work because other 1s will be left.

## Comments

comments powered by Disqus