Count Set Bits Brian Kernighan Algorithm in DSA Rust

Mental Model

Count how many 1s are in a number's binary form 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 all are out.

Number bits: 1 0 1 1 0 1 0 0
Rightmost 1 -> remove it -> count++
Example: 10110100 -> 10110000 -> 10100000 -> ...

Dry Run Walkthrough

Input: number = 13 (binary 1101)

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

Step 1: Start with number 13 (binary 1101), count = 0

1101 (13) count=0

Why: Initialize count and start with full number

Step 2: Remove rightmost set bit: number = number & (number - 1) -> 1101 & 1100 = 1100 (12), count=1

1100 (12) count=1

Why: Removing rightmost 1 reduces number of set bits by one

Step 3: Remove rightmost set bit again: 1100 & 1011 = 1000 (8), count=2

1000 (8) count=2

Why: Keep removing rightmost 1 to count all set bits

Step 4: Remove rightmost set bit again: 1000 & 0111 = 0000 (0), count=3

0000 (0) count=3

Why: No more set bits left, stop

Result:

0000 (0) count=3
Answer: 3 set bits in 13

Annotated Code

DSA Rust

fn count_set_bits(mut n: u32) -> u32 {
    let mut count = 0;
    while n != 0 {
        n = n & (n - 1); // remove rightmost set bit
        count += 1; // increment count for each removed bit
    }
    count
}

fn main() {
    let number = 13;
    let result = count_set_bits(number);
    println!("Number of set bits in {} is {}", number, result);
}

while n != 0 {

loop until all set bits are removed

n = n & (n - 1); // remove rightmost set bit

remove rightmost set bit to reduce count

count += 1; // increment count for each removed bit

count how many set bits removed

Output

Number of set bits in 13 is 3

Complexity Analysis

Time: O(k) because it loops once for each set bit k in the number

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

vs Alternative: Better than checking each bit one by one (O(n) where n is bit length), this only loops set bits

Edge Cases

number = 0 (no set bits)

loop does not run, count remains 0

DSA Rust

while n != 0 {

number = 1 (single set bit)

loop runs once, count becomes 1

DSA Rust

while n != 0 {

number with all bits set (e.g. 0xFFFFFFFF)

loop runs for all bits, counting each set bit

DSA Rust

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 quickly.

Common Mistakes

Mistake: Looping through all bits by shifting and checking each bit instead of removing rightmost set bit
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 the problem size quickly.

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