Count Set Bits Brian Kernighan Algorithm in DSA C# - Execution Trace

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→Stop, count is final

Yes↓

Perform n = n & (n-1)

↓

Increment count by 1

↩Back to Check n != 0

The algorithm repeatedly removes the rightmost set bit from n by doing n = n & (n-1), counting how many times this happens until n becomes zero.

Execution Sample

DSA C#

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

Counts how many bits are set to 1 in the binary form of n using Brian Kernighan's method.

Execution Table

Step	Operation	n (binary)	n (decimal)	Count	Visual State
1	Start	00001011	11	0	Initial number 11 (binary 1011)
2	n = n & (n-1)	00001010	10	1	Removed rightmost set bit from 1011 to 1010
3	n = n & (n-1)	00001000	8	2	Removed rightmost set bit from 1010 to 1000
4	n = n & (n-1)	00000000	0	3	Removed rightmost set bit from 1000 to 0000
5	Check n != 0	00000000	0	3	n is zero, stop counting

💡 n becomes 0 at step 4, loop ends with count = 3

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
n (decimal)	11	10	8	0	0
count	0	1	2	3	3

Key Moments - 3 Insights

Why does n = n & (n-1) remove the rightmost set bit?

Because subtracting 1 flips all bits after the rightmost set bit including it, and ANDing with n clears that rightmost set bit. See execution_table steps 2-4 where n changes from 1011 to 1010 to 1000.

Why does the loop stop when n becomes zero?

Because zero means no bits are set. The condition n != 0 in execution_table step 5 stops the loop, ensuring all set bits are counted.

What if the input number is zero at the start?

The loop never runs and count remains zero, as shown by the check at step 1 in execution_table where n=0 would skip the loop.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of count after step 3?

A 3

B 1

C 2

D 0

💡 Hint

Check the 'Count' column at step 3 in execution_table.

At which step does n become zero, ending the loop?

A Step 3

B Step 4

C Step 5

D Step 2

💡 Hint

Look at the 'n (decimal)' column and the exit_note in execution_table.

If the input number was 8 (binary 1000), how many times would the loop run?

A 1

B 2

C 3

D 4

💡 Hint

Think about how many set bits 8 has and relate to count increments in variable_tracker.

Concept Snapshot

Brian Kernighan's Algorithm to count set bits:
- Initialize count = 0
- While n != 0:
  - n = n & (n-1) removes rightmost set bit
  - Increment count
- Return count
Efficiently counts 1s in binary representation by clearing bits one by one.

Full Transcript

This visualization shows Brian Kernighan's algorithm to count set bits in a number. Starting with n=11 (binary 1011), each step clears the rightmost set bit by n = n & (n-1) and increments count. The process repeats until n becomes zero. The execution table tracks n's binary and decimal values, count, and visual state after each operation. Key moments clarify why the bit clearing works and when the loop stops. The quiz tests understanding of count values and loop termination. This method efficiently counts set bits by removing one set bit per iteration.

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