Why Count Set Bits Brian Kernighan Algorithm in DSA Python?

The Big Idea

Discover how a simple trick can make counting bits lightning fast!

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 is slow and boring. It wastes time because you look at bits that are zero and don't add to the count. This makes the process long and error-prone, especially for big numbers.

The Solution

The Brian Kernighan Algorithm smartly skips all the zero bits and jumps directly from one set bit to the next. It uses a simple trick to remove the rightmost set bit in each step, making counting very fast and neat.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This algorithm lets you count set bits quickly and efficiently, even in very large numbers, saving time and effort.

Real Life Example

In networking, counting set bits helps find how many devices are active in a network mask or how many features are enabled in a settings flag.

Key Takeaways

Manual bit counting checks every bit, which is slow.

Brian Kernighan's method removes one set bit at a time, speeding up counting.

This makes bit counting efficient and practical for big numbers.