Snippet: bitcount()

[Klaus Alexander Seistrup]

Tim Peters <tim_one at email.msn.com> wrote:

> > -- unless I decide to count several bits at a time, but
> > I wouldn't know how to construct such a thing.
>
> Oh, sure you do <wink>:
>
> count[0] = 0
> count[1] = 1
> count[2] = 1
> count[3] = 2
> ...
> count[255] = 8
>
> Now you can get the popcount of any one-byte int with one table-lookup.
> And the popcount of any N-byte int or long with N table lookups and N-1
> adds.  Put 2**16 entries in the table to cut the work in half.

I get your point, thanks, but I will spare this group for a posting of such
a 2**16 table, leave alone the full 32-bit version. ;-)

What I missed in my original posting, however, was to inform the forum that
the method fails for signed ints, like e.g. 0x8000000 (use longs instead),
and that it is best suited for, as you put it, "dealing with sparsely
populated large bit vectors", something my example with the two big twin
primes shows clearly.


Cheers,

  //Klaus

-- 
···[ Magnetic Ink ]·················································· ><> ···
···[ http://www.magnetic-ink.dk/ ]···········································