在 Python 中使用位技巧的 64 位 popcount

Question

我想在 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

可惜不对。我们可以通过对 int 1234 执行 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'))

Answer 1

为了使解决方案显而易见，我将其添加到此处，但归功于@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;
}

Answer 2

问题是 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
>>>

在 Python 中使用位技巧的 64 位 popcount

64 bit popcount using bit tricks in Python

python

bit-manipulation