python - Python 中的按位编程

Question

我正在尝试编写一个程序来解决 ACM 问题，它必须非常快。解决该问题的一种数学上快速的方法是使用按位计算。但是，我正在使用 python，并且无法在位级别执行这些计算。问题是：

1. 计算位中 1 和 0 的数量。例如，我们如何计算二进制数字 100010 有两个 1 和四个 0。我能想象的唯一方法是将其转换为字符串并计算它们。但是这种转换首先抵消了在位级别工作所获得的所有速度。
2. 如何将描述二进制数字（例如“100101”）的字符串输入表示为Python中的实际二进制数字？目前我有一个将位转换为整数的函数，并对整数执行按位运算。
3. 有位数据类型吗？那就是我可以将输入作为位而不是字符串或整数接收吗？

我确实考虑过在 C++ 中编写诸如 bitSet 之类的类，但我感觉这也不会很快。PS 我正在使用的二进制数字可能高达 1000 位，我可能必须使用 1000 个这样的二进制数字，因此效率至关重要。

Answer 1

这是一个著名的计算一位的算法：

def bitCount(x):
    count = 0
    while x != 0:
       count += 1
       x &= (x-1)
    return count

关键是 x-1 具有与 x 相同的二进制表示，除了最低有效一位被清除为 0 并且所有尾随 0 都设置为 1。因此，设置x = x & (x-1)只是清除最低有效的一位。