In More Betterer Game of Life, I needed a popcount (aka Hamming weight) function to sum the one bits in a 64-bit value.

I started with the basic popcount1 below, scraped with little thought from the Hamming_weight wikipedia page.

I'd like to improve that, hence this node.

use strict;
use warnings;
use Benchmark qw(timethese);

sub popcount1 {
   my $x = shift;
   my $count;
   for ($count = 0; $x; ++$count) { $x &= $x - 1 }
   return $count;
}

sub popcount2 {
   return sprintf('%b', shift) =~ tr/1//;
}

# Update: unpack('%b*', pack('J', shift)) is better (see Rosetta ref. 
+below)
# This works but is slower: unpack('b*', pack('J', shift)) =~ tr/1//;
sub popcount3 {
   return unpack('%32b*', pack('Q', shift));
}

my $start = 2**32 - 42;
my $end   = $start + 1000000;

print "sanity test for correctness\n";
for my $i (0 .. 256, $start .. $end) {
   my $one = popcount1($i);
   my $two = popcount2($i);
   my $three = popcount3($i);
   # print "$i: $one $two $three\n";
   $one == $two or die;
   $one == $three or die;
}

timethese 50, {
   One   => sub { popcount1($_) for $start .. $end },
   Two   => sub { popcount2($_) for $start .. $end },
   Three => sub { popcount3($_) for $start .. $end },
};
[download]

Running the above program on my machine produced:

sanity test for correctness
Benchmark: timing 50 iterations of One, Three, Two...
   One: 29 wallclock secs (28.41 usr +  0.00 sys = 28.41 CPU) @  1.76/
+s (n=50)
 Three: 10 wallclock secs (10.00 usr +  0.00 sys = 10.00 CPU) @  5.00/
+s (n=50)
   Two: 10 wallclock secs (10.03 usr +  0.00 sys = 10.03 CPU) @  4.98/
+s (n=50)
[download]

Improvements welcome.

References

• More Betterer Game of Life
• Bitwise operators on binary objects
• Hamming weight (wikipedia, aka popcount)
• Rosetta Code (Perl)
• chess programming - Population Count (was on chessprogramming.wikispaces.com until wikispaces closed)
• Programming pages of Jasper Neumann
• Hacker's Delight book by Henry S. Warren Jr
• Math::GMPz
• GMP: The GNU Multiple Precision Arithmetic Library
• perlnumber
• Integer Arithmetic (use integer)

• marioroy's MCE Sandbox (Sandboxing with Perl MCE/Inline::C, C/OpenMP, and Codon) - popcount function in bits.h and Math::Prime::Util

Update: Added some C/C++ information from Hamming weight (wikipedia).

Some C compilers provide intrinsic functions that provide bit counting facilities. For example, GCC (since version 3.4 in April 2004) includes a builtin function __builtin_popcount that will use a processor instruction if available or an efficient library implementation otherwise. LLVM-GCC has included this function since version 1.5 in June 2005.

In C++ STL, the bit-array data structure bitset has a count() method that counts the number of bits that are set. In C++20, a new header <bit> was added, containing functions std::popcount and std::has_single_bit, taking arguments of unsigned integer types.

I've used this for code that builds with both GCC and MSVC:

// Make GCC __builtin_popcountll available with MSVC
// (used to calculate the Hamming weight efficiently)
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcountll __popcnt64
#define __builtin_popcount   __popcnt
#endif
[download]

Updated: Added more references (thanks oiskuu)