Tuesday, September 04, 2007

Count the number of on bits in a 32 bit integer

#Count the number of on bits in in a 32bit integer
#

def bin2int(s):
    return sum(int(n)*2**i for i, n in zip(range(len(s)), s[::-1]))

def bitcount1(n):
    total = 0
    for i in range(32):
        total+=n&1
        n>>=1

masks = [(1,  '01010101010101010101010101010101'),
         (2,  '00110011001100110011001100110011'),
         (4,  '00001111000011110000111100001111'),
         (8,  '00000000111111110000000011111111'),
         (16'00000000000000001111111111111111')]

masks = [(shift, bin2int(mask)) for shift, mask in masks] 

def bitcount2(n):
    for shift, mask in masks:
        n = (n & mask) + (n>>shift & mask)
    return n

def bitcount3(n):
    mask = bin2int('00010001000100010001000100010001')
    total = 0
    for i in range(4):
        total+=(((n>>i&mask)*mask) >> 28)& 0xf
    return total
    
    
    

1 Comments:

At 2:46 AM, Anonymous Anonymous said...

ever heard of:

>>> int('00010001000100010001000100010001',2)
286331153

 

Post a Comment

<< Home