Count total number of set bits using Python

In this tutorial, we will find the total number of set bits present in an integer with Python program. This question will show the importance of the Bit Manipulation concept.

What are Set Bits?

Sets Bits is represented by 1’s in the binary form of a number.

So basically, we have to find the total number of 1’s present in the binary representation of a number.

Problem Statement

Given a number A. Return the total number of sets bits present in the binary representation of number A.

NOTE: 1 <= A <= 10^9.

EXAMPLE: –

INPUT: A = 5

OUTPUT: 2

EXPLANATION:

Since 101 is the binary form of 5 . And the total number of 1’s present in the 101 are 2.So the total number of set bits is 2.

Approach (1)

So, the first approach for this problem to solve is quite straightforward.

Convert the given decimal number into a binary number and then count the total number of 1’s present in the binary form of the converted number. But this is not an efficient way to solve this problem.

The time complexity will be linear in this case but we can make this approach more efficient.

Approach (2)

So, in this approach, we will see one of the concepts of Bit Manipulation. By using this concept we are able to make our code and approach more efficient.

So coming on the concept:

For any number A(A>0), we will do AND of A with A-1. We will repeat this work till A not equal to 0(zero). And we will keep the count of repetition and that count is the count of a total number of set bits present in the number given N.

So we will use a loop and the loop will work till A not equal to 0(zero). And inside the loop, we will do AND of A with A-1 and also increment the count value by 1.

Time for implementation using Python Language.

CODE

def countsetbits(A):
    count = 0         # initializing count with 0 value 
    while(A!=0):
        A = A & (A-1)    # ANDing of A with A-1
        count = count+1   # incrementing the count value
    return(count)       

print(countsetbits(8))
print(countsetbits(1))
print(countsetbits(2))
print(countsetbits(76869))
print(countsetbits(5))

OUTPUT

So, This is the basic concept of Bits Manipulation.

Do comment if you like this lesson and also do comment for any suggestion related to this tutorial.

Also, refer to these links for amazing concepts related to the Data Structure and Algorithm problem: