我想要在PHP中找到一些最快的设置位计数函数。
例如,0010101 => 3,00011110 => 4
我看到有一个很好的算法可以在C++中实现。 如何计算32位整数中设置位的数量?
是否有任何PHP内置函数或最快的用户定义函数可用?
我想要在PHP中找到一些最快的设置位计数函数。
例如,0010101 => 3,00011110 => 4
我看到有一个很好的算法可以在C++中实现。 如何计算32位整数中设置位的数量?
是否有任何PHP内置函数或最快的用户定义函数可用?
function getBitCount($value) {
$count = 0;
while($value)
{
$count += ($value & 1);
$value = $value >> 1;
}
return $count;
}
您还可以轻松地将您的函数放入 PHP 风格中
function NumberOfSetBits($v)
{
$c = $v - (($v >> 1) & 0x55555555);
$c = (($c >> 2) & 0x33333333) + ($c & 0x33333333);
$c = (($c >> 4) + $c) & 0x0F0F0F0F;
$c = (($c >> 8) + $c) & 0x00FF00FF;
$c = (($c >> 16) + $c) & 0x0000FFFF;
return $c;
}
我可以想出几种方法,但不确定哪一种是最快的:
PS:如果您从一个整数开始,这些示例将涉及首先使用decbin()。
有许多其他方法可选,但对于一个32位十进制整数,NumberOfSetBits
明显是最快的。
我最近偶然发现了 Brian Kernighan 算法,它具有O(log(n))
而不是大多数其他算法的O(n)
。我不知道为什么它在这里显示得不够快,但它仍然比所有其他非专用函数具有明显优势。
当然,没有什么能打败带有O(1)
的 NumberOfSetBits
。
我的基准测试:
function getBitCount($value) { $count = 0; while($value) { $count += ($value & 1); $value = $value >> 1; } return $count; }
function getBitCount2($value) { $count = 0; while($value) { if ($value & 1)$count++; $value >>= 1; } return $count; }
// if() instead of +=; >>=1 instead of assignment: sometimes slower, sometimes faster
function getBitCount2a($value) { for($count = 0;$value;$value >>= 1) if($value & 1)$count ++; return $count; }
// for instead of while: sometimes slower, sometimes faster
function getBitCount3($value) { for($i=1,$count=0;$i;$i<<=1) if($value&$i)$count++; return $count; }
// shifting the mask: incredibly slow (always shifts all bits)
function getBitCount3a($value) { for($i=1,$count=0;$i;$i<<=1) !($value&$i) ?: $count++; return $count; }
// with ternary instead of if: even slower
function NumberOfSetBits($v) {
// longest (in source code bytes), but fastest
$c = $v - (($v >> 1) & 0x55555555); $c = (($c >> 2) & 0x33333333) + ($c & 0x33333333);
$c = (($c >> 4) + $c) & 0x0F0F0F0F; $c = (($c >> 8) + $c) & 0x00FF00FF;
$c = (($c >> 16) + $c) & 0x0000FFFF; return $c;
}
function bitsByPregReplace($n) { return strlen(preg_replace('_0_','',decbin($n))); }
function bitsByNegPregReplace($n) { return strlen(preg_replace('/[^1]/','',decbin($n))); }
function bitsByPregMatchAll($n) { return preg_match_all('/1/',decbin($n)); }
function bitsBySubstr($i) { return substr_count(decbin($i), '1'); }
function bitsBySubstrInt($i) { return substr_count(decbin($i), 1); }
// shortest (in source code bytes)
function bitsByCountChars($n){ return count_chars(decbin($n))[49]; }
// slowest by far
function bitsByCountChars1($n) { return count_chars(decbin($n),1)[49]; }
// throws a notice for $n=0
function Kernighan($n) { for(;$n;$c++)$n&=$n-1;return$c; }
// Brian Kernighan’s Algorithm
function benchmark($function)
{
gc_collect_cycles();
$t0=microtime();
for($i=1e6;$i--;) $function($i);
$t1=microtime();
$t0=explode(' ', $t0); $t1=explode(' ', $t1);
echo ($t1[0]-$t0[0])+($t1[1]-$t0[1]), " s\t$function\n";
}
benchmark('getBitCount');
benchmark('getBitCount2');
benchmark('getBitCount2a');
benchmark('getBitCount3');
benchmark('getBitCount3a');
benchmark('NumberOfSetBits');
benchmark('bitsBySubstr');
benchmark('bitsBySubstrInt');
benchmark('bitsByPregReplace');
benchmark('bitsByPregMatchAll');
benchmark('bitsByCountChars');
benchmark('bitsByCountChars1');
benchmark('decbin');
基准测试结果(已排序)
> php count-bits.php
2.286831 s decbin
1.364934 s NumberOfSetBits
3.241821 s Kernighan
3.498779 s bitsBySubstr*
3.582412 s getBitCount2a
3.614841 s getBitCount2
3.751102 s getBitCount
3.769621 s bitsBySubstrInt*
5.806785 s bitsByPregMatchAll*
5.748319 s bitsByCountChars1*
6.350801 s bitsByNegPregReplace*
6.615289 s bitsByPregReplace*
13.863838 s getBitCount3
16.39626 s getBitCount3a
19.304038 s bitsByCountChars*
bitsBySubstrInt
总是稍微慢一些。*
标记了它们);只有 BitsBySubstr
在没有那种缺陷的情况下会接近获胜者。count_chars
快3倍。似乎数组索引需要相当多的时间。preg_replace
版本preg_match_all
版本NumberOfSetBits
的计时有笔误吗?如果没有,它在错误的代码块中。 - Rick James我的基准测试代码
start_benchmark();
for ($i = 0; $i < 1000000; $i++) {
getBitCount($i);
}
end_benchmark();
start_benchmark();
for ($i = 0; $i < 1000000; $i++) {
NumberOfSetBits($i);
}
end_benchmark();
start_benchmark();
for ($i = 0; $i < 1000000; $i++) {
substr_count(decbin($i), '1');
}
end_benchmark();
基准测试结果:
benchmark (NumberOfSetBits()) : 1.429042 毫秒
benchmark (substr_count()) : 1.672635 毫秒
benchmark (getBitCount()): 10.464981 毫秒
我认为NumberOfSetBits()和substr_count()是最佳选择。谢谢。
substr_count(decbin($i), '1');
比NumberOfSetBits()
更快。 - Daniel P这个选项比NumberOfSetBits($v)稍微快一点
function bitsCount(int $integer)
{
$count = $integer - (($integer >> 1) & 0x55555555);
$count = (($count >> 2) & 0x33333333) + ($count & 0x33333333);
$count = ((((($count >> 4) + $count) & 0x0F0F0F0F) * 0x01010101) >> 24) & 0xFF;
return $count;
}
基准测试(PHP8)
1.78 s bitsBySubstr
1.42 s NumberOfSetBits
1.11 s bitsCount
这里是另一种解决方案。可能不是最快的,但是它是最短的解决方案。它也适用于负数:
function countBits($num)
{
return substr_count(decbin($num), "1");
}
function countSetBits($int){ return substr_count(decbin($int), '1'); }
- BlitZ