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

From: Rene Rivera (grafik666_at_[hidden])
Date: 2002-07-30 23:05:58

[2002-07-30] Jeremy Siek wrote:
>On Wed, 31 Jul 2002, Gennaro Prota wrote:
[snip]
>> a) providing an implementation with a 16- or 32-slot table; then using
>> conditional compilation to choose between that table implementation
>> and the portable one. If the combination table-size/count()-loop is
>> not suitable for a given C++ platform boost automatically switches to
>> the portable 1-bit-a-time code.
>>
>>
>> b) as above, but with the possibility for the user to provide his own
>> bit-count solution for a single byte. For instance changing the loop
>> above in:
>>
>>     num +=  user_defined_count (*p);
>>
>> Again, suitable macros could be used to control whether to switch to
>> the slow solution or asking the user to provide the
>> user_defined_count() function.

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

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>

At 12 operations per byte, or 3/2 per bit.

Enjoy :-)

-- grafik - Don't Assume Anything
-- rrivera_at_[hidden] - grafik_at_[hidden]
-- 102708583_at_icq - Grafik666_at_AIM - Grafik_at_[hidden]