Count the number of set bits in a 32-bit integer

bit manipulation

set bits count

programming tutorial

32-bit integer

algorithm optimization

Count the number of set bits in a 32-bit integer

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

In computer science, the concept of counting the number of set bits, also known as the Hamming weight or population count, in a binary representation of a number is a fundamental operation with applications in various algorithms, data structures, and error-checking codes. For a 32-bit integer, this involves determining how many of those 32 bits are '1'.

Understanding Binary Representation

Every integer is stored in memory as a binary number. In a 32-bit integer, each of the 32 bits can independently be a 0 or a 1, allowing integers from $0$ to $2^{32}-1$ to be represented. For example, the integer 13 is represented in binary as 0000 0000 0000 0000 0000 0000 0000 1101, and it contains three set bits (1s).

Methods to Count Set Bits

1. Iterative Method

The simplest approach is to iteratively check each bit:

python

1def count_set_bits_iterative(n):
2    count = 0
3    while n:
4        count += n & 1
5        n >>= 1
6    return count

Explanation:

n & 1 checks if the least significant bit is set.
n >>= 1 shifts the number right by one bit, effectively dividing it by two.
This loop continues until all bits are shifted out (i.e., n becomes zero).

2. Brian Kernighan’s Algorithm

A more efficient approach involves clearing the least significant set bit one at a time:

python

1def count_set_bits_kernighan(n):
2    count = 0
3    while n:
4        n &= (n - 1)
5        count += 1
6    return count

Explanation:

n & (n - 1) clears the least significant set bit.
This reduces the number of iterations to the number of set bits, making it more efficient for sparse bitfields.

3. Bit Manipulation Using Built-in Functions

Many modern programming languages provide built-in functions:

python

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

Explanation:

bin(n) converts the number to its binary representation as a string.
Then, count('1') simply counts the number of 1s in the string.

4. Lookup Tables

Precomputing results for smaller numbers and using these can speed up the process for integers:

python

1# Precomputed table for 8-bit integers
2lookup_table = [bin(i).count('1') for i in range(256)]
3
4def count_set_bits_lookup(n):
5    count = (lookup_table[n & 0xff] +
6             lookup_table[(n >> 8) & 0xff] +
7             lookup_table[(n >> 16) & 0xff] +
8             lookup_table[(n >> 24) & 0xff])
9    return count

Explanation:

n & 0xff extracts the least significant byte of n.
Each chunk of 8 bits is processed via a lookup in the precomputed table.

Applications

Data Compression: Knowing the number of set bits helps in some forms of data encoding and compression where memory is a constraint.
Cryptography: Sometimes used in cryptographic algorithms to determine parity.
Parity Checking & Error Detection: Detects errors in data transmission or storage.

Summary of Methods

Method	Complexity	Efficiency in Practice
Iterative	$O(b)$	Reasonable for all cases
Brian Kernighan’s	$O(k)$	Fast for sparse data
Built-in Function	$O(b)$	Language-dependent
Lookup Table	$O(1)$ per lookup total $O(b/t)$	Fast with precomputation

$b$ = Number of bits (e.g., 32 for a 32-bit integer).
$k$ = Number of set bits.
t = Chunk size (e.g., 8 for byte-level).

In conclusion, counting set bits is a versatile operation with multiple implementations, each suited for different scenarios based on performance requirements and constraints. Understanding these methods empowers developers to select the best approach for their specific use cases.