Skip to main content

Counting Bits

Question​

How can I count the number of set bits in a given positive integer?

Example 1
Input:  num = 5
Output: [0,1,1,2,1,2]

Solution​

all//Counting Bits.py


def countBits(num):
    # Create an empty array to store the results
    result = [0]

    # Loop through all numbers from 1 to num (both inclusive)
    for i in range(1, num+1):
        # The result of current number is 1 plus
        # result of (number - 1)
        result.append(result[i >> 1] + (i & 1))

    # Return the result array
    return result

# Driver code
num = 8
print(countBits(num))