5

我只想在 php.ini 中找到一些最快的设置位计数函数。

例如，0010101 => 3、00011110 => 4

我看到有很好的算法可以用 c++ 实现。 如何计算 32 位整数中设置的位数？

是否有任何php内置函数或最快的用户定义函数？

4

5 回答 5

8

您可以尝试使用二进制 AND 应用掩码，并使用 shift 逐位测试，使用将迭代 32 次的循环。

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;
}
于 2013-05-31T02:47:41.543 回答
3

我可以想出几种方法，但不确定哪种方法最快：

  • 使用 substr_count()
  • 用 '' 替换所有无 '1' 字符，然后使用 strlen()
  • 使用 preg_match_all()

PS：如果您从整数开始，这些示例将首先涉及使用 decbin()。

于 2013-05-31T03:09:46.260 回答
3

还有许多其他方法；但是对于十进制的 32 位整数，NumberOfSetBits绝对是最快的。

我最近偶然发现了Brian Kernighan 的算法，而O(log(n))不是大多数其他算法O(n)。我不知道为什么它在这里没有那么快出现；但它仍然比所有其他非专业功能具有可衡量的优势。

当然，没有什么可以打败NumberOfSetBits的O(1)。

我的基准：

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*

这些是我的一次运行中的数字（使用 PHP 7.0.22）；其他人在3.5秒组内表现出不同的顺序。我可以说 - 在我的机器上 - 这五个中的四个是相当的，并且bitsBySubstrInt由于类型转换而总是有点慢。

大多数其他方法都需要一个 decbin（这通常比实际计数需要更长的时间；我*在基准结果中用 a 标记了它们）；没有那条腿，只会BitsBySubstr接近胜利者。

我发现很明显，通过将其限制为仅现有字符可以使count_chars速度提高 3 倍。似乎数组索引需要相当长的时间。

编辑：

  • 添加了另一个preg_replace版本
  • 固定preg_match_all版本
  • 添加了 Kernighan´s 算法（任意大小整数的最快算法）
  • 将垃圾收集添加到基准测试功能
  • 重新运行基准
于 2016-07-15T08:56:36.827 回答
2

我的基准测试代码

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();

基准测试结果：

基准（NumberOfSetBits（））：1.429042 毫秒

基准（substr_count（））：1.672635 毫秒

基准（getBitCount（））：10.464981 毫秒

我认为 NumberOfSetBits() 和 substr_count() 是最好的。谢谢。

于 2013-05-31T03:28:16.167 回答
2

这个选项比 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
于 2019-09-24T20:33:48.017 回答