5 Best Ways to Find the Number of 1 bits in a Given Number in Python

Rate this post

πŸ’‘ Problem Formulation: When working with binary numbers in Python, a common task is to count the number of 1 bits, also known as set bits, in the binary representation of a number. For example, given the input number 13, which is 1101 in binary, the desired output would be 3 as there are three 1 bits in its binary representation.

Method 1: Loop and Bitwise AND

This method involves iterating over each bit of the number using a loop and applying a bitwise AND operation with 1 to check if the least significant bit is a set bit (1). The count is increased each time a set bit is found, and the number is right-shifted to process the next bit until all bits are checked.

Here’s an example:

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

print(count_set_bits(13))

Output: 3

This code snippet defines a function count_set_bits() that takes an integer as an input and returns the count of set bits. It loops through each bit, incrementing the count when it encounters a set bit by performing a bitwise AND with 1. The number is then right-shifted to move to the next bit.

Method 2: Built-in bin() and count() Functions

Python’s built-in bin() function returns the binary representation of a number as a string, which allows us to use the string method count() to count the occurrences of bit 1 directly within the string.

Here’s an example:

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

print(count_set_bits(13))

Output: 3

In this snippet, the function count_set_bits() uses bin() to convert the number to its binary string form and then applies the count() method to find the number of ‘1’s in that string.

Method 3: Bitwise Operations with Bit Masking

In this method, a mask is used starting with the value 1, which is bitwise ANDed with the number to check for a set bit. After each check, the mask is left-shifted to move to the next bit. This continues until the mask is greater than the number.

Here’s an example:

def count_set_bits(num):
    count = 0
    mask = 1
    while mask <= num:
        if num & mask:
            count += 1
        mask <<= 1
    return count

print(count_set_bits(13))

Output: 3

This piece of code creates a mask with a single set bit and iterates through all the bits of the number. If the current bit is set, the count is incremented. This method is particularly useful to understand how bitmasking works.

Method 4: Brian Kernighan’s Algorithm

Brian Kernighan’s Algorithm takes advantage of the principle that for any number ‘n’, doing a bitwise AND of ‘n’ and ‘n-1’ flips the least significant bit of ‘n’ to 0. We use this property to count set bits until the number becomes zero.

Here’s an example:

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

print(count_set_bits(13))

Output: 3

The count_set_bits() function in this snippet uses Kernighan’s Algorithm. It repeatedly subtracts 1 from the number and does a bitwise AND with itself. This operation turns off the rightmost set bit in each iteration, and the process is repeated until the number becomes zero.

Bonus One-Liner Method 5: Using format() and a List Comprehension

This concise one-liner method relies on converting the number to its binary representation with format(), which is then iterated over in a list comprehension to sum the number of ‘1’s.

Here’s an example:

count_set_bits = lambda num: sum(1 for bit in format(num, 'b') if bit == '1')

print(count_set_bits(13))

Output: 3

The code creates a lambda function that uses format(num, 'b') to convert the number into a binary string and then generates a list of 1s for each ‘1’ bit in the string. The built-in sum() function calculates the total count.

Summary/Discussion

  • Method 1: Loop and Bitwise AND. Easy to understand, directly examines each bit. Slightly slower due to the loop.
  • Method 2: Built-in bin() and count() Functions. Extremely concise and leverages Python’s robust standard library. Performance depends on string operations.
  • Method 3: Bitwise Operations with Bit Masking. Good for educational purposes on how bitwise operations work. More verbose compared to other methods.
  • Method 4: Brian Kernighan’s Algorithm. Efficient since it operates only on set bits. However, it might be less intuitive for beginners.
  • Method 5: Bonus One-Liner with format() and List Comprehension. Elegantly concise and Pythonic way to solve the problem in one line. Can be slightly less readable due to compactness.