Count Set Bits Brian Kernighan Algorithm in DSA C - 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 the rightmost 1 bit one by one. Instead of checking every bit, it jumps directly to the next 1 bit until none are left. This makes counting faster, especially for numbers with fewer 1s.

Why it matters

Without this algorithm, counting set bits would mean checking every bit one by one, which can be slow for large numbers. Brian Kernighan's method speeds up this process, saving time and computing power. This is important in many areas like cryptography, error detection, and graphics where bit operations happen often. Without it, programs would run slower and use more energy.

Where it fits

Before learning this, you should understand binary numbers and basic bitwise operations like AND and subtraction. After this, you can explore more advanced bit manipulation tricks and algorithms that use set bit counts, such as parity checks or fast multiplication methods.

Mental Model

Core Idea

Each step removes the rightmost 1 bit from the number, 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 1s. Each time you blow out the rightmost lit candle, you count one. You keep doing this until no candles are left lit.

Number in binary:  10110
Step 1: 10110 & (10110 - 1) = 10110 & 10101 = 10100
Step 2: 10100 & (10100 - 1) = 10100 & 10011 = 10000
Step 3: 10000 & (10000 - 1) = 10000 & 01111 = 00000
Count of steps = 3 (number of set bits)

Build-Up - 7 Steps

1

Foundation

Understanding Binary Numbers

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

Every number can be shown in base 2, called binary. Each digit is a bit, either 0 or 1. For example, decimal 6 is 110 in binary (4 + 2 + 0). Counting how many 1s are in this binary form is called counting set bits.

Result

You can write any number in binary and identify its set bits.

Understanding binary is essential because bitwise operations work directly on these 0s and 1s.

2

Foundation

Basics of Bitwise AND Operation

Concept: Learn how the AND operation compares bits and returns 1 only if both bits are 1.

Bitwise AND compares two binary numbers bit by bit. For example, 1101 & 1011 = 1001. Only positions where both bits are 1 remain 1; others become 0.

Result

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

Bitwise AND is the key tool to isolate or remove bits in binary numbers.

3

Intermediate

Subtracting One from a Binary Number

Concept: Understand what happens to a binary number when you subtract 1.

Subtracting 1 flips the rightmost 1 bit to 0 and changes all bits to the right of it from 0 to 1. For example, 10100 - 1 = 10011.

Result

You can predict how subtraction affects the binary pattern.

Knowing this helps understand how the algorithm removes the rightmost set bit.

4

Intermediate

Brian Kernighan's Bit Removal Trick

🤔Before reading on: do you think subtracting 1 from a number always clears the rightmost 1 bit or changes other bits instead? Commit to your answer.

Concept: Learn how n & (n-1) removes the rightmost set bit from n.

When you do n & (n-1), it clears the rightmost 1 bit in n. For example, 12 (1100) & 11 (1011) = 8 (1000). This is because subtracting 1 flips bits after the rightmost 1, and AND clears that bit.

Result

You can remove one set bit at a time efficiently.

Understanding this trick is the core of the algorithm's speed and elegance.

5

Intermediate

Counting Set Bits Using the Trick

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

Concept: Use a loop that repeatedly applies n = n & (n-1) and counts iterations.

Start with count = 0. While n is not zero, do n = n & (n-1) and increment count. When n becomes zero, count holds the number of set bits.

Result

You get the total count of 1 bits in the number.

This method skips zero bits, making it faster especially when few bits are set.

6

Advanced

Implementing Brian Kernighan Algorithm in C

🤔Before reading on: do you think the code will correctly count set bits for zero input? Commit to your answer.

Concept: Write a complete C function using the algorithm.

int countSetBits(unsigned int n) { int count = 0; while (n) { n = n & (n - 1); count++; } return count; } // Example usage: // unsigned int result = countSetBits(29); // 29 in binary is 11101, so result should be 4

Result

Calling countSetBits(29) returns 4.

Seeing the full code helps connect theory to practice and confirms the algorithm's correctness.

7

Expert

Performance and Edge Cases of the Algorithm

🤔Before reading on: do you think this algorithm always runs in constant time? Commit to your answer.

Concept: Analyze time complexity and behavior on special inputs like zero or max int.

The algorithm runs in O(k) time where k is the number of set bits, not total bits. For zero input, it returns 0 immediately. For numbers with many set bits, it approaches O(log n). This makes it efficient for sparse bit patterns.

Result

You understand when the algorithm is fastest and its limits.

Knowing complexity helps choose the right method for different scenarios and avoid surprises in performance.

Under the Hood

The algorithm exploits the binary subtraction property where subtracting 1 flips bits from right to left until the first 1 bit is cleared. By ANDing the original number with one less than itself, it clears the rightmost set bit in a single operation. This repeats until the number becomes zero, effectively counting how many 1 bits were present.

Why designed this way?

This method was designed to avoid checking every bit individually, which is slow for large numbers. It leverages simple bitwise operations that processors execute very fast. Alternatives like looping through all bits waste time on zero bits. Brian Kernighan's approach balances simplicity and speed, making it a classic in bit manipulation.

Start: n (binary number)
   │
   ▼
Subtract 1: n - 1 (flips bits after rightmost 1)
   │
   ▼
AND: n & (n - 1) (clears rightmost set bit)
   │
   ▼
Repeat until n == 0
   │
   ▼
Count increments each step

Myth Busters - 3 Common Misconceptions

Quick: Does n & (n-1) clear all set bits or just one? Commit to your answer.

Common Belief: n & (n-1) clears all set bits in the number at once.

Reality: It only clears the rightmost set bit, leaving others unchanged.

Why it matters: Believing it clears all bits leads to wrong code that misses counting multiple set bits.

Quick: Is this algorithm always faster than checking each bit? Commit to your answer.

Common Belief: Brian Kernighan's algorithm is always faster than checking every bit.

Reality: It is faster when the number has few set bits but can be similar or slower if many bits are set.

Why it matters: Assuming it's always faster can cause inefficient choices in some cases.

Quick: Does the algorithm work correctly for zero input? Commit to your answer.

Common Belief: The algorithm fails or loops infinitely when input is zero.

Reality: It returns zero immediately because the loop condition fails at start.

Why it matters: Misunderstanding this can cause unnecessary checks or bugs in edge cases.

Expert Zone

1

The algorithm's speed depends on the number of set bits, not total bits, making it ideal for sparse bit patterns.

2

Using unsigned integers avoids issues with sign bits and ensures predictable behavior.

3

Combining this method with lookup tables can optimize counting in fixed-size chunks for very large numbers.

When NOT to use

Avoid this algorithm when you need to count bits in fixed-width numbers very frequently; table lookup methods or hardware instructions (like POPCNT) are faster. Also, for dense bit patterns, simple bit-by-bit checking may be comparable.

Production Patterns

Used in network packet processing to quickly count flags, in cryptography for parity checks, and in graphics for mask operations. Often combined with hardware instructions or vectorized code for maximum speed.

Connections

Bitwise Operations

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

Mastering bitwise operations is essential to understand and implement this algorithm efficiently.

Population Count Instruction (POPCNT)

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

Knowing this algorithm helps appreciate what hardware instructions do under the hood.

Error Detection Codes

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

Understanding how to count bits efficiently improves the performance of communication and storage systems.

Common Pitfalls

#1 Using signed integers causing incorrect results for negative numbers.

Wrong approach:

int countSetBits(int n) {
int count = 0;
while (n) {
n = n & (n - 1);
count++;
}
return count;
}
// Called with n = -1

Correct approach:

unsigned int countSetBits(unsigned int n) {
int count = 0;
while (n) {
n = n & (n - 1);
count++;
}
return count;
}
// Called with n = (unsigned int)-1

Root cause:

Signed integers use two's complement and can cause infinite loops or wrong counts when negative.

#2 Trying to count bits by shifting and checking bits one by one instead of using the algorithm.

Wrong approach:

int countSetBits(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if (n & (1 << i)) count++;
}
return count;
}

Correct approach:

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

Root cause:

Not knowing the efficient bit removal trick leads to slower code.

#3 Not handling zero input correctly, assuming the loop runs at least once.

Wrong approach:

int countSetBits(int n) {
int count = 0;
do {
n = n & (n - 1);
count++;
} while (n);
return count;
}
// Called with n = 0

Correct approach:

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

Root cause:

Using do-while causes count to increment once even if input is zero.

Key Takeaways

Brian Kernighan's algorithm counts set bits by repeatedly clearing the rightmost 1 bit using n & (n-1).

This method is faster than checking every bit because it skips zero bits and only loops as many times as there are set bits.

Understanding binary subtraction and bitwise AND is essential to grasp how the algorithm works.

The algorithm works correctly for zero and positive numbers but should use unsigned integers to avoid issues with negatives.

Knowing this algorithm helps in many fields like cryptography, networking, and graphics where bit counting is common.