Clear questions and runnable codeget the best and fastest answer 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";
[download]```

Dave

Log In?
 Username: Password:

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

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2018-02-24 00:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When it is dark outside I am happiest to see ...

Results (310 votes). Check out past polls.

Notices?