Count Set Bits Brian Kernighan Algorithm in DSA Go - 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 one set bit at a time. Instead of checking every bit, it jumps directly to the next set bit. This makes counting faster, especially for numbers with few set bits.

Why it matters

Without an efficient way to count set bits, programs would waste time checking every bit one by one. This slows down tasks like error detection, cryptography, and data compression. The Brian Kernighan algorithm speeds up these tasks, making software faster and more efficient in real life.

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 optimization techniques in algorithms.

Mental Model

Core Idea

Each step of the Brian Kernighan algorithm removes the rightmost set 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 set bits. Each time you blow out the rightmost lit candle, you count one. You keep doing this until all candles are out.

Number:  0b10110 (22 decimal)
Step 1:  0b10110 & (0b10110 - 1) = 0b10110 & 0b10101 = 0b10100 (20 decimal)
Step 2:  0b10100 & (0b10100 - 1) = 0b10100 & 0b10011 = 0b10000 (16 decimal)
Step 3:  0b10000 & (0b10000 - 1) = 0b10000 & 0b01111 = 0b00000 (0 decimal)
Count of steps = 3 set bits

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn how numbers are represented in binary using bits.

Every number in computers is stored as bits, which are 0s and 1s. For example, the number 5 is 101 in binary. Each position represents a power of two, starting from the right with 2^0. Counting how many 1s are in this binary form is called counting set bits.

Result

You can convert any decimal number to binary and identify which bits are set (1).

Understanding binary is essential because bitwise algorithms work directly on these bits, not decimal numbers.

2

Foundation

Basics of Bitwise Operations

Concept: Introduce bitwise AND and subtraction operations used in the algorithm.

Bitwise AND (&) compares two bits and returns 1 only if both bits are 1. Subtraction reduces a number by one, affecting its binary form. For example, 6 (110) - 1 = 5 (101). These operations help manipulate bits directly.

Result

You can perform bitwise AND and subtraction on numbers and see how bits change.

Knowing how these operations change bits is key to understanding how the algorithm removes set bits.

3

Intermediate

Naive Set Bit Counting Method

🤔Before reading on: Do you think checking each bit one by one is fast or slow for large numbers? Commit to your answer.

Concept: Counting set bits by checking each bit individually.

The simplest way is to check each bit from right to left using a mask. For each bit, check if it is 1 and count it. This takes as many steps as the number of bits in the number (e.g., 32 or 64).

Result

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

This method is easy but inefficient for large numbers because it always checks every bit, even if most are zero.

4

Intermediate

Brian Kernighan Algorithm Introduction

🤔Before reading on: Do you think removing one set bit at a time can be faster than checking all bits? Commit to your answer.

Concept: Use bitwise trick to remove the rightmost set bit in each step.

The algorithm repeatedly does: number = number & (number - 1). This operation removes the rightmost set bit. Count how many times this happens until the number becomes zero. This counts all set bits efficiently.

Result

For number 13 (1101), steps are: 1101 & 1100 = 1100 (count 1) 1100 & 1011 = 1000 (count 2) 1000 & 0111 = 0000 (count 3) Total count = 3

Removing set bits directly skips zeros, making counting faster especially when few bits are set.

5

Advanced

Implementing Brian Kernighan in Go

🤔Before reading on: Predict the output of counting set bits for 29 using this algorithm.

Concept: Write a complete Go function using the algorithm to count set bits.

package main import "fmt" func countSetBits(n uint) int { count := 0 for n != 0 { n = n & (n - 1) // Remove rightmost set bit count++ } return count } func main() { fmt.Println(countSetBits(29)) // 29 in binary is 11101 }

Result

Output: 4

Seeing the code in action confirms the algorithm's efficiency and correctness.

6

Expert

Performance and Use Cases of Brian Kernighan

🤔Before reading on: Do you think this algorithm is always the fastest way to count set bits? Commit to your answer.

Concept: Understand when this algorithm excels and its limits compared to other methods.

Brian Kernighan's algorithm runs in time proportional to the number of set bits, not total bits. This is great for sparse numbers. However, for numbers with many set bits, lookup tables or hardware instructions may be faster. It is widely used in embedded systems and low-level programming where speed and simplicity matter.

Result

You know when to choose this algorithm and when to consider alternatives.

Knowing the algorithm's performance characteristics helps optimize real-world applications.

Under the Hood

The key operation n = n & (n - 1) works because subtracting 1 flips all bits after the rightmost set bit, including that bit itself. ANDing with n clears that rightmost set bit. This repeats until no set bits remain, counting how many were removed.

Why designed this way?

This method was designed to avoid checking every bit individually, reducing steps to the number of set bits. It trades simple iteration for a clever bit manipulation trick, improving speed especially for numbers with few 1s.

n (binary):    1 0 1 1 0 0
n - 1:         1 0 1 0 1 1
AND (&):       1 0 1 0 0 0
Result: rightmost set bit cleared

Myth Busters - 3 Common Misconceptions

Quick: Does n & (n - 1) always clear the leftmost set bit? Commit yes or no.

Common Belief: The operation n & (n - 1) clears the leftmost set bit.

Reality: It actually clears the rightmost set bit, the one closest to the least significant bit.

Why it matters: Misunderstanding which bit is cleared leads to incorrect reasoning about the algorithm's behavior and bugs in bit manipulation code.

Quick: Is Brian Kernighan's algorithm always faster than checking all bits? Commit yes or no.

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

Reality: It is faster when the number has few set bits but can be slower than table lookup or hardware instructions for dense numbers.

Why it matters: Assuming it is always fastest can cause inefficient code in performance-critical systems.

Quick: Does the algorithm work correctly for zero input? Commit yes or no.

Common Belief: The algorithm fails or loops infinitely if the input is zero.

Reality: It correctly returns zero immediately because the loop condition n != 0 fails at start.

Why it matters: Knowing this prevents unnecessary checks or special cases in code.

Expert Zone

1

The algorithm's runtime depends on the number of set bits, not the total bit length, making it input-sensitive.

2

In some architectures, hardware popcount instructions outperform this algorithm, but it remains valuable for portability.

3

Combining this algorithm with parallel processing can count bits in large data sets efficiently.

When NOT to use

Avoid this algorithm when counting bits in very large numbers with many set bits where lookup tables or CPU popcount instructions are faster.

Production Patterns

Used in embedded systems, cryptography, network packet processing, and compression algorithms where quick bit counting is essential and hardware support may be limited.

Connections

Bitwise Operations

Builds-on

Mastering bitwise operations is essential to understand and implement the Brian Kernighan algorithm effectively.

Population Count (Popcount) Instruction

Alternative approach

Knowing hardware popcount instructions helps decide when to use software algorithms like Brian Kernighan versus hardware acceleration.

Error Detection in Communication Systems

Application

Counting set bits is fundamental in parity checks and error detection, showing how this algorithm supports reliable data transmission.

Common Pitfalls

#1 Using n & (n + 1) instead of n & (n - 1) to clear set bits.

Wrong approach:

for n != 0 {
n = n & (n + 1) // wrong operation
count++
}

Correct approach:

for n != 0 {
n = n & (n - 1) // correct operation
count++
}

Root cause:

Confusing the subtraction operation needed to clear the rightmost set bit with addition, which does not have the same effect.

#2 Not handling zero input, causing unnecessary loop or errors.

Wrong approach:

func countSetBits(n uint) int {
count := 0
for {
n = n & (n - 1)
count++
if n == 0 {
break
}
}
return count
}

Correct approach:

func countSetBits(n uint) int {
count := 0
for n != 0 {
n = n & (n - 1)
count++
}
return count
}

Root cause:

Not using the loop condition properly to exit when n becomes zero.

#3 Using signed integers without care, causing unexpected behavior with negative numbers.

Wrong approach:

func countSetBits(n int) int {
count := 0
for n != 0 {
n = n & (n - 1)
count++
}
return count
}

Correct approach:

func countSetBits(n uint) int {
count := 0
for n != 0 {
n = n & (n - 1)
count++
}
return count
}

Root cause:

Signed integers use two's complement, which can cause infinite loops or wrong counts if negative.

Key Takeaways

The Brian Kernighan algorithm counts set bits by repeatedly clearing the rightmost set bit until the number is zero.

It is more efficient than checking every bit, especially when the number has few set bits.

Understanding bitwise AND and subtraction is essential to grasp how the algorithm works.

This algorithm is widely used in systems programming, cryptography, and error detection for its speed and simplicity.

Knowing its limits helps choose the best bit counting method for different scenarios.

Practice

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

easy

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

B. It counts the total number of digits in the binary representation

C. It shifts the number right until it becomes zero and counts the shifts

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 clears the least significant set bit by doing n = n & (n-1) repeatedly.

2. Step 2: Effect of clearing bits

   Each operation removes one '1' bit, counting how many set bits exist until n 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 counts set bits [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax for the Brian Kernighan loop in Go to count set bits of an integer n?

easy

A. while n > 0 { count++; n = n - 1 }

B. for n > 0 { count += n & 1; n = n >> 1 }

C. for n != 0 { count++; n = n & (n - 1) }

D. for i := 0; i < 32; i++ { if n & (1 << i) != 0 { count++ } }

Solution

1. Step 1: Identify the Brian Kernighan loop condition

   The loop runs while n is not zero, clearing the least significant set bit each iteration.

2. Step 2: Confirm the bit clearing operation

   The operation n = n & (n - 1) clears the least significant set bit correctly.

3. Final Answer:

   for n != 0 { count++; n = n & (n - 1) } -> Option C

4. Quick Check:

   Loop with n & (n-1) clears bits [OK]

Hint: Use n = n & (n-1) inside for loop [OK]

Common Mistakes:

• Using shift instead of bit clear
• Using while instead of for in Go
• Counting bits by subtracting 1 only

3. What is the output of the following Go code snippet?

func countSetBits(n int) int {
    count := 0
    for n != 0 {
        n = n & (n - 1)
        count++
    }
    return count
}

fmt.Println(countSetBits(13))

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Convert 13 to binary

   13 in binary is 1101, which has three set bits (1s).

2. Step 2: Apply Brian Kernighan algorithm

   Each iteration clears one set bit, so count increments 3 times until n becomes 0.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Binary 1101 has 3 ones [OK]

Hint: Count ones in binary 13 = 3 [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Miscounting binary digits
• Confusing bitwise AND with OR

4. Identify the error in this Go code snippet that tries to count set bits using Brian Kernighan's algorithm:

func countSetBits(n int) int {
    count := 0
    for n > 0 {
        count = count + (n & 1)
        n = n & (n - 1)
    }
    return count
}

medium

A. Using n & 1 to count bits conflicts with n = n & (n - 1) clearing bits

B. Loop condition should be n != 0 instead of n > 0

C. Count variable should be initialized to 1

D. Missing return statement

Solution

1. Step 1: Analyze counting method

   The code adds n & 1 to count, which checks the least significant bit.

2. Step 2: Analyze bit clearing step

   Then it clears the least significant set bit with n = n & (n - 1), which may skip bits.

3. Step 3: Conflict explanation

   Using both methods together causes incorrect counting because n & 1 and clearing bits are mixed incorrectly.

4. Final Answer:

   Using n & 1 to count bits conflicts with n = n & (n - 1) clearing bits -> Option A

5. Quick Check:

   Mixing bit check and clear causes wrong count [OK]

Hint: Use either bit check or bit clear, not both [OK]

Common Mistakes:

• Mixing bitwise AND with bit clearing
• Incorrect loop condition
• Wrong initialization of count

5. Given a list of integers [7, 8, 15, 23], which Go code snippet correctly uses Brian Kernighan's algorithm to return a map of each integer to its count of set bits?

hard

A. func countSetBits(n int) int {
count := 0
for n != 0 {
n = n & (n - 1)
count++
}
return count
}

func mapSetBits(nums []int) map[int]int {
result := make(map[int]int)
for _, num := range nums {
result[countSetBits(num)] = num
}
return result
}

B. func countSetBits(n int) int {
count := 0
for n > 0 {
count += n & 1
n = n >> 1
}
return count
}

func mapSetBits(nums []int) map[int]int {
result := make(map[int]int)
for i := 0; i < len(nums); i++ {
result[i] = countSetBits(nums[i])
}
return result
}

C. func countSetBits(n int) int {
count := 0
for n != 0 {
n = n & (n - 1)
count++
}
return count
}

func mapSetBits(nums []int) map[int]int {
result := make(map[int]int)
for i, num := range nums {
result[i] = countSetBits(num)
}
return result
}

D. func countSetBits(n int) int {
count := 0
for n != 0 {
n = n & (n - 1)
count++
}
return count
}

func mapSetBits(nums []int) map[int]int {
result := make(map[int]int)
for _, num := range nums {
result[num] = countSetBits(num)
}
return result
}

Solution

1. Step 1: Check countSetBits function correctness

   func countSetBits(n int) int { count := 0 for n != 0 { n = n & (n - 1) count++ } return count } func mapSetBits(nums []int) map[int]int { result := make(map[int]int) for _, num := range nums { result[num] = countSetBits(num) } return result } uses Brian Kernighan's algorithm correctly to count set bits.

2. Step 2: Check mapSetBits function logic

   The mapSetBits function correctly maps each number (as key) to its set bit count (as value).

3. Step 3: Verify other options

   func countSetBits(n int) int { count := 0 for n > 0 { count += n & 1 n = n >> 1 } return count } func mapSetBits(nums []int) map[int]int { result := make(map[int]int) for i := 0; i < len(nums); i++ { result[i] = countSetBits(nums[i]) } return result } uses shift method and wrong map keys; func countSetBits(n int) int { count := 0 for n != 0 { n = n & (n - 1) count++ } return count } func mapSetBits(nums []int) map[int]int { result := make(map[int]int) for i, num := range nums { result[i] = countSetBits(num) } return result } uses index as key; func countSetBits(n int) int { count := 0 for n != 0 { n = n & (n - 1) count++ } return count } func mapSetBits(nums []int) map[int]int { result := make(map[int]int) for _, num := range nums { result[countSetBits(num)] = num } return result } reverses key and value.

4. Final Answer:

   The code that maps num to countSetBits(num) -> Option D

5. Quick Check:

   Map keys are numbers, values are counts [OK]

Hint: Map number to countSetBits result using correct keys [OK]

Common Mistakes:

• Using index as map key instead of number
• Swapping keys and values in map
• Using shift method instead of Brian Kernighan