# Boost :

From: Anatoliy Kuznetsov (anatoliy_kuznetsov_at_[hidden])
Date: 2002-07-31 08:43:21

Hi !

> In game programming bit counting has been reinvented
> many times and so far
> the fastest, most portable way to do this doesn't
> require any tables and is
> a fixed set of operations per bit (or byte, or word,
> depending on the
> granularity you think in).

I also work on bitsets and use similar algorithm on
different granularities. It looks like that it pays
off only on 64-bit integers (on 64-bit platforms).
Otherwise bitcount table looks faster.

>
> This counts the 1 bits on an 8 bit byte:
>
> byte x = <some_bit_value>;
> byte a = (x & 0xAA) >> 1;
> byte b = (x & 0x55);
> x = a+b;
> a = (x & 0xCC) >> 2;
> b = (x & 0x33);
> x = a+b;
> a = (x & 0xF0) >> 4;
> b = (x & 0x0F);
> x = a+b;
>
> x == <the bit count>
>

Here is the code:

int count(long long b)
{
b = (b & 0x5555555555555555LU) + (b >> 1 &
0x5555555555555555LU);
b = (b & 0x3333333333333333LU) + (b >> 2 &
0x3333333333333333LU);
b = b + (b >> 4) & 0x0F0F0F0F0F0F0F0FLU;
b = b + (b >> 8);
b = b + (b >> 16);
b = b + (b >> 32) & 0x0000007F;

return (int) b;
}

Regards,
Anatoliy Kuznetsov
http://bmagic.sourceforge.net

__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com