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.

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,

dadoh

Thanks for the info.

BTW – The algo I posted is O(number of set bits).