Number of 1 Bits

• There are six ways to solve this problem.

Intuition

Using lookup table this can be done in O(1)

Code

BitsSetTable256 = [0] * 256
 
# Function to initialise the lookup table
def initialize():
     
    # To initially generate the
    # table algorithmically
    BitsSetTable256[0] = 0
    for i in range(256):
        BitsSetTable256[i] = (i & 1) + BitsSetTable256[i // 2]
 
# Function to return the count
# of set bits in n
def countSetBits(n):
    return (BitsSetTable256[n & 0xff] +
            BitsSetTable256[(n >> 8) & 0xff] +
            BitsSetTable256[(n >> 16) & 0xff] +
            BitsSetTable256[n >> 24])
 
# Driver code
 
# Initialise the lookup table
initialize()
n = 9
print(countSetBits(n))

Approach 2 Code

In GCC, we can directly count set bits using __builtin_popcount(). So we can avoid a separate function for counting set bits.

print(bin(4).count('1'));
print(bin(15).count('1'));