Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

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";

Dave


Comment on Re: Efficient bit counting with a twist.
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1015565]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2014-09-21 06:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (166 votes), past polls