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]

Update: In the final/best Perl solution Re^2: More Betterer Game of Life searching for popcount reveals that I ended up using:

   # $cnt += popcount($row->[$iy] & $BM_MIDDLE);
   $cnt += sprintf('%b', $row->[$iy] & $BM_MIDDLE) =~ tr/1//;
[download]

Updated: Added more references (thanks oiskuu)

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.