Insanely Low-Level

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

This entry was posted on Tuesday, June 5th, 2007 at 3:12 pm and is filed under Assembly, Optimization. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.