Python 中的按位编程
Bitwise Programming in Python
我正在尝试编写一个程序来解决 ACM 问题，它必须非常快。解决该问题的数学快速方法是使用按位计算。但是，我正在使用 python 并且在位级别执行这些计算时遇到问题。问题是：
- 计算位中 1 和 0 的个数。比如我们如何计算二进制数100010有两个1和4个0。我能想到的唯一方法是将其转换为字符串并计算它们。但是这种转换首先抵消了在位级别工作所获得的所有速度。
- 如何将描述二进制数字（例如“100101”）的字符串输入表示为 Python 中的实际二进制数字？目前我有一个将位转换为整数的函数，我对整数执行按位运算。
- 有bit数据类型吗？那就是我可以接收输入而不是字符串或整数吗？
我确实考虑过用 C++ 写一个 class，比如 bitSet，但我感觉这也不会很快。 P.S。我正在处理的二进制数字可以大到 1000 位，我可能不得不处理 1000 个这样的二进制数字，因此效率是必不可少的。
这里有一个众所周知的计算一位的算法：
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) 只是清除最低有效一位。
我正在尝试编写一个程序来解决 ACM 问题，它必须非常快。解决该问题的数学快速方法是使用按位计算。但是，我正在使用 python 并且在位级别执行这些计算时遇到问题。问题是：
- 计算位中 1 和 0 的个数。比如我们如何计算二进制数100010有两个1和4个0。我能想到的唯一方法是将其转换为字符串并计算它们。但是这种转换首先抵消了在位级别工作所获得的所有速度。
- 如何将描述二进制数字（例如“100101”）的字符串输入表示为 Python 中的实际二进制数字？目前我有一个将位转换为整数的函数，我对整数执行按位运算。
- 有bit数据类型吗？那就是我可以接收输入而不是字符串或整数吗？
我确实考虑过用 C++ 写一个 class，比如 bitSet，但我感觉这也不会很快。 P.S。我正在处理的二进制数字可以大到 1000 位，我可能不得不处理 1000 个这样的二进制数字，因此效率是必不可少的。
这里有一个众所周知的计算一位的算法：
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) 只是清除最低有效一位。