Count Set Bits Brian Kernighan Algorithm in DSA Python - Deep Dive

Overview - Count Set Bits Brian Kernighan Algorithm

What is it?

Counting set bits means finding how many 1s are in the binary form of a number. The Brian Kernighan algorithm is a smart way to do this quickly by removing one set bit at a time. Instead of checking every bit, it jumps directly to the next set bit until none are left. This makes counting faster, especially for large numbers.

Why it matters

Without an efficient way to count set bits, programs that rely on bit operations would run slower and waste resources. This algorithm helps in tasks like error detection, cryptography, and graphics where bit manipulation is common. It makes software faster and more efficient, which is important in real-world applications like video games or network security.

Where it fits

Before learning this, you should understand binary numbers and basic bitwise operations like AND and subtraction. After mastering this, you can explore other bit manipulation tricks and algorithms that optimize performance in low-level programming and competitive coding.

Mental Model

Core Idea

Each step of the Brian Kernighan algorithm removes the rightmost set bit, counting how many times this can be done until the number becomes zero.

Think of it like...

Imagine you have a row of lit candles representing set bits. Each time you blow out the rightmost lit candle, you count one. You keep doing this until all candles are out, and the count tells you how many candles were lit.

Number (binary):  0b10110 (22 decimal)
Step 1: 22 & (22-1) = 22 & 21 = 0b10110 & 0b10101 = 0b10100 (20 decimal)
Step 2: 20 & (20-1) = 20 & 19 = 0b10100 & 0b10011 = 0b10000 (16 decimal)
Step 3: 16 & (16-1) = 16 & 15 = 0b10000 & 0b01111 = 0b00000 (0 decimal)
Count of steps = 3 set bits

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn how numbers are represented in binary using 0s and 1s.

Every number can be written in base 2, called binary. For example, decimal 5 is 101 in binary, which means 1*4 + 0*2 + 1*1. Each digit is called a bit. Set bits are bits with value 1.

Result

You can convert any decimal number to binary and identify which bits are set (1) or unset (0).

Understanding binary is essential because bitwise operations work directly on these bits, not on decimal numbers.

2

Foundation

Basics of Bitwise AND Operation

Concept: Learn how the AND operation compares bits of two numbers.

Bitwise AND compares each bit of two numbers and returns 1 only if both bits are 1. For example, 6 (110) & 3 (011) = 2 (010). This operation helps isolate bits.

Result

You can use AND to check or clear specific bits in a number.

Bitwise AND is the key tool that Brian Kernighan's algorithm uses to remove set bits efficiently.

3

Intermediate

Naive Set Bit Counting Method

Concept: Count set bits by checking each bit one by one.

Start from the rightmost bit and check if it is 1 by ANDing with 1. Shift the number right by one bit and repeat until the number is zero. Count how many times you find a 1.

Result

For number 13 (1101), the count is 3 set bits.

This method works but can be slow for large numbers because it checks every bit, even zeros.

4

Intermediate

Brian Kernighan Algorithm Introduction

🤔Before reading on: do you think removing one set bit at a time is faster than checking every bit? Commit to your answer.

Concept: Instead of checking each bit, repeatedly remove the rightmost set bit until the number becomes zero.

The trick is to do n = n & (n-1). This operation removes the rightmost set bit. Count how many times you do this until n is zero.

Result

For 13 (1101), steps: 1101 & 1100 = 1100, 1100 & 1011 = 1000, 1000 & 0111 = 0000. Count = 3.

Removing set bits directly reduces the number of operations to the number of set bits, making it faster for numbers with few set bits.

5

Advanced

Implementing Brian Kernighan Algorithm in Python

🤔Before reading on: do you think the loop will run as many times as the number of bits or the number of set bits? Commit to your answer.

Concept: Write a Python function that counts set bits using the Brian Kernighan method.

def count_set_bits(n: int) -> int: count = 0 while n: n &= n - 1 # Remove rightmost set bit count += 1 return count Example: count_set_bits(22) returns 3.

Result

Output for input 22 is 3, matching the number of set bits in binary 10110.

This implementation is concise and efficient, showing how a simple loop with bitwise operations can outperform naive methods.

6

Expert

Performance and Use Cases of Brian Kernighan Algorithm

🤔Before reading on: do you think this algorithm is always the fastest way to count set bits? Commit to your answer.

Concept: Understand when this algorithm shines and when other methods might be better.

Brian Kernighan's algorithm runs in O(k) time, where k is the number of set bits. For sparse numbers, it's very fast. For dense numbers, lookup tables or hardware instructions might be faster. It's widely used in embedded systems and competitive programming.

Result

Knowing the algorithm's complexity helps choose the right method for the problem.

Understanding the algorithm's time depends on set bits, not total bits, reveals why it is efficient and when to consider alternatives.

Under the Hood

The key operation n = n & (n-1) works by flipping the rightmost set bit to zero. This happens because subtracting 1 from n flips all bits after the rightmost set bit, including that bit itself, and ANDing with n clears that bit. Repeating this removes one set bit each time until none remain.

Why designed this way?

This method was designed to avoid checking every bit individually, which is slow. It leverages binary arithmetic properties to jump directly to set bits. Alternatives like looping over all bits or using lookup tables exist but may be less efficient or require extra memory.

n (binary):    10110
n-1 (binary):  10101
AND result:    10100  (rightmost set bit cleared)

Repeat until n = 0:

┌───────────────┐
│ Start with n  │
│ 10110 (22)    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Compute n-1   │
│ 10101 (21)    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ n = n & (n-1) │
│ 10100 (20)    │
└──────┬────────┘
       │
       ▼
Repeat until n=0

Myth Busters - 3 Common Misconceptions

Quick: Does Brian Kernighan's algorithm check every bit of the number? Commit yes or no.

Common Belief: It checks every bit one by one like the naive method.

Reality: It only runs as many times as there are set bits, skipping zeros entirely.

Why it matters: Believing it checks every bit leads to underestimating its efficiency and missing opportunities to optimize code.

Quick: Is the operation n & (n-1) the same as subtracting 1 from n? Commit yes or no.

Common Belief: n & (n-1) just subtracts 1 from n.

Reality: It removes the rightmost set bit but is not the same as subtracting 1; it uses subtraction as part of the process.

Why it matters: Confusing these operations can cause bugs when manipulating bits or misunderstanding how the algorithm works.

Quick: Does this algorithm always run faster than using built-in functions or lookup tables? Commit yes or no.

Common Belief: Brian Kernighan's algorithm is always the fastest way to count set bits.

Reality: Hardware instructions or lookup tables can be faster for dense numbers or specific platforms.

Why it matters: Assuming it is always fastest may lead to suboptimal performance in some real-world applications.

Expert Zone

1

The algorithm's runtime depends on the number of set bits, not the total bit length, making it especially efficient for sparse bit patterns.

2

In some CPUs, hardware instructions like POPCNT can count bits faster, but Brian Kernighan's method is portable and requires no extra memory.

3

Combining this algorithm with memoization or lookup tables can optimize counting in bulk operations or repeated calls.

When NOT to use

Avoid this algorithm when working with very dense bit patterns or when hardware support for bit counting exists. In such cases, use CPU instructions like POPCNT or precomputed lookup tables for faster results.

Production Patterns

Used in embedded systems for low-memory environments, competitive programming for fast bit counting, and cryptographic algorithms where bit manipulation speed is critical.

Connections

Bitwise Operations

Brian Kernighan's algorithm builds directly on bitwise AND and subtraction operations.

Mastering bitwise operations is essential to understand and implement efficient bit manipulation algorithms like this one.

Population Count Instruction (POPCNT)

POPCNT is a hardware instruction that performs the same task as Brian Kernighan's algorithm but faster.

Knowing this helps understand the tradeoff between software algorithms and hardware acceleration.

Error Detection in Communication Systems

Counting set bits is used in parity checks and error detection codes.

Understanding this algorithm helps grasp how digital systems detect errors by counting bits efficiently.

Common Pitfalls

#1 Using a loop that checks every bit instead of removing set bits.

Wrong approach:

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

Correct approach:

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

Root cause:

Misunderstanding that checking each bit is necessary instead of removing set bits directly.

#2 Confusing n & (n-1) with n - 1 alone.

Wrong approach:

def count_set_bits(n):
count = 0
while n:
n = n - 1 # Wrong: does not remove rightmost set bit correctly
count += 1
return count

Correct approach:

def count_set_bits(n):
count = 0
while n:
n &= n - 1 # Correct: removes rightmost set bit
count += 1
return count

Root cause:

Not understanding the bitwise AND operation's role in clearing the rightmost set bit.

Key Takeaways

Counting set bits efficiently is important for performance in many computing tasks.

Brian Kernighan's algorithm removes one set bit at a time using n = n & (n-1), making it faster than checking every bit.

The algorithm's speed depends on the number of set bits, not the total number of bits.

Understanding bitwise operations is crucial to grasp how this algorithm works.

While efficient, this algorithm may not always be the fastest option on hardware with specialized instructions.