How to count the number of set bits in a 32-bit integer?

How to Count the Number of Set Bits in a 32-bit Integer

Counting the number of set bits (also known as 1s or "Hamming weight") in a 32-bit integer is a common bit manipulation task. Here are several methods to accomplish this in an efficient manner:

Method 1: Brian Kernighan’s Algorithm

Brian Kernighan’s algorithm is an efficient way to count the number of set bits. It works by repeatedly turning off the rightmost set bit.

Explanation

• Subtracting 1 from a number flips all the bits after the rightmost set bit, including the rightmost set bit itself.
• Performing a bitwise AND between the number and the number minus one results in turning off the rightmost set bit.
• Repeat this process until the number becomes zero.

Implementation in Python

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

# Example usage
number = 29  # Binary: 11101
print(count_set_bits(number))  # Output: 4

Method 2: Lookup Table Method

This method precomputes the number of set bits for all possible byte values (0 to 255) and uses this table to count the bits in a 32-bit integer.

Explanation

• Divide the 32-bit integer into 4 bytes.
• Use the precomputed table to find the number of set bits in each byte.
• Sum the counts for all four bytes.

Implementation in Python

# Precompute the number of set bits for each byte value (0 to 255)
lookup_table = [bin(i).count('1') for i in range(256)]

def count_set_bits(n):
    count = (lookup_table[n & 0xff] +
             lookup_table[(n >> 8) & 0xff] +
             lookup_table[(n >> 16) & 0xff] +
             lookup_table[(n >> 24) & 0xff])
    return count

# Example usage
number = 29  # Binary: 11101
print(count_set_bits(number))  # Output: 4

Method 3: Bitwise Manipulation with a Simple Loop

This method uses a loop to count the set bits by checking each bit one by one.

Explanation

• Use a loop to iterate through each bit of the integer.
• Check if the least significant bit (LSB) is set using n & 1.
• Right shift the integer to check the next bit.
• Count the number of set bits.

Implementation in Python

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

# Example usage
number = 29  # Binary: 11101
print(count_set_bits(number))  # Output: 4

Method 4: Using Built-in Functions

Most modern programming languages have built-in functions to count the number of set bits. In Python, you can use bin() and count() methods.

Implementation in Python

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

# Example usage
number = 29  # Binary: 11101
print(count_set_bits(number))  # Output: 4

Summary

• Brian Kernighan’s Algorithm: Efficiently counts set bits by turning off the rightmost set bit iteratively.
• Lookup Table Method: Uses precomputed values for bytes to quickly sum the number of set bits.
• Simple Loop with Bitwise Manipulation: Iterates through each bit and checks if it is set.
• Built-in Functions: Utilizes language-specific built-in methods for simplicity and efficiency.

Each method has its own advantages, and the choice depends on the specific requirements and constraints of your application. For more in-depth knowledge and practical examples on programming concepts, consider exploring Grokking the Coding Interview on DesignGurus.io, which provides comprehensive courses on essential coding and interview techniques.