Python：设置位计数（popcount）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/407587/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python: Set Bits Count (popcount)
提问by Krishna Chaitanya
Few blob's have been duplicated in my database(oracle 11g), performed XOR operations on the blob using UTL_RAW.BIT_XOR. After that i wanted to count the number of set bits in the binary string, so wrote the code above.
在我的数据库（oracle 11g）中复制了很少的 blob，使用 UTL_RAW.BIT_XOR 对 blob 执行 XOR 操作。之后我想计算二进制字符串中设置位的数量，所以写了上面的代码。
During a small experiment, i wanted to see what is the hex and the integer value produced and wrote this procedure..
在一个小实验中，我想看看生成的十六进制和整数值是什么，并编写了这个程序。
SQL> declare
2
3 vblob1 blob;
4
5 BEGIN
6
7 select leftiriscode INTO vblob1 FROM irisdata WHERE irisid=1;
8
9 dbms_output.put_line(rawtohex(vblob1));
10
11
12 dbms_output.put_line(UTL_RAW.CAST_TO_binary_integer(vblob1));
13
14
15 END;
16 /
OUTPUT: HEXVALUE:
输出： 十六进制：
0F0008020003030D030C1D1C3C383C330A3311373724764C54496C0A6B029B84840547A341BBA83D
BB5FB9DE4CDE5EFE96E1FC6169438344D604681D409F9F9F3BC07EE0C4E0C033A23B37791F59F84F
F94E4F664E3072B0229DA09D9F0F1FC600C2E380D6988C198B39517D157E7D66FE675237673D3D28
3A016C01411003343C76740F710F0F4F8FE976E1E882C186D316A63C0C7D7D7D7D397F016101B043
0176C37E767C7E0C7D010C8302C2D3E4F2ACE42F8D3F3F367A46F54285434ABB61BDB53CBF6C7CC0
F4C1C3F349B3F7BEB30E4A0CFE1C85180DC338C2C1C6E7A5CE3104303178724CCC5F451F573F3B24
7F24052000202003291F130F1B0E070C0E0D0F0E0F0B0B07070F1E1B330F27073F3F272E2F2F6F7B
2F2E1F2E4F7EFF7EDF3EBF253F3D2F39BF3D7F7FFED72FF39FE7773DBE9DBFBB3FE7A76E777DF55C
5F5F7ADF7FBD7F6AFE7B7D1FBE7F7F7DD7F63FBFBF2D3B7F7F5F2F7F3D7F7D3B3F3B7FFF4D676F7F
5D9FAD7DD17F7F6F6F0B6F7F3F767F1779364737370F7D3F5F377F2F3D3F7F1F2FE7709FB7BCB77B
0B77CF1DF5BF1F7F3D3E4E7F197F571F7D7E3F7F7F7D7F6F4F75FF6F7ECE2FFF793EFFEDB7BDDD1F
FF3BCE3F7F3FBF3D6C7FFF7F7F4FAF7F6FFFFF8D7777BF3AE30FAEEEEBCF5FEEFEE75FFEACFFDF0F
DFFFF77FFF677F4FFF7F7F1B5F1F5F146F1F1E1B3B1F3F273303170F370E250B
INTEGER VALUE: 15
There was a variance between the hex code and the integer value produced, so used the following python code to check the actual integer value.
十六进制代码和生成的整数值之间存在差异，因此使用以下python代码检查实际整数值。
print int("0F0008020003030D030C1D1C3C383C330A3311373724764C54496C0A6B029B84840547A341BBA83D
BB5FB9DE4CDE5EFE96E1FC6169438344D604681D409F9F9F3BC07EE0C4E0C033A23B37791F59F84F
F94E4F664E3072B0229DA09D9F0F1FC600C2E380D6988C198B39517D157E7D66FE675237673D3D28
3A016C01411003343C76740F710F0F4F8FE976E1E882C186D316A63C0C7D7D7D7D397F016101B043
0176C37E767C7E0C7D010C8302C2D3E4F2ACE42F8D3F3F367A46F54285434ABB61BDB53CBF6C7CC0
F4C1C3F349B3F7BEB30E4A0CFE1C85180DC338C2C1C6E7A5CE3104303178724CCC5F451F573F3B24
7F24052000202003291F130F1B0E070C0E0D0F0E0F0B0B07070F1E1B330F27073F3F272E2F2F6F7B
2F2E1F2E4F7EFF7EDF3EBF253F3D2F39BF3D7F7FFED72FF39FE7773DBE9DBFBB3FE7A76E777DF55C
5F5F7ADF7FBD7F6AFE7B7D1FBE7F7F7DD7F63FBFBF2D3B7F7F5F2F7F3D7F7D3B3F3B7FFF4D676F7F
5D9FAD7DD17F7F6F6F0B6F7F3F767F1779364737370F7D3F5F377F2F3D3F7F1F2FE7709FB7BCB77B
0B77CF1DF5BF1F7F3D3E4E7F197F571F7D7E3F7F7F7D7F6F4F75FF6F7ECE2FFF793EFFEDB7BDDD1F
FF3BCE3F7F3FBF3D6C7FFF7F7F4FAF7F6FFFFF8D7777BF3AE30FAEEEEBCF5FEEFEE75FFEACFFDF0F
DFFFF77FFF677F4FFF7F7F1B5F1F5F146F1F1E1B3B1F3F273303170F370E250B",16)
Answer:
回答：
611951595100708231079693644541095422704525056339295086455197024065285448917042457
942011979060274412229909425184116963447100932992139876977824261789243946528467423
887840013630358158845039770703659333212332565531927875442166643379024991542726916
563271158141698128396823655639931773363878078933197184072343959630467756337300811
165816534945075483141582643531294791665590339000206551162697220540050652439977992
246472159627917169957822698172925680112854091876671868161705785698942483896808137
210721991100755736178634253569843464062494863175653771387230991126430841565373390
924951878267929443498220727531299945275045612499928105876210478958806304156695438
684335624641395635997624911334453040399012259638042898470872203581555352191122920
004010193837249388365999010692555403377045768493630826307316376698443166439386014
145858084176544890282148970436631175577000673079418699845203671050174181808397880
048734270748095682582556024378558289251964544327507321930196203199459115159756564
507340111030285226951393012863778670390172056906403480159339130447254293412506482
027099835944315172972281427649277354815211185293109925602315480350955479477144523
387689192243720928249121486221114300503766209279369960344185651810101969585926336
07333771272398091
To get the set-bit count I have written the following code in C:
为了获得设置位计数，我用 C 编写了以下代码：
int bitsoncount(unsigned x)
{
unsigned int b=0;
if(x > 1)
b=1;
while(x &= (x - 1))
b++;
return b;
}
When I tried the same code in python it did not work. I am new to python through curiosity I'm experimenting, excuse me if am wrong.
当我在 python 中尝试相同的代码时，它不起作用。我是 Python 新手，因为我正在试验的好奇心，如果我错了，请原谅。
def bitsoncount(x):
b=0;
if(x>1):
b=1;
while(x &= (x-1)):
I get an error at the last line, need some help in resolving this and implementing the logic in python :-)
我在最后一行出现错误，需要一些帮助来解决这个问题并在 python 中实现逻辑:-)
I was interested in checking out the set bits version in python after what i have seen!
在我看到之后，我有兴趣在 python 中查看 set bits 版本！
Related question: Best algorithm to count the number of set bits in a 32-bit integer?
相关问题：计算 32 位整数中设置位数的最佳算法？
回答by jfs
Python 2.6 or 3.0:
Python 2.6 或 3.0：
def bitsoncount(x):
return bin(x).count('1')
Example:
例子：
>>> x = 123
>>> bin(x)
'0b1111011'
>>> bitsoncount(x)
6
Or
或者
Matt Howells's answerin Python:
Matt Howells在 Python 中的回答：
def bitsoncount(i):
assert 0 <= i < 0x100000000
i = i - ((i >> 1) & 0x55555555)
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
回答by Autoplectic
what you're looking for is called the Hamming Weight.
你要找的东西叫做汉明重量。
in python 2.6/3.0 it can be found rather easily with:
在 python 2.6/3.0 中，它可以很容易地找到：
bits = sum( b == '1' for b in bin(x)[2:] )
回答by Alex
What version of Python are you using? First off, Python uses white space not semicolon's, so to start it should look something like this...
您使用的是什么版本的 Python？首先，Python 使用空格而不是分号，所以一开始它应该看起来像这样......
def bitsoncount(x):
b=0
while(x > 0):
x &= x - 1
b+=1
return b
回答by gnud
The direct translation of your C algorithm is as follows:
你的C算法的直接翻译如下：
def bitsoncount(x):
b = 0
while x > 0:
x &= x - 1
b += 1
return b
回答by Kiv
Maybe this is what you mean?
也许这就是你的意思？
def bits_on_count(x):
b = 0
while x != 0:
if x & 1: # Last bit is a 1
b += 1
x >>= 1 # Shift the bits of x right
return b
There's also a way to do it simply in Python 3.0:
还有一种方法可以在 Python 3.0 中简单地做到这一点：
def bits_on_count(x):
return sum(c=='1' for c in bin(x))
This uses the fact that bin(x) gives a binary representation of x.
这使用 bin(x) 给出 x 的二进制表示这一事实。
回答by tzot
Try this module:
试试这个模块：
import sys
if sys.maxint < 2**32:
msb2= 2**30
else:
msb2= 2**62
BITS=[-msb2*2] # not converted into long
while msb2:
BITS.append(msb2)
msb2 >>= 1
def bitcount(n):
return sum(1 for b in BITS if b&n)
This should work for machine integers (depending on your OS and the Python version). It won't work for any long.
这应该适用于机器整数（取决于您的操作系统和 Python 版本）。它对任何long.
回答by ThomasH
How do you like this one:
你喜欢这个吗：
def bitsoncount(x):
b = 0
bit = 1
while bit <= x:
b += int(x & bit > 0)
bit = bit << 1
return b
Basically, you use a test bit that starts right and gets shifted all the way through up to the bit length of your in parameter. For each position the bit & x yields a single bit which is on, or none. Check > 0 and turn the resulting True|False into 1|0 with int(), and add this to the accumulator. Seems to work nicely for longs :-) .
基本上，您使用一个从正确开始的测试位，并一直移动到您的 in 参数的位长度。对于每个位置，位 & x 产生一个打开或没有的位。检查 > 0 并使用 int() 将结果 True|False 转换为 1|0，并将其添加到累加器中。似乎很适合长期 :-) 。
