Count Set Bits Brian Kernighan Algorithm in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Brian Kernighan's Set Bits Count for 13

What is the output of the following Go code that counts set bits using Brian Kernighan's algorithm for the number 13?

DSA Go

package main
import "fmt"
func countSetBits(n int) int {
    count := 0
    for n > 0 {
        n = n & (n - 1)
        count++
    }
    return count
}
func main() {
    fmt.Println(countSetBits(13))
}

A 3

B 2

C 4

D 1

💡 Hint

Think about how many 1s are in the binary form of 13 (1101).

The binary form of 13 is 1101, which has three 1s. Brian Kernighan's algorithm counts these by repeatedly turning off the rightmost set bit until the number becomes zero.

🧠 Conceptual

intermediate

Why does Brian Kernighan's Algorithm Work?

Why does the operation n = n & (n - 1) reduce the number of set bits by one in Brian Kernighan's algorithm?

A It flips all bits from 0 to 1 and 1 to 0.

B It shifts all bits to the right by one position.

C It sets all bits to zero except the leftmost bit.

D It clears the rightmost set bit by turning it to zero.

💡 Hint

Consider what happens when you subtract 1 from a number in binary.

Subtracting 1 flips the rightmost set bit and all bits to its right. ANDing with the original number clears that rightmost set bit, reducing the count by one.

❓ Predict Output

advanced

Count Set Bits for 0 and 1 Using Brian Kernighan's Algorithm

What is the output of the following Go code when counting set bits for 0 and 1?

DSA Go

package main
import "fmt"
func countSetBits(n int) int {
    count := 0
    for n > 0 {
        n = n & (n - 1)
        count++
    }
    return count
}
func main() {
    fmt.Println(countSetBits(0))
    fmt.Println(countSetBits(1))
}

A 0\n0

B 1\n0

C 0\n1

D 1\n1

💡 Hint

Remember that 0 has no set bits and 1 has exactly one set bit.

0 has no bits set, so count is 0. 1 has one bit set, so count is 1.

🔧 Debug

advanced

Identify the Error in Brian Kernighan's Algorithm Implementation

What error will the following Go code produce when trying to count set bits using Brian Kernighan's algorithm?

DSA Go

package main
import "fmt"
func countSetBits(n int) int {
    count := 0
    for n >= 0 {
        n = n & (n - 1)
        count++
    }
    return count
}
func main() {
    fmt.Println(countSetBits(5))
}

A Returns 0 immediately

B Infinite loop

C Runtime panic: integer overflow

D Syntax error

💡 Hint

Check the loop condition and what happens when n becomes zero.

The loop condition n >= 0 never becomes false for signed integers because when n reaches 0, n & (n-1) becomes 0 & -1 which is 0, so n stays 0 and the loop never ends.

🧠 Conceptual

expert

Time Complexity of Brian Kernighan's Algorithm

What is the time complexity of Brian Kernighan's algorithm for counting set bits in an integer n?

A O(number of set bits in n)

B O(log n)

C O(n)

D O(1)

💡 Hint

The loop runs once for each set bit.

Brian Kernighan's algorithm runs in time proportional to the number of set bits because each iteration clears one set bit.

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