Count Set Bits (Brian Kernighan's) 🎯

Welcome to a comprehensive guide on counting set bits using Brian Kernighan's method! This tutorial is designed to help both beginners and intermediate learners understand the concept from scratch. Let's dive in!

What are Set Bits? 📝

In computer science, a set bit refers to a 1 in a binary number. For example, in the binary representation of the decimal number 13 (1101), there are three set bits (1s).

Why Count Set Bits? 💡

Counting set bits is a fundamental operation in computer science, with applications in various areas such as data compression, graphics, and cryptography. It can help optimize algorithms and improve efficiency.

Introduction to Brian Kernighan's Method 📝

Brian Kernighan's method is a simple and efficient way to count the number of set bits in an integer. It's named after Brian Kernighan, a renowned computer scientist and author.

The Code - C Version ✅

Here's a simple C program that counts the number of set bits in an integer using Brian Kernighan's method:

#include <stdio.h>

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

int main() {
    int num = 13; // binary: 1101
    printf("Number of set bits in %d: %d\n", num, countSetBits(num));
    return 0;
}

💡 Pro Tip: This code works by repeatedly ANDing the number with (num - 1), which removes the rightmost set bit each time and increments the count of set bits.

The Code - Python Version ✅

Here's the equivalent Python code for counting set bits using Brian Kernighan's method:

python

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

num = 13  # binary: 1101
print(f"Number of set bits in {num}: {count_set_bits(num)}")

Practical Applications 💡

Counting set bits can be useful in various practical applications, such as:

Compression algorithms like Run-Length Encoding (RLE)
Detecting prime numbers
Generating random numbers
Image processing algorithms

Quiz Time 🎯

That's all for today! By understanding and applying Brian Kernighan's method, you're well on your way to mastering data structures and algorithms. Stay tuned for more lessons on CodeYourCraft! 🎉