🔢 Bitcount in C: Counting Set Bits Efficiently

Table of contents

📖 Introduction

In this blog post, we explore how to count the number of set bits (1s) in an integer in C based on the method described by K&R (The C Programming Language by Brian Kernighan and Dennis Ritchie). We will compare two approaches:

1. A simple method that shifts and checks each bit sequentially.
2. A faster method using K&R’s bitwise trick x & (x - 1).

🚶 1. The Simple Method: Bit-by-Bit Shift

This approach is straightforward: it inspects each bit one by one starting from the least significant bit (LSB - rightmost bit) and shifts the number to the right until all bits are processed.

Algorithm Steps

• Initialize count to 0.
• While the integer is not zero:
  • Check if the rightmost bit is 1 using i & 01.
  • If set, increment count.
  • Shift the integer right by 1 bit (i >>= 1).
• Return count.

Implementation

int bitcount_simple(unsigned int i) {
    int count = 0;

    for (; i != 0; i >>= 1) {
        if (i & 01) {
            count++;
        }
    }
    return count;
}

Time Complexity: Proportional to the position of the most significant (Leftmost) 1-bit (O(total bits)) in the worst case.

⚡ 2. The Faster Method: K&R’s Bitwise Trick

Instead of shifting through every bit position, we can use a clever bitwise trick that clears the rightmost set bit (1) in each iteration:

x = x & (x - 1);

🔍 Why Does x & (x - 1) work?

In binary two’s complement arithmetic, subtracting 1 from x (x - 1):

• the rightmost 1 bit in x becomes 0
• the bits after the rightmost 1 bit become 1s
• the bits before the rightmost 1 bit remain unchanged because the carry generated there propagates to higher bits which remain bits unchanged.

When we perform x & (x - 1):

• The unchanged higher bits remain identical.
• The rightmost 1 (which became 0 in x - 1) ANDed with 1 in x becomes 0.
• The trailing 0s ANDed with 1s remain 0.

Hence, each operation x & (x - 1) clears exactly one set bit—the lowest-order 1.

📊 Step-by-Step Example

Let’s trace x = 196:

  x             = 196   ->  11000100  (binary)
  -1            = 255   ->  11111111  (binary) // two's complement representation of -1
  -----------------------------------------
  x + (-1)      = 195   ->  11000011  (binary)
    // rightmost 1 bit (3rd bit from the right)
    // all bits after the rightmost 1 bit (2nd and 1st bits from the right) become 1s
    // all bits before the rightmost 1 bit (4th, 5th, 6th, and 7th bits from the right) remain unchanged
  -----------------------------------------

  
  x              = 196  ->  11000100  (binary)
  x - 1          = 195  ->  11000011  (binary) // as explained above
  --------------------------------------------
  x & (x-1)      = 192  ->  11000000  (rightmost 1-bit - 3rd bit from the right cleared!)
  --------------------------------------------

💻 Implementation

By repeating this trick until x becomes 0, the loop executes only as many times as there are 1s:

int bitcount_faster(unsigned int x) {
    int count = 0;

    while(x != 0){
        x = x & (x - 1);
        count++;
    }
    return count;
}

⚖️ Performance Comparison

🏁 Conclusion

K&R’s algorithm x & (x - 1) is an elegant bitwise technique that skips zero-bits entirely. It reduces execution time, making it the preferred method for counting set bits.