Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Re: Efficient bit counting with a twist.

by davido (Archbishop)
on Jan 27, 2013 at 07:23 UTC ( #1015565=note: print w/replies, xml ) Need Help??

in reply to Efficient bit counting with a twist.

I'm hesitant to post this because I haven't had the time to turn an idea into a viable solution (and won't have time tonight). I haven't tested this against your code or even on a large vector. It's just an idea that hit me. Then as I was looking for other ideas on algorithms I came across Hamming Weight, which mentions this:

With unlimited memory, we could simply create a large lookup table of the Hamming weight of every 64 bit integer.

Well, obviously we don't have unlimited memory, but using an array as a lookup for 16-bit integers would allow you to count 16 bits at a time rather than a single bit at a time. So this is a quick rough-draft. It doesn't take into consideration bit strings that are of lengths that aren't evenly divisible by 16. It's just an incomplete proof of concept before I go to bed... there's work to be done on it before it's a solution, and of course the work needs to be followed by benchmarks. :)

my @lookup; for( 0 .. 65535 ) { my $bits = sprintf "%b", $_; my $count = $bits =~ tr/1/1/; push @lookup, $count; } my $bitstring = ''; vec( $bitstring, 0, 32 ) = 1234567891; my $count = 0; for( 0 .. length( $bitstring ) / 2 - 1 ) { $count += $lookup[ vec( $bitstring, $_, 16 ) ]; } print $count, "\n";


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1015565]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2018-05-28 02:24 GMT
Find Nodes?
    Voting Booth?