This (labelled "six" ) is the fastest C/Perl method I found when I was looking a (long) while ago) that works on chips that don't have a popcnt instruction:
#! perl -slw
use strict; package SparseBitVector; use Config;
use Inline C => Config => BUILD_NOISY => 1;
use Inline C => <<'END_C', NAME => 'Junk', CLEAN_AFTER_BUILD =>0;
typedef unsigned __int64 U64;
typedef __int64 I64;
unsigned popcnt( SV *sv ) {
U64 x = (U64) SvUVX( sv );
x -=( x >> 1 ) & 0x5555555555555555ULL;
x = ( x & 0x3333333333333333ULL ) + ( ( x >> 2 ) & 0x3333333333333
+333ULL );
x = ( x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
return (unsigned)( ( x * 0x0101010101010101ull ) >> 56 );
}
END_C
use Benchmark qw( cmpthese );
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//;
}
sub popcount3 {
return unpack('%32b*', pack('Q', shift));
}
sub popcount4 {
return unpack( '%32b*', pack('Q', $_[0] ) );
}
my $start = 2**32 - 42;
my $end = $start + 1000000;
print "sanity test for correctness\n";
for my $i (0 .. 256, $start .. $end) {
my $two = popcount2($i);
my $three = popcount3($i);
my $four = popcount4( $i );
my $six = popcnt( $i );
$three == $two or print "$i: $two $three\n" and die;
$four == $six and $three == $six or print "$i: 2:$two 3:$three 6:$s
+ix\n" and die;
}
cmpthese -3, {
# One => sub { popcount1($_) for $start .. $end },
Two => sub { popcount2($_) for $start .. $end },
Three => sub { popcount3($_) for $start .. $end },
Four => sub { popcount4($_) for $start .. $end },
Six => sub { popcnt( $_) for $start .. $end },
};
Outputs:
C:\test>1199987.pl
sanity test for correctness
Rate Two Three Four Six
Two 1.02/s -- -4% -5% -58%
Three 1.06/s 4% -- -1% -57%
Four 1.08/s 5% 1% -- -56%
Six 2.45/s 140% 131% 128% --
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
In the absence of evidence, opinion is indistinguishable from prejudice.
Suck that fhit
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.