如何最快的计算php中的设置位数?

v09wglhw  于 2022-12-21  发布在  PHP
关注(0)|答案(6)|浏览(125)

我只是想在php中找到一些最快的位计数函数。
例如,0010101 =〉3,00011110 =〉4
我看到有很好的算法,可以在c++. How to count the number of set bits in a 32-bit integer?中实现
有没有php内置函数或者最快的用户自定义函数?

z0qdvdin

z0qdvdin1#

您可以尝试使用二进制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;
}
0g0grzrc

0g0grzrc2#

我可以想出几种方法,但不确定哪一种会是最快的:

  • 使用子字符串计数()
  • 将所有非'1'字符替换为'',然后使用strlen()
  • 使用preg_match_all()

PS:如果你从一个整数开始,这些例子将首先使用decbin()。

ycggw6v2

ycggw6v23#

还有许多其他的方法;但是对于十进制32位整数,NumberOfSetBits无疑是最快的。
我最近偶然发现了Brian Kernighan´s algorithm,它有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*

这些是我运行的一个代码(使用PHP 7.0.22);其他人在3. 5秒组中显示了不同的顺序。我可以说-在我的机器上-这五个中的四个是相当相等的,并且由于类型转换,bitsBySubstrInt总是慢一点。
大多数其他方式需要一个decbin(这大多比实际计数需要更长的时间;我在基准测试结果中用*标记了它们);只有BitsBySubstr没有那条腿才能接近胜利者。
我发现值得注意的是,通过将count_chars限制为仅包含现有的字符,可以使其速度提高3倍。
编辑:

  • 添加了另一个preg_replace版本
  • 固定preg_match_all版本
  • 增加了Kernighan算法(任意大小整数的最快算法)
  • 在基准测试功能中添加了垃圾收集
  • 重新运行基准测试
wfveoks0

wfveoks04#

我的基准测试代码

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

对标结果:
基准(设置位数()):1.429042毫秒
基准(substr_count()):1.672635毫秒
基准测试(getBitCount()):10.464981毫秒
我认为NumberOfSetBits()和substr_count()是最好的。谢谢。

uxhixvfz

uxhixvfz5#

此选项比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;
}

弯痕(PHP 8)

1.78 s  bitsBySubstr
1.42 s  NumberOfSetBits
1.11 s  bitsCount
brqmpdu1

brqmpdu16#

下面是另一个解决方案,可能不是最快的,但也是最短的,它也适用于负数:

function countBits($num)
{
   return substr_count(decbin($num), "1");
}

相关问题