Count Set Bits Brian Kernighan Algorithm in DSA Rust - Execution Trace

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→End: count is final

Yes↓

Remove rightmost set bit: n = n & (n-1)

↓

Increment count

↓

Repeat check

The algorithm repeatedly removes the rightmost set bit from the number and counts how many times this happens until the number becomes zero.

Execution Sample

DSA Rust

fn count_set_bits(mut n: u32) -> u32 {
    let mut count = 0;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    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	Check n != 0	00001011	11	0	11 != 0, continue
3	Remove rightmost set bit: n = n & (n-1)	00001011 & 00001010 = 00001010	11 & 10 = 10	0	n becomes 10 (binary 1010)
4	Increment count	00001010	10	1	Count incremented to 1
5	Check n != 0	00001010	10	1	10 != 0, continue
6	Remove rightmost set bit	00001010 & 00001001 = 00001000	10 & 9 = 8	1	n becomes 8 (binary 1000)
7	Increment count	00001000	8	2	Count incremented to 2
8	Check n != 0	00001000	8	2	8 != 0, continue
9	Remove rightmost set bit	00001000 & 00000111 = 00000000	8 & 7 = 0	2	n becomes 0 (binary 0)
10	Increment count	00000000	0	3	Count incremented to 3
11	Check n != 0	00000000	0	3	0 == 0, stop
12	Return count	-	-	3	Final count is 3

💡 n becomes 0, so loop ends and count of set bits is returned

Variable Tracker

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

Key Moments - 3 Insights

Why do we use n = n & (n-1) to remove the rightmost set bit?

Because subtracting 1 flips all bits after the rightmost set bit, and ANDing with n clears that rightmost set bit. See execution_table steps 3, 6, and 9 for how n changes.

Why does the loop stop when n becomes zero?

Because zero means no bits are set. The condition n != 0 fails at step 11, so the loop ends and count is final.

How does the count variable track the number of set bits?

Each time we remove a set bit (steps 4, 7, 10), we increment count by 1. This matches the number of times the loop runs.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of n (decimal) after step 6?

A 9

B 8

C 10

D 0

💡 Hint

Check the 'n (decimal)' column at step 6 in the execution_table.

At which step does the count variable become 3?

A Step 10

B Step 9

C Step 11

D Step 12

💡 Hint

Look at the 'Count' column in execution_table rows for when count increments.

If the input number was 0, how many times would the loop run?

A Depends on number

B 1 time

C 0 times

D Infinite loop

💡 Hint

Refer to the exit condition in execution_table step 2 and 11 where n == 0 stops the loop.

Concept Snapshot

Count Set Bits using Brian Kernighan Algorithm:
- Initialize count = 0
- While n != 0:
  - n = n & (n-1) removes rightmost set bit
  - Increment count
- Return count
Efficiently counts set bits by clearing one bit per iteration.

Full Transcript

This visualization shows how Brian Kernighan's algorithm counts the number of set bits in a number. Starting with the input number n, the algorithm checks if n is not zero. If not zero, it removes the rightmost set bit by performing n = n & (n-1), then increments the count. This repeats until n becomes zero, meaning no set bits remain. The count variable then holds the total number of set bits. The execution table traces each step with binary and decimal values of n and the count. Key moments clarify why the bit removal works and when the loop stops. The visual quiz tests understanding of variable values at specific steps. This method is efficient because it only loops as many times as there are set bits, not the total number of bits.

Practice

1. What does the Brian Kernighan algorithm do when counting set bits in a number?

easy

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

B. It counts the total number of bits in the number

C. It shifts the number right until it becomes zero

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 time the least significant set bit is cleared, the count of set bits increases 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 set bit repeatedly to count set bits [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Using string conversion instead of bit operations
• Shifting without checking bits

2. Which of the following Rust code snippets correctly implements the Brian Kernighan algorithm to count set bits?

easy

A. fn count_set_bits(mut n: u32) -> u32 { let mut count = 0; while n > 0 { count += n & 1; n >>= 1; } count }

B. fn count_set_bits(n: u32) -> u32 { n.count_ones() }

C. fn count_set_bits(n: u32) -> u32 { n.trailing_zeros() }

D. fn count_set_bits(mut n: u32) -> u32 { let mut count = 0; while n != 0 { n &= n - 1; count += 1; } count }

Solution

1. Step 1: Identify the Brian Kernighan algorithm code

   fn count_set_bits(mut n: u32) -> u32 { let mut count = 0; while n != 0 { n &= n - 1; count += 1; } count } uses the loop with n &= n - 1 to clear the least significant set bit repeatedly.

2. Step 2: Verify other options

   fn count_set_bits(n: u32) -> u32 { n.count_ones() } uses built-in count_ones(), fn count_set_bits(mut n: u32) -> u32 { let mut count = 0; while n > 0 { count += n & 1; n >>= 1; } count } uses bit shifting, and fn count_set_bits(n: u32) -> u32 { n.trailing_zeros() } uses trailing_zeros(), which are not Brian Kernighan's method.

3. Final Answer:

   fn count_set_bits(mut n: u32) -> u32 { let mut count = 0; while n != 0 { n &= n - 1; count += 1; } count } -> Option D

4. Quick Check:

   n &= n - 1 loop is Brian Kernighan's method [OK]

Hint: Use n &= n - 1 in loop to clear bits [OK]

Common Mistakes:

• Using built-in functions instead of algorithm
• Shifting bits instead of clearing
• Using trailing_zeros which counts zeros, not ones

3. What is the output of the following Rust code?

fn main() {
    let mut n = 29u32; // binary 11101
    let mut count = 0;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    println!("{}", count);
}

medium

A. 3

B. 4

C. 5

D. 6

Solution

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

   29 in binary is 11101, which has four set bits (1s).

2. Step 2: Apply Brian Kernighan algorithm steps

   Each iteration clears one set bit until n becomes zero, so count increments 4 times.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Number of 1s in 11101 = 4 [OK]

Hint: Count 1s in binary representation [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Miscounting binary digits
• Confusing zero bits with set bits

4. Identify the error in this Rust implementation of Brian Kernighan's algorithm:

fn count_set_bits(mut n: u32) -> u32 {
    let mut count = 0;
    while n > 0 {
        n = n - 1;
        count += 1;
    }
    count
}

medium

A. It uses n > 0 instead of n != 0 in the loop condition

B. It uses a while loop instead of a for loop

C. It decrements n by 1 instead of clearing the least significant set bit

D. It does not initialize count to zero

Solution

1. Step 1: Analyze the loop operation on n

   The code subtracts 1 from n each time, which does not clear the least significant set bit correctly.

2. Step 2: Understand Brian Kernighan's method

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

3. Final Answer:

   It decrements n by 1 instead of clearing the least significant set bit -> Option C

4. Quick Check:

   Use n &= n - 1 to clear bits, not n = n - 1 [OK]

Hint: Use bitwise AND to clear bits, not subtraction alone [OK]

Common Mistakes:

• Using subtraction instead of bitwise AND
• Wrong loop condition causing infinite loop
• Not incrementing count properly

5. Given a list of unsigned integers [7, 8, 15, 23], which Rust code using Brian Kernighan's algorithm correctly returns a vector of their set bit counts?

hard

A. fn count_bits_list(nums: &[u32]) -> Vec<u32> { nums.iter().map(|&n| { let mut x = n; let mut c = 0; while x != 0 { x &= x - 1; c += 1; } c }).collect() }

B. fn count_bits_list(nums: &[u32]) -> Vec<u32> { nums.iter().map(|&n| n.count_ones()).collect() }

C. fn count_bits_list(nums: &[u32]) -> Vec<u32> { nums.iter().map(|&n| n.trailing_zeros()).collect() }

D. fn count_bits_list(nums: &[u32]) -> Vec<u32> { nums.iter().map(|&n| n.leading_zeros()).collect() }

Solution

1. Step 1: Identify Brian Kernighan's algorithm in code

   fn count_bits_list(nums: &[u32]) -> Vec<u32> { nums.iter().map(|&n| { let mut x = n; let mut c = 0; while x != 0 { x &= x - 1; c += 1; } c }).collect() } uses the loop with x &= x - 1 to count set bits for each number.

2. Step 2: Check other options

   Options B, C, and D use built-in functions not related to Brian Kernighan's algorithm.

3. Step 3: Confirm output correctness

   fn count_bits_list(nums: &[u32]) -> Vec<u32> { nums.iter().map(|&n| { let mut x = n; let mut c = 0; while x != 0 { x &= x - 1; c += 1; } c }).collect() } returns a vector with counts of set bits for each number in the list.

4. Final Answer:

   fn count_bits_list(nums: &[u32]) -> Vec<u32> { nums.iter().map(|&n| { let mut x = n; let mut c = 0; while x != 0 { x &= x - 1; c += 1; } c }).collect() } -> Option A

5. Quick Check:

   Loop with x &= x - 1 counts bits per number [OK]

Hint: Map each number with Brian Kernighan loop to count bits [OK]

Common Mistakes:

• Using built-in count_ones instead of algorithm
• Using trailing_zeros or leading_zeros which count zeros
• Not collecting results into a vector