Re: [boost] dynamic_bitset: performances and other notes - dyn_bs_modifications #1.zip (0/1)

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