## Pop Count

Population Count is counting the number of bits set to one in a word (or any sized integer). I found pop counting as one of the most fascinating small algorithms in the bit twiddling category. There are so many uses for pop counting. Though, rarely, I find myself use them, to make stuff compact, like bit-arrays, special bit-flags which represent collections, etc… There are also popular algorithms which use pop counting in error-correcting codes and sound/image processing.

Here’s my favorite implementation:

``` int popcount(unsigned int x) { int c = 0; for (; x > 0; x &= x -1) c++; return c; }```

The whole concept is behind the mere formula: x &= x -1. But I will leave it for you to figure it out.

Speaking of pop count, Imri and I even used this same implementation above in the NULL Terminated Strip. I even hinted for this algorithm. And here’s a real 32 bits bugfree implementation (that strip has the bugs on purpose):

```XCHG EBX, EAX XOR EAX, EAX OR EBX, EBX JZ END A: LEA ECX, [EBX-1] INC EAX AND EBX, ECX JNZ A END: ```

Of course, most implementation are branch-free code, for the sake of speed. However – Lately, I added the SSE4 support to diStorm, and among the new instructions I found out there is a single instruction for it all: popcnt. :)

### 2 Responses to “Pop Count”

Shalom Gil

You possibly know this, but give a look at the third method for “Counting Bits” in the nice and free PcAsm book (http://www.drpaulcarter.com/pcasm/). I really like this O(log n), but there is a space tradeoff.

Warning: the first method is a spoiler of your post.

all the best,