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

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→Done

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 Go

func countSetBits(n int) int {
    count := 0
    for 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	Check n != 0	00001011	11	0	11 != 0, continue
3	Remove rightmost set bit: n = n & (n-1)	00001011 & 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: n = n & (n-1)	00001010 & 00001001	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: n = n & (n-1)	00001000 & 00000111	8 & 7 = 0	2	n becomes 0 (binary 0000)
10	Increment count	00000000	0	3	Count incremented to 3
11	Check n != 0	00000000	0	3	0 == 0, stop loop
12	Return count	-	-	3	Total set bits = 3

💡 Loop stops when n becomes 0, count holds the number of set bits.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
n (decimal)	11	10	8	0	0
n (binary)	00001011	00001010	00001000	00000000	00000000
count	0	1	2	3	3

Key Moments - 3 Insights

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

Because n & (n-1) clears the rightmost 1 bit in n, reducing the number of set bits by one each time (see steps 3, 6, 9 in execution_table).

Why does the loop stop when n becomes zero?

When n is zero, there are no set bits left to count, so the condition n != 0 fails and the loop ends (see step 11).

How does the count variable relate to the number of set bits?

Count increments each time a set bit is removed, so at the end it equals the total number of set bits in the original number (see steps 4, 7, 10).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of n in decimal?

A 8

B 9

C 10

D 11

💡 Hint

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

At which step does the loop condition n != 0 become false?

A Step 9

B Step 11

C Step 10

D Step 12

💡 Hint

Look for the step where 'Check n != 0' results in stopping the loop in execution_table.

If the input number was 15 (binary 1111), how many times would the count increment?

A 3

B 4

C 5

D 1

💡 Hint

Count increments once per set bit removed; 15 has four set bits (1111).

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 as total set bits
This method 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 an integer. Starting with the number n, the algorithm checks if n is not zero. If true, it removes the rightmost set bit by performing n = n & (n-1), then increments the count. This repeats until n becomes zero. The execution table traces each step with the binary and decimal values of n, the count, and the operation performed. The variable tracker shows how n and count change after each removal of a set bit. Key moments clarify why the bit removal works, why the loop stops, and how count relates to set bits. The quiz tests understanding of the steps and the algorithm's behavior with different inputs.

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