Boost logo

Boost :

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:
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

Boost list run by bdawes at, gregod at, cpdaniel at, john at