Re: [boost] dynamic_bitset count

Subject: Re: [boost] dynamic_bitset count
From: Andreas Klein (klein_at_[hidden])
Date: 2009-03-19 02:35:35

>
> How do these compare with the bit count algorithms at:
>
> http://graphics.stanford.edu/~seander/bithacks.html
>
These algorithms are simple algorithms that work wordwise. In our test 
program we have a lot of variations of such algorithms. In short for 
32-bit table look up it the best algorithm for a single word and for 
64-bit one should use a divde an conquer method like some of the one on 
this side.

But if the bitst is much larger than one words these algorithms are not 
optimal. You can save time if you use an algorithm that works on servel 
word in parallel. With our method we save about 60% time for bitset with 
more than 250 words. The Harley-Seal method saves 25%-50% time depending 
on the iteration an need only few words (about 10-30).

Alalgorithms have fallbacks, so they do not wast time, if they see only 
one word.

Best wishes
         Andreas Klein