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

From: Victor A. Wagner, Jr. (vawjr_at_[hidden])
Date: 2002-07-31 22:29:26

for _speed_ I'll waste the 256 bytes and do a single indexed load anytime.

At Tuesday 2002/07/30 21:05, you wrote:
>[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]
>_______________________________________________
>Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Victor A. Wagner Jr.      http://rudbek.com
PGP RSA fingerprint = 4D20 EBF6 0101 B069 3817 8DBF C846 E47A
PGP D-H fingerprint = 98BC 65E3 1A19 43EC 3908 65B9 F755 E6F4 63BB 9D93
The five most dangerous words in the English language:
               "There oughta be a law"