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 clever way to count these 1s quickly. Instead of checking every bit, it jumps from one set bit to the next. This makes it faster than simple methods, especially for large numbers.

Why it matters

Counting set bits is important in many areas like computer graphics, networking, and cryptography. Without efficient methods like Brian Kernighan's, programs would run slower when dealing with bit operations. This algorithm helps computers make decisions faster and saves energy by doing less work.

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 optimization techniques in algorithms.

Mental Model

Core Idea

Each time you remove the rightmost set bit from a number, you get closer to zero, and counting how many times you do this tells you how many set bits there were.

Think of it like...

Imagine you have a row of lit candles (1s) and unlit candles (0s). Instead of checking each candle, you blow out the rightmost lit candle one by one, counting how many you blow out until none are left.

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

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn what binary numbers are and how they represent values using 0s and 1s.

Binary numbers use only two digits: 0 and 1. Each position represents a power of two, starting from the right with 2^0. For example, the binary number 1011 means 1x8 + 0x4 + 1x2 + 1x1 = 11 in decimal.

Result

You can convert any decimal number to binary and understand its bit pattern.

Understanding binary is essential because set bits are simply the 1s in this representation.

2

Foundation

Basics of Bitwise AND Operation

Concept: Learn how the AND operation works on bits to combine two numbers.

Bitwise AND compares each bit of two numbers. It returns 1 only if both bits are 1, otherwise 0. For example, 1101 & 1011 = 1001 because only the first and last bits are both 1.

Result

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

Bitwise AND is the key tool to isolate or remove bits, which is crucial for counting set bits efficiently.

3

Intermediate

Naive Set Bit Counting Method

🤔Before reading on: do you think checking each bit one by one is fast or slow for large numbers? Commit to your answer.

Concept: Counting set bits by checking each bit individually.

Start from the least significant bit and check if it is 1 by ANDing with 1. Then right-shift the number by one bit and repeat until the number becomes zero. Count how many times you find a 1.

Result

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

This method is simple but can be slow because it checks every bit, even zeros.

4

Intermediate

Brian Kernighan's Algorithm Introduction

🤔Before reading on: do you think it's possible to skip zero bits and only count set bits directly? Commit to your answer.

Concept: Using a trick to remove the rightmost set bit in each step to count set bits faster.

The algorithm repeatedly does: number = number & (number - 1). This operation removes the rightmost set bit. Count how many times this happens until the number becomes zero.

Result

For number 13 (1101), steps are: 1101 & 1100 = 1100 (count 1) 1100 & 1011 = 1000 (count 2) 1000 & 0111 = 0000 (count 3) Total set bits = 3.

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

5

Advanced

Implementing Brian Kernighan Algorithm in C++

🤔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: Writing a complete, runnable C++ function using Brian Kernighan's method.

int countSetBits(int n) { int count = 0; while (n) { n = n & (n - 1); // remove rightmost set bit count++; } return count; } // Example usage: // int result = countSetBits(13); // result will be 3

Result

Calling countSetBits(13) returns 3, the number of set bits in binary 1101.

This implementation is concise and efficient, running in time proportional to the number of set bits, not total bits.

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: Understanding when this algorithm shines and its limits compared to other methods.

Brian Kernighan's algorithm is very fast when numbers have few set bits. For dense numbers, lookup tables or hardware instructions may be faster. It is widely used in embedded systems and competitive programming for its simplicity and speed. Modern CPUs often have built-in instructions (like POPCNT) that outperform software methods.

Result

You know when to choose this algorithm and when to prefer hardware or table-based methods.

Knowing the algorithm's strengths and limits helps you write optimal code depending on the problem context.

Under the Hood

The key operation n = n & (n - 1) works because subtracting 1 flips all bits after the rightmost set bit, including that bit itself. ANDing with n clears that rightmost set bit. Repeating this removes one set bit at a time until none remain.

Why designed this way?

This method was designed to minimize the number of operations by skipping zero bits entirely. Earlier methods checked every bit, wasting time on zeros. The tradeoff is simplicity and speed, especially when set bits are sparse.

n (binary):    1 0 1 1 0 0 0
n - 1:         1 0 1 0 1 1 1
AND (n & n-1): 1 0 1 0 0 0 0

This clears the rightmost set bit (the fourth bit from right).

Myth Busters - 3 Common Misconceptions

Quick: Does n & (n - 1) always clear the leftmost set bit? Commit yes or no.

Common Belief: Many think n & (n - 1) clears the leftmost set bit.

Reality: It actually clears the rightmost set bit, the one closest to the least significant bit.

Why it matters: Misunderstanding this leads to incorrect bit manipulation and bugs in algorithms relying on this operation.

Quick: Is Brian Kernighan's algorithm always faster than checking each bit? Commit yes or no.

Common Belief: People often believe this algorithm is always the fastest way to count set bits.

Reality: It is faster when the number has few set bits but can be slower than hardware instructions or lookup tables for dense numbers.

Why it matters: Choosing the wrong method can cause performance issues in critical systems.

Quick: Does the algorithm work correctly for zero input? Commit yes or no.

Common Belief: Some think the algorithm might fail or loop infinitely if input is zero.

Reality: The algorithm immediately ends because the while loop condition fails when n is zero.

Why it matters: Knowing this prevents unnecessary checks or special cases in code.

Expert Zone

1

The algorithm's runtime depends on the number of set bits, not total bits, which is a rare and valuable property in bit manipulation.

2

In some architectures, combining this algorithm with hardware POPCNT instructions can optimize performance further by handling large chunks quickly.

3

When used in parallel algorithms, care must be taken because bitwise operations are not always thread-safe without synchronization.

When NOT to use

Avoid this algorithm when working with very dense bit patterns or when hardware instructions like POPCNT are available, as those are faster. For fixed small bit widths, lookup tables can be more efficient.

Production Patterns

Used in embedded systems for resource-limited environments, in competitive programming for fast bit counting, and in cryptographic algorithms where bit-level operations are common. Also used in graphics and compression algorithms to quickly analyze bit patterns.

Connections

Bitwise Operations

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

Mastering this algorithm deepens understanding of how bitwise operations can be combined to solve problems efficiently.

Population Count (POPCNT) Instruction

POPCNT is a hardware instruction that counts set bits, serving as a faster alternative to software algorithms.

Knowing software methods like Brian Kernighan's helps appreciate hardware optimizations and fallback strategies.

Error Detection in Communication Systems

Counting set bits is used in parity checks and error detection codes to find errors in transmitted data.

Understanding set bit counting algorithms helps grasp how computers detect and correct errors in real-world data transmission.

Common Pitfalls

#1 Using n & (n - 1) without updating n inside the loop.

Wrong approach:

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

Correct approach:

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

Root cause:

Forgetting to assign the result back to n means the loop never changes n, causing an infinite loop.

#2 Using the algorithm on negative numbers without considering two's complement.

Wrong approach:

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

Correct approach:

Use unsigned integers to avoid infinite loops:
unsigned int countSetBits(unsigned int n) {
int count = 0;
while (n) {
n = n & (n - 1);
count++;
}
return count;
}

Root cause:

Negative numbers in two's complement have infinite leading 1s, causing the loop to never end.

#3 Assuming the algorithm counts unset bits (0s) instead of set bits (1s).

Wrong approach:

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

Correct approach:

int countUnsetBits(int n) {
int totalBits = sizeof(n) * 8;
int setBits = 0;
int temp = n;
while (temp) {
temp = temp & (temp - 1);
setBits++;
}
return totalBits - setBits;
}

Root cause:

The algorithm only counts set bits; counting unset bits requires subtracting from total bit length.

Key Takeaways

Brian Kernighan's algorithm efficiently counts set bits by repeatedly clearing the rightmost set bit.

Its runtime depends on the number of set bits, making it faster than checking every bit for sparse numbers.

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

The algorithm is simple, elegant, and widely used in performance-critical applications.

Knowing its limits and alternatives like hardware instructions ensures optimal use in real-world scenarios.

Practice

1. What does the Brian Kernighan algorithm do when counting set bits in an integer?

easy

A. It repeatedly clears the least significant set bit until the number becomes zero.

B. It counts the total number of digits in the integer.

C. It shifts the bits to the right one by one and counts all bits.

D. It converts the number to a string and counts '1' characters.

Solution

1. Step 1: Understand the algorithm's main operation

   The Brian Kernighan algorithm works by clearing the least significant set bit in each iteration.

2. Step 2: Effect of clearing bits

   Each clearing reduces the number of set bits by one until the number becomes zero.

3. Final Answer:

   It repeatedly clears the least significant set bit until the number becomes zero. -> Option A

4. Quick Check:

   Clearing bits one by one counts set bits [OK]

Hint: Clear least significant set bit repeatedly to count bits [OK]

Common Mistakes:

• Counting all bits instead of only set bits
• Using string conversion unnecessarily
• Shifting bits without checking if set

2. Which of the following is the correct syntax for the main loop in Brian Kernighan's algorithm in C++?

easy

A. while (n > 0) { count += n % 2; n /= 2; }

B. for (int i = 0; i < n; i++) { count += n & 1; n >>= 1; }

C. while (n != 0) { n = n & (n - 1); count++; }

D. for (int i = 0; i < 32; i++) { count += (n >> i) & 1; }

Solution

1. Step 1: Identify Brian Kernighan's loop

   The algorithm uses while (n != 0) and clears the least significant set bit by n = n & (n - 1).

2. Step 2: Confirm increment of count

   Each iteration increments count by one for each cleared set bit.

3. Final Answer:

   while (n != 0) { n = n & (n - 1); count++; } -> Option C

4. Quick Check:

   Loop clears bits and counts [OK]

Hint: Use while with n = n & (n-1) to clear bits [OK]

Common Mistakes:

• Using for loop instead of while
• Counting bits by shifting instead of clearing
• Using modulo instead of bitwise operations

3. What is the output of the following C++ code snippet using Brian Kernighan's algorithm?

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

int main() {
  int x = 13;
  std::cout << countSetBits(x);
  return 0;
}

medium

A. 5

B. 3

C. 2

D. 4

Solution

1. Step 1: Convert 13 to binary

   13 in binary is 1101, which has three set bits (1s).

2. Step 2: Apply Brian Kernighan's algorithm

   Each iteration clears one set bit, so count increments 3 times before n becomes 0.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Number of 1s in 1101 = 3 [OK]

Hint: Count 1s in binary of number for quick answer [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Miscounting binary 1s
• Confusing bitwise AND with OR

4. Identify the error in this Brian Kernighan algorithm implementation:

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

medium

A. Missing return statement.

B. Not initializing count to zero.

C. Using while (n > 0) instead of while (n != 0).

D. Using n + 1 instead of n - 1 in bit clearing step.

Solution

1. Step 1: Check bit clearing operation

   The correct operation to clear the least significant set bit is n = n & (n - 1), not n + 1.

2. Step 2: Effect of wrong operation

   Using n + 1 does not clear bits properly and causes incorrect count or infinite loop.

3. Final Answer:

   Using n + 1 instead of n - 1 in bit clearing step. -> Option D

4. Quick Check:

   Correct bit clearing uses n & (n - 1) [OK]

Hint: Use n & (n - 1) to clear bits, not n + 1 [OK]

Common Mistakes:

• Replacing n - 1 with n + 1
• Confusing loop condition syntax
• Forgetting to increment count

5. Given an array of integers, how can you use Brian Kernighan's algorithm to find the total number of set bits in all elements? Choose the best approach.

hard

A. Iterate over each element, apply Brian Kernighan's algorithm to count set bits, and sum all counts.

B. Convert all integers to strings and count '1's in each string, then sum.

C. Use a single Brian Kernighan's algorithm call on the sum of all integers.

D. Count set bits only in the first element and multiply by array size.

Solution

1. Step 1: Understand counting set bits per element

   Brian Kernighan's algorithm counts set bits in one integer at a time.

2. Step 2: Apply algorithm to each array element

   Iterate through the array, count set bits for each element, and sum these counts for total.

3. Final Answer:

   Iterate over each element, apply Brian Kernighan's algorithm to count set bits, and sum all counts. -> Option A

4. Quick Check:

   Sum of individual counts gives total set bits [OK]

Hint: Count bits per element, then sum for total [OK]

Common Mistakes:

• Counting bits of sum instead of each element
• Using string conversion unnecessarily
• Assuming uniform bit count per element