Python Program to Count Set Bits in Number

You can count set bits in a number in Python using bin(n).count('1') which converts the number to binary and counts the '1's.

Examples

Input0

Output0

Input13

Output3

Input255

Output8

How to Think About It

To count set bits, think of the number in binary form. Each '1' bit means a set bit. We can convert the number to a binary string and count how many '1's it has, or repeatedly check each bit by shifting and masking.

Algorithm

1

Get the input number.

2

Convert the number to binary or check bits one by one.

3

Count how many bits are set to 1.

4

Return the count.

Code

python

def count_set_bits(n):
    return bin(n).count('1')

# Example usage
num = 13
print(f"Number of set bits in {num}: {count_set_bits(num)}")

Output

Number of set bits in 13: 3

Dry Run

Let's trace the number 13 through the code to count set bits.

1

Convert to binary

bin(13) returns '0b1101'

2

Count '1's

The string '1101' has three '1's

3

Return count

Return 3 as the number of set bits

Step	Binary String	Count of '1's
1	0b1101	3

Why This Works

Step 1: Binary Conversion

The bin() function converts the number to a binary string starting with '0b'.

Step 2: Counting Set Bits

Counting the '1' characters in the binary string gives the number of set bits.

Step 3: Return Result

The count is returned as the total number of bits set to 1 in the number.

Alternative Approaches

Bitwise Loop

python

def count_set_bits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

print(count_set_bits(13))

This method uses bitwise operations and loops through each bit, which is efficient and does not convert to string.

Brian Kernighan's Algorithm

python

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

print(count_set_bits(13))

This method repeatedly clears the lowest set bit, making it faster for numbers with few set bits.

Complexity: O(k) time, O(1) space

Time Complexity

Counting set bits takes O(k) time where k is the number of bits in the number, as each bit is checked or counted.

Space Complexity

The space used is O(1) because counting bits uses a fixed amount of memory regardless of input size.

Which Approach is Fastest?

Brian Kernighan's algorithm is fastest for sparse bits, while bin().count('1') is simplest and fast enough for most uses.

Approach	Time	Space	Best For
bin().count('1')	O(k)	O(1)	Simplicity and readability
Bitwise Loop	O(k)	O(1)	General use, no string conversion
Brian Kernighan's Algorithm	O(m)	O(1)	Numbers with few set bits (m = set bits count)