计算 32 位整数列表中的非零位
Counting non-zero bits in a list of 32-bit integers
编辑：问题已解决，不过请注意下面的代码，哈哈，我从一开始就在概念上有一些错误。
我尝试计算各种 32 位整数中的非零位的时间比我愿意承认的要长，但似乎总是有点偏差。
因此，例如，数字的正确数量的非零位：
13676 9190872 136669 -17621 -1631 -183 15570 0 495 468656377 -1340216 -91
将是：
8 12 10 26 25 27 8 0 8 18
然而，无论我尝试什么，我总是至少在几个数字（尤其是负数）上有几位数的偏差。
目前我正在使用：
def bitCount():
numbers = input().split()
answer = []
for num in numbers:
data = bin(((1 << 32) + int(num)) & -5)
bitCount = 0
for char in data[3:]:
if char == '1':
bitCount += 1
answer.append(str(bitCount))
print(' '.join(answer))
bitCount()
上面的一组数字生成：7 12 9 25 24 26 8 0 7 18 19 26
我做错了什么？我将如何解决这个问题？我无法想象它太复杂了，但经过数小时的搜索、阅读和试验后，我觉得我一定是遗漏了一些明显的东西。任何帮助将不胜感激。
我认为你让这件事变得比你需要的要难得多。我不明白 bin((1 << 32) + int(num) & -5) 应该做什么。正如您所注意到的，bin(number) returns 数字的二进制表示。所以现在你所要做的就是数 1。所以这会起作用：
for num in numbers:
data = bin(num)
bitCount = 0
for char in data:
if char == '1':
bitCount += 1
要诱导 python 转换为二进制补码，您可以将 32 位 1（即 0xFFFFFFFF）的位掩码应用于 n。如果 n 为正，则结果为 n。但是，如果 n 为负，则位掩码操作 returns 一个正数，它具有与负数 n 的二进制补码表示相同的所有位。因此，无论哪种情况，位数都是您所期望的。
从那里您可以简单地计算出作为 "bin" 函数结果的位数。
[bin(n & 0xFFFFFFFF).count("1") for n in numbers]
您的示例输入的结果是
[8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28]
除了给你期望的答案，this other question 还建议 bin(n).count 是找到整数汉明权重的最快方法
试试这个：
#!/usr/bin/env python
def bit_counter(number):
suffix = 2
if number < 0:
suffix = 3
bit = bin(number)
counter = 0
for i in bit[suffix:]:
if int(i) == 1:
counter += 1
return counter
def main():
a = 13676
print bit_counter(a)
a = -13676
print bit_counter(a)
if __name__ == "__main__":
main()
它适用于负数和非负数。
您的整个方法在 Python 中没有意义。
-17621 中的 1 位数，又名 -100010011010101 二进制，是 7。如果您期望 26，则您不需要询问 1 中的位数number，您要求的是解释为 C 32 位无符号整数的 C 32 位 2 补码有符号整数表示中的 1 位数。如果你想要 Python 中的那个，你必须明确地要求它。例如，您可以使用 num % 0x100000000.
与此同时，无论您从 (1 << 32) + num & -5 获得什么位技巧列表，它都是 也 假设 C int32 数学而不是实际的整数算术，所以它将又错了另外，我很确定你抄错了。另外，在 Python 中没有理由使用这些技巧——很可能它实际上会更慢，而不是更快，但无论哪种方式，它都会太慢，无法在一个时间里做无数次紧密的循环，而且速度足够快，可以做几次，所以这种挤出最后 5% 的优化在 Python 中比在 C 中毫无意义。（尽管许多这些老把戏实际上，使用现代编译器和 CPU，在 C 中也会减慢速度……）
并通过再次执行 [3:] 来取消初始 1 位假设您有一个 32 位表示，这又是错误的。 （这就是为什么您所有的正数都减去 1 的原因——您要去掉第一个 1 位。）
所以，让我们简单点：
answer = []
for num in numbers:
data = int(num) % 0x100000000
bits = format(data, 'b')
answer.append(str(bits.count('1')))
print(' '.join(answer))
注意我用的是format(data, 'b')，这样就不用把开头的0b去掉了。
或者，如果你想让它更紧凑：
print(' '.join(str(format(int(num)%0x100000000, 'b').count('1')) for num in numbers))
无论哪种方式，您都会得到：
8 12 10 26 25 27 8 0 8 18 20 28
…确实比您的预期输出多了两个数字，但是您的输入也比您的预期输出多了两个数字，所以我认为这是可以预料的。
整数中设置为 1 的位数称为其 汉明权重 或 人口计数。
有几种快速算法可以执行这样的计算。查看以下来源：
- Bit array 维基百科文章
- Bit Twiddling Hack
- 对Whosebug question #109023
的回答
- Bit Manipulation page 在 Python 维基上。
- The Aggregate Magic Algorithms（针对 32 位整数进行了优化）。
我首选的通用算法是：
def bit_count(n):
"""Return the number of bits set to 1 in the integer number 'n'.
This is called the Hamming weight or the population count of 'n'.
The algorithm performs as many iterations as there are set bits.
References:
The C Programming Language 2nd Ed., Kernighan & Ritchie, 1988.
Peter Wegner in CACM 3 (1960), 322.
"""
assert n >= 0, 'Argument of bit_count() must be non-negative'
count = 0
while n:
n &= n - 1
count += 1
return count
对于 32 位非负整数，以下函数速度更快：
def bit_count_parallel_32(n):
"""Return the number of set bits (1) present in the integer number 'n'.
This algorithm accepts only 32-bit non-negative integer numbers.
"""
assert 0 <= n < 2**32, ('Argument of bit_count_parallel_32() must be '
'non-negative and less than %d (2**32)') % 2**32
n = n - ((n >> 1) & 0x55555555)
n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
return (((n + (n >> 4) & 0x0F0F0F0F) * 0x01010101) & 0xffffffff) >> (8 + 16)
如果有人需要，这里是 64 位非负整数的版本：
def bit_count_parallel_64(n):
"""Return the number of set bits (1) present in the integer number 'n'.
This algorithm accepts only 64-bit non-negative integer numbers.
"""
assert 0 <= n < 2**64, ('Argument of bit_count_parallel_64() must be '
'non-negative and less than %d (2**64)') % 2**64
n = n - ((n >> 1) & 0x5555555555555555)
n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
return (((n + (n >> 4) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) \
& 0xffffffffffffffff) >> (8 + 16 + 32)
但是请注意，所有这些算法都不适用于负整数。如果需要使用负数，可以使用前面的函数统计负数的补码表示中设置的位数，例如：
>>> bit_count(-3 & 0xFF)
7
也可以看看专门介绍这本好书的网站 Hacker's Delight (Wayback Machine)。
最简单的方法是使用gmpy:
import gmpy
[gmpy.popcount(n & 0xFFFFFFFF) for n in numbers]
#>>> [8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28]
与字符串操作相比，这也可能相当快。
另一种方法是使用 Numpy：
import numpy
def count_bits_u32(u32):
u32 = (u32 & 0x55555555) + ((u32 & 0xAAAAAAAA) >> 1)
u32 = (u32 & 0x33333333) + ((u32 & 0xCCCCCCCC) >> 2)
u32 = (u32 & 0x0F0F0F0F) + ((u32 & 0xF0F0F0F0) >> 4)
u32 = (u32 & 0x00FF00FF) + ((u32 & 0xFF00FF00) >> 8)
u32 = (u32 & 0x0000FFFF) + ((u32 & 0xFFFF0000) >> 16)
return u32
count_bits_u32(numpy.array(numbers, dtype="uint32"))
#>>> array([ 8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28], dtype=uint32)
这对于大型值列表可能更有效，因为它打包整数并使用矢量化运算。
编辑：问题已解决，不过请注意下面的代码，哈哈，我从一开始就在概念上有一些错误。
我尝试计算各种 32 位整数中的非零位的时间比我愿意承认的要长，但似乎总是有点偏差。
因此，例如，数字的正确数量的非零位：
13676 9190872 136669 -17621 -1631 -183 15570 0 495 468656377 -1340216 -91
将是：
8 12 10 26 25 27 8 0 8 18
然而，无论我尝试什么，我总是至少在几个数字（尤其是负数）上有几位数的偏差。
目前我正在使用：
def bitCount():
numbers = input().split()
answer = []
for num in numbers:
data = bin(((1 << 32) + int(num)) & -5)
bitCount = 0
for char in data[3:]:
if char == '1':
bitCount += 1
answer.append(str(bitCount))
print(' '.join(answer))
bitCount()
上面的一组数字生成：7 12 9 25 24 26 8 0 7 18 19 26
我做错了什么？我将如何解决这个问题？我无法想象它太复杂了，但经过数小时的搜索、阅读和试验后，我觉得我一定是遗漏了一些明显的东西。任何帮助将不胜感激。
我认为你让这件事变得比你需要的要难得多。我不明白 bin((1 << 32) + int(num) & -5) 应该做什么。正如您所注意到的，bin(number) returns 数字的二进制表示。所以现在你所要做的就是数 1。所以这会起作用：
for num in numbers:
data = bin(num)
bitCount = 0
for char in data:
if char == '1':
bitCount += 1
要诱导 python 转换为二进制补码，您可以将 32 位 1（即 0xFFFFFFFF）的位掩码应用于 n。如果 n 为正，则结果为 n。但是，如果 n 为负，则位掩码操作 returns 一个正数，它具有与负数 n 的二进制补码表示相同的所有位。因此，无论哪种情况，位数都是您所期望的。
从那里您可以简单地计算出作为 "bin" 函数结果的位数。
[bin(n & 0xFFFFFFFF).count("1") for n in numbers]
您的示例输入的结果是
[8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28]
除了给你期望的答案，this other question 还建议 bin(n).count 是找到整数汉明权重的最快方法
试试这个：
#!/usr/bin/env python
def bit_counter(number):
suffix = 2
if number < 0:
suffix = 3
bit = bin(number)
counter = 0
for i in bit[suffix:]:
if int(i) == 1:
counter += 1
return counter
def main():
a = 13676
print bit_counter(a)
a = -13676
print bit_counter(a)
if __name__ == "__main__":
main()
它适用于负数和非负数。
您的整个方法在 Python 中没有意义。
-17621 中的 1 位数，又名 -100010011010101 二进制，是 7。如果您期望 26，则您不需要询问 1 中的位数number，您要求的是解释为 C 32 位无符号整数的 C 32 位 2 补码有符号整数表示中的 1 位数。如果你想要 Python 中的那个，你必须明确地要求它。例如，您可以使用 num % 0x100000000.
与此同时，无论您从 (1 << 32) + num & -5 获得什么位技巧列表，它都是 也 假设 C int32 数学而不是实际的整数算术，所以它将又错了另外，我很确定你抄错了。另外，在 Python 中没有理由使用这些技巧——很可能它实际上会更慢，而不是更快，但无论哪种方式，它都会太慢，无法在一个时间里做无数次紧密的循环，而且速度足够快，可以做几次，所以这种挤出最后 5% 的优化在 Python 中比在 C 中毫无意义。（尽管许多这些老把戏实际上，使用现代编译器和 CPU，在 C 中也会减慢速度……）
并通过再次执行 [3:] 来取消初始 1 位假设您有一个 32 位表示，这又是错误的。 （这就是为什么您所有的正数都减去 1 的原因——您要去掉第一个 1 位。）
所以，让我们简单点：
answer = []
for num in numbers:
data = int(num) % 0x100000000
bits = format(data, 'b')
answer.append(str(bits.count('1')))
print(' '.join(answer))
注意我用的是format(data, 'b')，这样就不用把开头的0b去掉了。
或者，如果你想让它更紧凑：
print(' '.join(str(format(int(num)%0x100000000, 'b').count('1')) for num in numbers))
无论哪种方式，您都会得到：
8 12 10 26 25 27 8 0 8 18 20 28
…确实比您的预期输出多了两个数字，但是您的输入也比您的预期输出多了两个数字，所以我认为这是可以预料的。
整数中设置为 1 的位数称为其 汉明权重 或 人口计数。
有几种快速算法可以执行这样的计算。查看以下来源：
- Bit array 维基百科文章
- Bit Twiddling Hack
- 对Whosebug question #109023 的回答
- Bit Manipulation page 在 Python 维基上。
- The Aggregate Magic Algorithms（针对 32 位整数进行了优化）。
我首选的通用算法是：
def bit_count(n):
"""Return the number of bits set to 1 in the integer number 'n'.
This is called the Hamming weight or the population count of 'n'.
The algorithm performs as many iterations as there are set bits.
References:
The C Programming Language 2nd Ed., Kernighan & Ritchie, 1988.
Peter Wegner in CACM 3 (1960), 322.
"""
assert n >= 0, 'Argument of bit_count() must be non-negative'
count = 0
while n:
n &= n - 1
count += 1
return count
对于 32 位非负整数，以下函数速度更快：
def bit_count_parallel_32(n):
"""Return the number of set bits (1) present in the integer number 'n'.
This algorithm accepts only 32-bit non-negative integer numbers.
"""
assert 0 <= n < 2**32, ('Argument of bit_count_parallel_32() must be '
'non-negative and less than %d (2**32)') % 2**32
n = n - ((n >> 1) & 0x55555555)
n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
return (((n + (n >> 4) & 0x0F0F0F0F) * 0x01010101) & 0xffffffff) >> (8 + 16)
如果有人需要，这里是 64 位非负整数的版本：
def bit_count_parallel_64(n):
"""Return the number of set bits (1) present in the integer number 'n'.
This algorithm accepts only 64-bit non-negative integer numbers.
"""
assert 0 <= n < 2**64, ('Argument of bit_count_parallel_64() must be '
'non-negative and less than %d (2**64)') % 2**64
n = n - ((n >> 1) & 0x5555555555555555)
n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
return (((n + (n >> 4) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) \
& 0xffffffffffffffff) >> (8 + 16 + 32)
但是请注意，所有这些算法都不适用于负整数。如果需要使用负数，可以使用前面的函数统计负数的补码表示中设置的位数，例如：
>>> bit_count(-3 & 0xFF)
7
也可以看看专门介绍这本好书的网站 Hacker's Delight (Wayback Machine)。
最简单的方法是使用gmpy:
import gmpy
[gmpy.popcount(n & 0xFFFFFFFF) for n in numbers]
#>>> [8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28]
与字符串操作相比，这也可能相当快。
另一种方法是使用 Numpy：
import numpy
def count_bits_u32(u32):
u32 = (u32 & 0x55555555) + ((u32 & 0xAAAAAAAA) >> 1)
u32 = (u32 & 0x33333333) + ((u32 & 0xCCCCCCCC) >> 2)
u32 = (u32 & 0x0F0F0F0F) + ((u32 & 0xF0F0F0F0) >> 4)
u32 = (u32 & 0x00FF00FF) + ((u32 & 0xFF00FF00) >> 8)
u32 = (u32 & 0x0000FFFF) + ((u32 & 0xFFFF0000) >> 16)
return u32
count_bits_u32(numpy.array(numbers, dtype="uint32"))
#>>> array([ 8, 12, 10, 26, 25, 27, 8, 0, 8, 18, 20, 28], dtype=uint32)
这对于大型值列表可能更有效，因为它打包整数并使用矢量化运算。