Count Set Bits Brian Kernighan Algorithm in DSA C#

Mental Model

Count how many 1s are in the binary form of a number by removing the rightmost 1 one by one.

Analogy: Imagine you have a row of lit candles (1s). Each time you blow out the rightmost lit candle, you count one until none are left.

Number: 13 (binary 1101)
Bits: 1 -> 1 -> 0 -> 1
Rightmost 1 marked: 1 -> 1 -> 0 -> [1↑]

Dry Run Walkthrough

Input: number = 13 (binary 1101)

Goal: Count how many bits are set to 1 in the number 13

Step 1: Remove rightmost set bit from 1101

1101 (13) -> 1100 (12)

Why: Removing rightmost 1 reduces count by one, helps count set bits efficiently

Step 2: Remove rightmost set bit from 1100

1100 (12) -> 1000 (8)

Why: Next rightmost 1 removed to count another set bit

Step 3: Remove rightmost set bit from 1000

1000 (8) -> 0000 (0)

Why: Last set bit removed, counting complete

Result:

0000 (0) with count = 3 set bits

Annotated Code

DSA C#

using System;

class Program
{
    // Function to count set bits using Brian Kernighan's Algorithm
    static int CountSetBits(int n)
    {
        int count = 0;
        while (n > 0)
        {
            n = n & (n - 1); // remove rightmost set bit
            count++; // increment count for each removal
        }
        return count;
    }

    static void Main()
    {
        int number = 13;
        int result = CountSetBits(number);
        Console.WriteLine($"Number of set bits in {number} is {result}");
    }
}

while (n > 0)

loop until all set bits are removed

n = n & (n - 1);

remove rightmost set bit from n

count++;

increment count for each removed set bit

Output

Number of set bits in 13 is 3

Complexity Analysis

Time: O(k) where k is number of set bits, because each iteration removes one set bit

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Better than checking all bits (O(log n)) because it only loops over set bits, not total bits

Edge Cases

number = 0 (no set bits)

loop does not run, count remains 0

DSA C#

while (n > 0)

number = 1 (single set bit)

loop runs once, count becomes 1

DSA C#

while (n > 0)

number with all bits set (e.g., 15 for 4 bits)

loop runs once per set bit, count equals total bits set

DSA C#

while (n > 0)

When to Use This Pattern

When you need to count how many bits are 1 in a number efficiently, use Brian Kernighan's algorithm because it skips zero bits and counts only set bits.

Common Mistakes

Mistake: Looping through all bits by shifting and checking each bit instead of removing set bits directly.
Fix: Use n = n & (n - 1) to remove rightmost set bit and count only set bits.

Summary

Counts how many bits are set to 1 in a number by repeatedly removing the rightmost set bit.

Use when you want an efficient way to count set bits without checking every bit.

The key insight is that n & (n - 1) removes the rightmost set bit, reducing work to number of set bits.

Practice

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

easy

A. It converts the number to a string and counts characters.

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

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

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

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 on counting set bits

   Each time it clears a set bit, it increments the count until the number becomes zero.

3. Final Answer:

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

4. Quick Check:

   Clearing bits counts set bits [OK]

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

Common Mistakes:

• Counting zeros instead of ones
• Using string conversion to count bits
• Shifting bits without clearing

2. Which of the following is the correct syntax to clear the least significant set bit in C# using Brian Kernighan's method?

easy

A. n = n & (n - 1);

B. n = n | (n - 1);

C. n = n ^ (n + 1);

D. n = n << 1;

Solution

1. Step 1: Identify the bit clearing operation

   The expression n = n & (n - 1) clears the least significant set bit in n.

2. Step 2: Verify other options

   Other options perform different bitwise operations that do not clear the least significant set bit.

3. Final Answer:

   n = n & (n - 1); -> Option A

4. Quick Check:

   Use n & (n-1) to clear least set bit [OK]

Hint: Use n & (n-1) to clear least set bit [OK]

Common Mistakes:

• Using OR instead of AND
• Using XOR with n+1 incorrectly
• Using left shift which moves bits

3. What is the output of the following C# code snippet?

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

Console.WriteLine(countSetBits(13));

medium

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Convert 13 to binary and count set bits

   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 the loop runs 3 times, incrementing count to 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Binary 1101 has 3 ones [OK]

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

Common Mistakes:

• Counting total bits instead of set bits
• Misunderstanding bitwise AND operation
• Off-by-one errors in loop

4. Identify the error in the following C# code that attempts to count set bits using Brian Kernighan's algorithm:

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

medium

A. Missing return statement

B. Using n & (n + 1) instead of n & (n - 1)

C. Count variable not initialized

D. Incorrect loop condition; should be n > 0

Solution

1. Step 1: Check the bit clearing expression

   The code uses n & (n + 1), which does not clear the least significant set bit correctly.

2. Step 2: Correct expression for clearing bits

   The correct expression is n & (n - 1) to clear the least significant set bit.

3. Final Answer:

   Using n & (n + 1) instead of n & (n - 1) -> Option B

4. Quick Check:

   Use n & (n-1) to clear bits [OK]

Hint: Always use n & (n-1) to clear least set bit [OK]

Common Mistakes:

• Using n & (n + 1) which is incorrect
• Confusing loop conditions
• Forgetting to initialize count

5. You want to count set bits in a large list of integers efficiently using Brian Kernighan's algorithm in C#. Which approach is best to optimize performance?

hard

A. Convert each integer to binary string and count '1' characters sequentially.

B. Use a simple for loop shifting bits right and counting set bits sequentially.

C. Use Brian Kernighan's algorithm inside a parallel loop to count bits for each integer concurrently.

D. Store all integers in a list and count set bits only for the first element.

Solution

1. Step 1: Understand the need for efficiency

   Counting set bits for many integers can be slow if done sequentially.

2. Step 2: Use parallel processing with Brian Kernighan's algorithm

   Running the efficient bit counting algorithm concurrently on multiple integers speeds up processing.

3. Final Answer:

   Use Brian Kernighan's algorithm inside a parallel loop to count bits for each integer concurrently. -> Option C

4. Quick Check:

   Parallel + efficient algorithm = best performance [OK]

Hint: Combine parallelism with Brian Kernighan's method [OK]

Common Mistakes:

• Using string conversion which is slow
• Sequential bit shifting which is less efficient
• Ignoring concurrency for large data