Count set bits in an integer | PHP 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
< ? php $ num_to_bits = array ( 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 ) ; function countSetBitsRec ( $ num ) { global $ num_to_bits ; $ nibble = 0 ; if ( 0 == $ num ) return $ num_to_bits [ 0 ] ; $ nibble = $ num & 0xf ; return $ num_to_bits [ $ nibble ] + countSetBitsRec ( $ num >> 4 ) ; } $ num = 31 ; echo ( countSetBitsRec ( $ num ) ) ; ? >