And after all that if it's still slow and you're sure its the optimal format but you still want to stay in Perl consider dropping into C via Inline::C or an XS module and do the bit twiddling there instead.

Dropping to C is indeed an option, but bit twiddling should be pretty darn fast in Perl too. To generate 1 million random numbers and process their bits took 4 seconds:

my $stime = time;

for (1..1_000_000) {
   my $i = rand(4294967295);
   while ($i) {
      $count++ if $i>>=2;
   }
}

my $etime = time;
print($etime-$stime, " seconds to count the $count 1s in 32_000_000 bi
+ts\n");
[download]

4 seconds to count the 14665902 1s in 32_000_000 bits
[download]

Update: Oops! if $i>>=2; should be if ($i>>=2) & 1; as per reply.

my $stime = time;

for (1..1_000_000) {
   my $i = rand(4294967295);
   while ($i) {
      $count++ if $i>>=2;
   }
}

my $etime = time;
print($etime-$stime, " seconds to count the $count 1s in 32_000_000 bi
+ts\n");
[download]

That isn't counting 1s. It kind of assigns a score from 0 to 15 based on how big the number is, with most numbers scoring 15, and it is equivalent to

   $count +=
      ($i > 2**2) +
      ($i > 2**4) +
      ($i > 2**6) +
      ...
      ($i > 2**26) +
      ($i > 2**28) +
      ($i > 2**30);
[download]

which on average gives 14 2/3. (3/4 of the numbers get 15, 3/4 of the remaining numbers get 14, 3/4 of the remaining numbers get 13, etc.)

To count 1s (one of many ways):

do {
   ++$count if $i & 1;
} while $i >>= 1;
[download]

--
Online Fortune Cookie Search