我只是想在php中找到一些最快的位计数函数。
例如,0010101 =〉3,00011110 =〉4
我看到有很好的算法,可以在c++. How to count the number of set bits in a 32-bit integer?中实现
有没有php内置函数或者最快的用户自定义函数?
我只是想在php中找到一些最快的位计数函数。
例如,0010101 =〉3,00011110 =〉4
我看到有很好的算法,可以在c++. How to count the number of set bits in a 32-bit integer?中实现
有没有php内置函数或者最快的用户自定义函数?
6条答案
按热度按时间z0qdvdin1#
您可以尝试使用二进制AND应用掩码,并使用shift逐个测试位,使用一个将迭代32次的循环。
您还可以轻松地将函数转换为PHP样式
0g0grzrc2#
我可以想出几种方法,但不确定哪一种会是最快的:
PS:如果你从一个整数开始,这些例子将首先使用decbin()。
ycggw6v23#
还有许多其他的方法;但是对于十进制32位整数,
NumberOfSetBits
无疑是最快的。我最近偶然发现了Brian Kernighan´s algorithm,它有
O(log(n))
而不是大多数其他的有O(n)
,我不知道为什么它在这里出现的不那么快;但是它仍然具有优于所有其它非专用功能的可测量的优点。当然,没有什么能用
O(1)
击败NumberOfSetBits
。这些是我运行的一个代码(使用PHP 7.0.22);其他人在3. 5秒组中显示了不同的顺序。我可以说-在我的机器上-这五个中的四个是相当相等的,并且由于类型转换,
bitsBySubstrInt
总是慢一点。大多数其他方式需要一个decbin(这大多比实际计数需要更长的时间;我在基准测试结果中用
*
标记了它们);只有BitsBySubstr
没有那条腿才能接近胜利者。我发现值得注意的是,通过将
count_chars
限制为仅包含现有的字符,可以使其速度提高3倍。编辑:
preg_replace
版本preg_match_all
版本wfveoks04#
我的基准测试代码
对标结果:
基准(设置位数()):1.429042毫秒
基准(substr_count()):1.672635毫秒
基准测试(getBitCount()):10.464981毫秒
我认为NumberOfSetBits()和substr_count()是最好的。谢谢。
uxhixvfz5#
此选项比NumberOfSetBits($v)稍快一些
弯痕(PHP 8)
brqmpdu16#
下面是另一个解决方案,可能不是最快的,但也是最短的,它也适用于负数: