Count set bits in an integer | Python3 program to count set bits by pre - storing count set bits in nibbles . ; Recursively get nibble of a given number and map them in the array ; Find last nibble ; Use pre - stored values to find count in last nibble plus recursively add remaining nibbles . ; Driver code
num_to_bits = [ 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 ] ; NEW_LINE def countSetBitsRec ( num ) : NEW_LINE INDENT nibble = 0 ; NEW_LINE if ( 0 == num ) : NEW_LINE INDENT return num_to_bits [ 0 ] ; NEW_LINE DEDENT nibble = num & 0xf ; NEW_LINE return num_to_bits [ nibble ] + countSetBitsRec ( num >> 4 ) ; NEW_LINE DEDENT num = 31 ; NEW_LINE print ( countSetBitsRec ( num ) ) ; NEW_LINE