Re: Efficient bit counting with a twist.

[davido]

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