Count Set Bits Brian Kernighan Algorithm in DSA Rust - 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 smart way to do this quickly by removing the rightmost 1 bit one by one. Instead of checking every bit, it jumps directly to the next set bit until none are left. This makes counting faster, especially for numbers with few 1s.

Why it matters

Without efficient bit counting, programs that rely on bit operations, like compression, encryption, or graphics, would run slower and waste resources. The Brian Kernighan algorithm speeds up these tasks by reducing unnecessary checks. This helps software run faster and saves energy, which is important in devices like phones or servers.

Where it fits

Before learning this, you should understand binary numbers and basic bitwise operations like AND and subtraction. After this, you can explore other bit manipulation tricks and optimizations used in algorithms and systems programming.

Mental Model

Core Idea

Each step of the Brian Kernighan algorithm removes the rightmost 1 bit, counting how many times this can be done until the number becomes zero.

Think of it like...

Imagine you have a row of lit candles representing 1s. Each time you blow out the rightmost lit candle, you count one. You keep doing this until no candles are left lit.

Number (binary): 10110
Step 1: 10110 & (10110 - 1) = 10110 & 10101 = 10100 (count 1)
Step 2: 10100 & (10100 - 1) = 10100 & 10011 = 10000 (count 2)
Step 3: 10000 & (10000 - 1) = 10000 & 01111 = 00000 (count 3)
Result: 3 set bits

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn how numbers are represented in binary using 0s and 1s.

Every number can be shown as a series of bits (0 or 1). For example, decimal 6 is 110 in binary, meaning 1*2^2 + 1*2^1 + 0*2^0. Each bit position represents a power of two.

Result

You can convert any decimal number to binary and see which bits are set (1) or unset (0).

Understanding binary is essential because bit counting works directly on this representation.

2

Foundation

Basics of Bitwise AND Operation

Concept: Learn how the AND operation compares bits of two numbers.

Bitwise AND compares each bit of two numbers and returns 1 only if both bits are 1. For example, 1101 & 1011 = 1001. This operation helps isolate or clear bits.

Result

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

Knowing AND is crucial because the Brian Kernighan algorithm uses it to remove bits.

3

Intermediate

Naive Set Bit Counting Method

Concept: Counting bits by checking each bit one by one.

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

Result

For number 13 (1101), the count is 3 set bits after checking all bits.

This method works but can be slow for large numbers because it checks every bit.

4

Intermediate

Brian Kernighan Algorithm Introduction

🤔Before reading on: do you think removing the rightmost set bit reduces the number of steps compared to checking every bit? Commit to yes or no.

Concept: Instead of checking all bits, remove the rightmost set bit repeatedly to count set bits faster.

The key trick: n = n & (n - 1) removes the rightmost 1 bit from n. Repeat this until n becomes zero, counting how many times you do it.

Result

For 13 (1101): Step 1: 1101 & 1100 = 1100 (count 1) Step 2: 1100 & 1011 = 1000 (count 2) Step 3: 1000 & 0111 = 0000 (count 3) Total set bits = 3

Removing the rightmost set bit skips zeros, making counting faster especially when few bits are set.

5

Advanced

Rust Implementation of Brian Kernighan Algorithm

🤔Before reading on: do you think the loop will run as many times as there are set bits or total bits? Commit to your answer.

Concept: Write efficient Rust code using the Brian Kernighan method to count set bits.

fn count_set_bits(mut n: u32) -> u32 { let mut count = 0; while n != 0 { n &= n - 1; // remove rightmost set bit count += 1; } count } // Example usage: // let result = count_set_bits(13); // println!("Set bits: {}", result);

Result

Output for input 13: Set bits: 3

Knowing how to implement this in Rust shows practical use and how bitwise operations work in real code.

6

Expert

Performance and Use Cases of Brian Kernighan Algorithm

🤔Before reading on: do you think this algorithm is always faster than built-in bit counting functions? Commit to yes or no.

Concept: Understand when this algorithm shines and its limits compared to hardware or built-in functions.

Brian Kernighan's algorithm runs in time proportional to the number of set bits, not total bits. This is great for sparse bitsets. However, modern CPUs often have built-in instructions (like POPCNT) that count bits faster. Still, this algorithm is useful in environments without such instructions or for teaching bit manipulation.

Result

You learn when to prefer this algorithm and when to rely on hardware or library functions.

Knowing the algorithm's performance characteristics helps choose the right tool for the job.

Under the Hood

The algorithm works by exploiting the fact that subtracting 1 from a number flips all bits after the rightmost set bit, including that bit itself. When you AND the original number with (number - 1), you clear the rightmost set bit. Repeating this removes one set bit at a time until the number becomes zero.

Why designed this way?

This method was designed to count set bits efficiently without checking every bit. It reduces the number of operations to the number of set bits, which is often much smaller than total bits. Alternatives like checking each bit are slower, and hardware instructions were not always available.

n (binary): 10110
n - 1:      10101
n & (n-1):  10100  <-- rightmost set bit cleared
Repeat until n = 0

Myth Busters - 3 Common Misconceptions

Quick: Does the Brian Kernighan algorithm check every bit in the number? Commit to yes or no.

Common Belief: It checks every bit one by one to count set bits.

Reality: It only loops as many times as there are set bits, skipping zeros entirely.

Why it matters: Believing it checks every bit leads to underestimating its efficiency and missing optimization opportunities.

Quick: Is the Brian Kernighan algorithm always faster than CPU built-in bit counting? Commit to yes or no.

Common Belief: This algorithm is always the fastest way to count set bits.

Reality: Modern CPUs have special instructions that count bits faster than this algorithm.

Why it matters: Ignoring hardware capabilities can lead to slower programs when better options exist.

Quick: Does subtracting 1 from a number always clear the rightmost set bit? Commit to yes or no.

Common Belief: Subtracting 1 always clears the rightmost set bit directly.

Reality: Subtracting 1 flips bits after the rightmost set bit and clears that bit, enabling the AND operation to remove it.

Why it matters: Misunderstanding this can cause confusion about why the algorithm works and how bitwise operations behave.

Expert Zone

1

The algorithm's runtime depends on the number of set bits, making it ideal for sparse bitsets but less so for dense ones.

2

In some languages or platforms, compiler intrinsics or CPU instructions can replace this algorithm for better performance.

3

Understanding this algorithm helps in designing custom bitset data structures and low-level optimizations.

When NOT to use

Avoid this algorithm when your platform supports hardware bit counting instructions like POPCNT or when working with very dense bitsets where other methods may be faster.

Production Patterns

Used in embedded systems without hardware support, in cryptography for bit counting, and in competitive programming for fast bit manipulation.

Connections

Bitwise Operations

Builds-on

Mastering this algorithm deepens understanding of AND, subtraction, and bit manipulation fundamentals.

Population Count Instruction (POPCNT)

Alternative approach

Knowing this algorithm helps appreciate hardware instructions that optimize the same problem.

Digital Circuit Design

Similar pattern

The idea of clearing bits one by one relates to how circuits count signals or pulses efficiently.

Common Pitfalls

#1 Using a loop that checks every bit instead of removing set bits.

Wrong approach:

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

Correct approach:

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

Root cause:

Not knowing the trick to remove the rightmost set bit leads to slower bit counting.

#2 Assuming n & (n - 1) always clears the leftmost set bit.

Wrong approach:

let n = 0b10100;
let result = n & (n - 1); // expecting leftmost bit cleared

Correct approach:

let n = 0b10100;
let result = n & (n - 1); // actually clears rightmost set bit

Root cause:

Misunderstanding which bit is cleared by the operation causes incorrect assumptions.

Key Takeaways

Counting set bits efficiently is important for many computing tasks involving binary data.

The Brian Kernighan algorithm removes the rightmost set bit repeatedly to count set bits faster than checking each bit.

This algorithm runs in time proportional to the number of set bits, making it efficient for sparse bit patterns.

Understanding bitwise operations like AND and subtraction is essential to grasp how this algorithm works.

While powerful, this algorithm can be outperformed by hardware instructions on modern CPUs.

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