Counting 1's in Binary Representation: From Basic Algorithms to O(1) Time Optimization

Overview of Counting 1's in Binary Representation

In computer science, counting the number of 1's in the binary representation of an integer is a classic problem, often referred to as Hamming Weight or Population Count. This problem has wide applications in data compression, error detection, cryptography, and more. For instance, in algorithms like parity checks and Bloom filters, quickly counting 1's is crucial.

Basic Algorithm: Bit-by-Bit Checking

The most straightforward method involves checking each bit one by one. By repeatedly right-shifting the number, the least significant bit (LSB) is examined, and the count of 1's is accumulated. This approach has a time complexity of O(log n), where n is the input value. While simple to implement, it is inefficient for large numbers or high-frequency calls.

unsigned int countSetBits(unsigned int n) {
    unsigned int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

The above code uses n & 1 to get the LSB; if it is 1, the count increments, and the number is right-shifted until it becomes 0. Although this can be considered O(1) for fixed bit lengths (e.g., 32 bits), it theoretically depends on the value's size.

Brian Kernighan's Algorithm: Efficiently Eliminating the Lowest Set Bit

Brian Kernighan's algorithm cleverly uses the n & (n-1) operation to remove the lowest set bit in each iteration, reducing the loop count to the actual number of 1's k, with a time complexity of O(k).

unsigned int countSetBits(int n) {
    unsigned int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

The core idea is that subtracting 1 from n flips the lowest set bit to 0 and all trailing 0's to 1; performing a bitwise AND with n clears that lowest set bit. For example, with n=9 (binary 1001), after the first operation n becomes 8 (1000), and after the second, n=0, giving a count of 2. This method significantly improves efficiency when the number of 1's is small.

O(1) Time Complexity Solution: Lookup Table Method

Given sufficient memory, a precomputed lookup table can achieve O(1) time complexity for counting 1's. The process involves building a 256-byte table that stores the count of 1's for each number from 0 to 255, then splitting a 32-bit integer into four 8-bit bytes, looking up each in the table, and summing the results.

int BitsSetTable256[256];

void initialize() {
    BitsSetTable256[0] = 0;
    for (int i = 0; i < 256; i++) {
        BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
    }
}

int countSetBits(int n) {
    return (BitsSetTable256[n & 0xff] +
            BitsSetTable256[(n >> 8) & 0xff] +
            BitsSetTable256[(n >> 16) & 0xff] +
            BitsSetTable256[n >> 24]);
}

The initialization function builds the table using the recurrence relation BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2], where i / 2 is equivalent to a right shift by one bit. The counting function extracts each byte using bit masks and shifts, then sums the looked-up values. Although this requires extra memory, it offers extremely fast queries, making it ideal for high-performance computing scenarios.

Comparison with Other Efficient Algorithms

Beyond the above methods, several optimized algorithms exist. For example, the divide-and-conquer bit manipulation approach progressively accumulates the count through multiple shifts and masks:

int count_one(int x) {
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

This algorithm uses magic number masks (e.g., 0x55555555 for 0101...) to group bits, gradually merging counts. The first step counts 1's in pairs of bits, the second in groups of four, and so on, ultimately yielding the total. It requires no extra memory and performs well on modern processors due to efficient bit operations.

Recursive and Library Function Implementations

The recursive method checks the LSB and right-shifts for recursive calls, offering concise code but with O(log n) space complexity:

int countSetBits(int n) {
    if (n == 0) return 0;
    return (n & 1) + countSetBits(n >> 1);
}

Many programming languages provide built-in functions, such as GCC's __builtin_popcount(), Java's Integer.bitCount(), and Python's bin(n).count('1'). These are typically highly optimized and recommended for production use.

Algorithm Selection and Performance Analysis

Choosing the right algorithm depends on the context:

• Bit-by-Bit Checking: Suitable for education or simple applications, with O(log n) time complexity.
• Brian Kernighan's Algorithm: Efficient when the number of 1's is much smaller than the total bits, with average time complexity O(k).
• Lookup Table Method: Optimal for O(1) time when memory is available, offering very fast queries after preprocessing.
• Divide-and-Conquer Bit Manipulation: No extra memory needed, constant-time operations, ideal for embedded or memory-constrained environments.

In practice, built-in functions are often the best choice unless specific optimizations are required. For example, in scenarios involving frequent calculations on large datasets, the lookup table method can significantly enhance performance.

Conclusion

Counting 1's in a binary number is a multi-faceted optimization problem. From basic O(log n) methods to efficient O(1) lookup tables, each algorithm has its strengths and weaknesses. Understanding these principles and implementations aids in selecting the optimal solution for specific contexts, improving program efficiency. As hardware evolves, such as CPUs with POPCOUNT instructions, this problem may simplify further, but mastering core algorithmic concepts remains fundamental to computer science.