Count set bits in an integer | Lookup table ; Function to initialise the lookup table ; To initially generate the table algorithmically ; Function to return the count of set bits in n ; Initialise the lookup table
BitsSetTable256 = [ 0 ] * 256 NEW_LINE def initialize ( ) : NEW_LINE INDENT BitsSetTable256 [ 0 ] = 0 NEW_LINE for i in range ( 256 ) : NEW_LINE INDENT BitsSetTable256 [ i ] = ( i & 1 ) + BitsSetTable256 [ i // 2 ] NEW_LINE DEDENT DEDENT def countSetBits ( n ) : NEW_LINE INDENT return ( BitsSetTable256 [ n & 0xff ] + BitsSetTable256 [ ( n >> 8 ) & 0xff ] + BitsSetTable256 [ ( n >> 16 ) & 0xff ] + BitsSetTable256 [ n >> 24 ] ) NEW_LINE DEDENT initialize ( ) NEW_LINE n = 9 NEW_LINE print ( countSetBits ( n ) ) NEW_LINE