Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
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 avoiding work at the Monastery: (9)
As of 2015-07-07 02:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (86 votes), past polls