Python: number of bit sets (popcount)

Question

In my database (oracle 11g), several blob that duplicated XOR operations on blob using UTL_RAW.BIT_XOR were duplicated. After that, I wanted to count the number of bits in a binary string, so I wrote the code above.

During a small experiment, I wanted to see what a hexadecimal and integer value is, and I 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 difference between the hexadecimal code and the resulting integer value, so the following python code was used to check the actual integer value.

 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 of multiple bits, I wrote the following code in 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, sorry if I'm wrong.

 def bitsoncount(x): b=0; if(x>1): b=1; while(x &= (x-1)): 

I get an error on the last line, you need help resolving this and implementing logic in python :-)

I was interested in checking the version of the bit set in python after what I saw!

Thanks Chaitanya

Related question: Best algorithm for counting the number of bits in a 32-bit integer?

Answer 1

Python 2.6 or 3.0:

 def bitsoncount(x): return bin(x).count('1') 

Example:

 >>> x = 123 >>> bin(x) '0b1111011' >>> bitsoncount(x) 6 

Or

Matt Howells answer in 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 

Answer 2

what you are looking for is called a Hamming weight .

in python 2.6 / 3.0 it can be easily found with:

 bits = sum( b == '1' for b in bin(x)[2:] ) 

Answer 3

What version of Python are you using? First, Python uses a space, not a semicolon, so for starters it should look something like this:

  def bitsoncount(x): b=0 while(x > 0): x &= x - 1 b+=1 return b 

Answer 4

A direct translation of your C algorithm is as follows:

 def bitsoncount(x): b = 0 while x > 0: x &= x - 1 b += 1 return b 

Answer 5

Perhaps 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 you can also do this simply in Python 3.0:

 def bits_on_count(x): return sum(c=='1' for c in bin(x)) 

This exploits the fact that bin (x) gives a binary representation of x.

Answer 6

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 integers (depending on your OS and Python version). It will not work for any long .

Answer 7

How do you like this:

 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 to the right and shifts completely to the bit length of your parameter. For each position, bits and x give one bit that is on or not. Check> 0 and rotate the resulting True | False in 1 | 0 using int () and add this to the battery. Seems to work well for a long time :-).