eyepopslikeamosquito has asked for the wisdom of the Perl Monks concerning the following question:
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 }, };
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)
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
Updated: Added more references (thanks oiskuu)