Henry's Points

Probably to count set bits in a byte or in 4 bytes will be most frequent asked question in the interview. Fortunately, I found four solution.

1. The mask and shift approach.
2. The Brian Kernighan approach.
3. The index into an array approach.
4. The MIT HACKMEM approach.

Make and Shift

unsigned char countbits_shift_method (unsigned char b)
{
unsigned char mask, count;

for (count = 0, mask = 0×80; mask != 0; mask >>= 1)
{
if (b & mask)
count++;
}

return (count);
}

Brian Kernighan

unsigned char countbits_bk_method (unsigned char b)
{
unsigned char count;

for (count = 0; b != 0; count++)
{
b &= b – 1; // this clears the LSB-most set bit
}

return (count);
}

Index into an Array

unsigned char parity_array [256] =
{ 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, … };
// Note that you need to fill-in this array

unsigned char countbits_array_method (unsigned char b)
{
return (parity_array [b]);
}

MIT Hack Memo

int BitCount(unsigned int u)

{
unsigned int uCount;

uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;

}

Share on Facebook

Tags: Coding // Add Comment »