Python中使用位技巧的64位popcount
Python中使用位技巧的64位popcount
提问于 2020-01-28 06:42:43
我想在Python中实现64位popcount的小技巧。我尝试复制this code，如下所示：
def popcount_test(y):
y -= ((y >> 1) & 0x5555555555555555)
y = (y & 0x3333333333333333) + (y >> 2 & 0x3333333333333333)
return ((y + (y >> 4)) & 0xf0f0f0f0f0f0f0f) * 0x101010101010101 >> 56不幸的是，这是不正确的。我们可以通过在int1234上执行popcount来看到这一点。
popcount_test(1234)
261
bin(1234).count('1')
5在Python中实现的正确的位技巧是什么？
可以使用以下命令执行进一步的测试：
import random
num = random.randint(0, 2**64-1)
print(popcount_test(num), bin(num).count('1'))回答 2
Stack Overflow用户
回答已采纳
发布于 2020-01-28 07:43:59
问题是C版本期望乘法结果只产生低位64位，但是Python使用扩展精度整数，所以你得到了整个结果。您可以通过将结果移位后掩码为8位来修复它：
def popcount_test(y):
y -= ((y >> 1) & 0x5555555555555555)
y = (y & 0x3333333333333333) + (y >> 2 & 0x3333333333333333)
return (((y + (y >> 4)) & 0xf0f0f0f0f0f0f0f) * 0x101010101010101 >> 56) & 0xff这会产生以下结果：
>>> popcount_test(1234)
5
>>> Stack Overflow用户
发布于 2020-01-28 06:52:57
为了使解决方案显而易见，我在这里添加了它，但功劳归功于@TimPeters和@Heap-Overflow
def popcount_test(y):
y -= ((y >> 1) & 0x5555555555555555)
y = (y & 0x3333333333333333) + (y >> 2 & 0x3333333333333333)
return ((((y + (y >> 4)) & 0xf0f0f0f0f0f0f0f) * 0x101010101010101) >> 56) & 0xff这就是Python在Modules/mathmodule.c中的工作方式
static unsigned long
count_set_bits(unsigned long n)
{
unsigned long count = 0;
while (n != 0) {
++count;
n &= n - 1; /* clear least significant bit */
}
return count;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59939945
复制相关文章
相似问题
腾讯云开发者
