Why Count Set Bits Brian Kernighan Algorithm in DSA C?

The Big Idea

What if you could count only the important bits and skip the rest, saving time and effort?

The Scenario

Imagine you have a long list of numbers, and you want to know how many bits are set to 1 in each number. Doing this by checking every bit one by one feels like counting every grain of sand on a beach by hand.

The Problem

Checking each bit manually means going through all bits even if most are zero. This is slow and wastes time, especially for big numbers. It's easy to make mistakes counting so many bits one by one.

The Solution

The Brian Kernighan Algorithm quickly jumps from one set bit to the next by turning off the rightmost set bit each time. This way, it only counts the bits that are 1, skipping all zeros, making the process much faster and less error-prone.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This algorithm enables fast and efficient counting of set bits, which is essential in tasks like error detection, cryptography, and network data processing.

Real Life Example

In networking, counting set bits helps quickly find how many devices are active in a network mask, improving speed and accuracy in managing connections.

Key Takeaways

Manual bit counting is slow and error-prone.

Brian Kernighan's method skips zeros and counts only set bits.

This makes counting bits faster and more efficient.