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).