Python Program to Count Set Bits in an Integer

This is a Python program to count set bits in a number.

Problem Description

The program finds the number of ones in the binary representation of a number.

Problem Solution

1. Create a function count_set_bits that takes a number n as argument.
2. The function works by performing bitwise AND of n with n – 1 and storing the result in n until n becomes 0.
3. Performing bitwise AND with n – 1 has the effect of clearing the rightmost set bit of n.
4. Thus the number of operations required to make n zero is the number of set bits in n.

Program/Source Code

Here is the source code of a Python program count set bits in a number. The program output is shown below.

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count
 
 
n = int(input('Enter n: '))
print('Number of set bits:', count_set_bits(n))
Program Explanation

1. The user is asked to input n.
2. The number of set bits is found by calling count_set_bits on n.

advertisement
advertisement
Runtime Test Cases
Case 1:
Enter n: 9
Number of set bits: 2
 
Case 2:
Enter n: 31
Number of set bits: 5
 
Case 3:
Enter n: 1
Number of set bits: 1

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.