python pop count

popcnt.py

#!/bin/env python
""" :mod: popcnt
    ============
 
    .. module: popcnt
    :synopsis: couting bits set ("1") in int or long
    .. moduleauthor:: Krzysztof.Ciba@NOSPAMgmail.com    
"""
## bit count look up table in range 0..255
__bcLUT = [ 0 ] * 256
for i in range(256):
  __bcLUT[i] = ( i & 1 ) + __bcLUT[i/2]

def popcntLUT( arg ):
  """ popcnt using look up table """
  assert type(arg) in ( int, long )
  e = lambda x, y: x + int( bool( y ) ) << 3
  return sum( [ __bcLUT[ ( arg >> i ) & 255 ] 
                for i in range( 0, e( *divmod( arg.bit_length(), 8) ), 8 ) ] )

def popcntBK( arg ):
  """ Brian Kernighan way - loop only for bits set """
  assert type(arg) in ( int, long )
  pop = 0
  while arg:
    arg &= arg - 1
    pop += 1
  return pop

def popcntNaive( arg ):
  """ naive - loop for every bit in arg """
  assert type(arg) in ( int, long )
  pop = 0
  while arg:
    pop += arg & 1
    arg >>= 1
  return pop

def popcntUgly( arg ):
  """ ugly but pythonic way? """
  assert type(arg) in ( int, long ) 
  return bin(arg).count("1")
 

# # eep!
if __name__ == "__main__":
  # dummy testing
  for i in range(1024):
    ugly = popcntUgly(i)
    lut = popcntLUT(i)
    bk = popcntBK(i)
    naive = popcntNaive(i)
    assert ugly == lut
    assert ugly == bk
    assert ugly == naive