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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Brian Kernighan's Set Bits Count

What is the output of the following Java code that counts set bits using Brian Kernighan's algorithm?

DSA Java

public class Main {
    public static int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countSetBits(29));
    }
}

A 2

B 3

C 4

D 5

💡 Hint

Count how many times the loop runs by removing the rightmost set bit each time.

29 in binary is 11101 which has 4 set bits. Brian Kernighan's algorithm removes one set bit per iteration, so the count is 4.

❓ Predict Output

intermediate

Result of Counting Set Bits for Zero

What will be the output when the input number is zero?

DSA Java

public class Main {
    public static int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countSetBits(0));
    }
}

A -1

B 1

C Exception thrown

D 0

💡 Hint

Zero has no set bits in binary.

Since 0 has no set bits, the loop never runs and count remains 0.

🔧 Debug

advanced

Identify the Error in Set Bits Counting Code

What error will occur when running this code to count set bits?

DSA Java

public class Main {
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n + 1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countSetBits(2));
    }
}

A Infinite loop

B Correct output 1

C Compilation error

D Returns 0

💡 Hint

Check the bitwise operation inside the loop and how it affects n.

Using n & (n + 1) does not clear the rightmost set bit and can cause n to never become zero, leading to an infinite loop.

🧠 Conceptual

advanced

Why Brian Kernighan's Algorithm is Efficient

Why is Brian Kernighan's algorithm more efficient than checking each bit individually to count set bits?

A It only loops as many times as there are set bits, not total bits

B It converts the number to a string and counts '1's

C It uses recursion to speed up counting

D It uses a built-in CPU instruction for counting bits

💡 Hint

Think about how many times the loop runs compared to the number of bits in the number.

Brian Kernighan's algorithm reduces the number by removing one set bit each iteration, so it runs only as many times as there are set bits, making it faster than checking all bits.

❓ Predict Output

expert

Output of Counting Set Bits for Negative Number

What is the output of the following code when counting set bits of -1 in Java?

DSA Java

public class Main {
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countSetBits(-1));
    }
}

A Infinite loop

B 32

C 0

D Throws exception

💡 Hint

Consider how negative numbers are represented in Java (32-bit two's complement).

-1 in Java is represented as all 32 bits set to 1 in two's complement, so the count of set bits is 32.

Practice

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

easy

A. It counts the total number of digits in the integer

B. It converts the number to binary string and counts '0's

C. It shifts the bits to the right without changing the number

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

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 clearing reduces the number of set bits by one until the number becomes zero.

3. Final Answer:

   It repeatedly clears the least significant set bit until the number becomes zero -> Option D

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 digits instead of set bits
• Shifting bits without counting
• Counting zeros instead of ones

2. Which of the following Java code snippets correctly implements the Brian Kernighan algorithm to count set bits?

easy

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

B. int count = 0; while(n > 0) { n = n >> 1; count++; }

C. int count = 0; while(n > 0) { n = n & (n - 1); count++; }

D. int count = 0; while(n > 0) { n = n | (n - 1); count++; }

Solution

1. Step 1: Identify the correct bit clearing operation

   The Brian Kernighan algorithm uses n = n & (n - 1) to clear the least significant set bit.

2. Step 2: Verify the loop and count increment

   Loop runs while n > 0 and increments count each time a bit is cleared.

3. Final Answer:

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

4. Quick Check:

   Use n = n & (n - 1) to clear bits [OK]

Hint: Use n = n & (n - 1) inside loop to count bits [OK]

Common Mistakes:

• Using right shift instead of bit clearing
• Using bitwise OR instead of AND
• Counting bits by checking each bit manually

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

int n = 13; // binary 1101
int count = 0;
while (n > 0) {
  n = n & (n - 1);
  count++;
}
System.out.println(count);

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Convert 13 to binary and count set bits

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

2. Step 2: Apply Brian Kernighan algorithm iterations

   Each iteration clears one set bit: - Iteration 1: 1101 & 1100 = 1100 - Iteration 2: 1100 & 1011 = 1000 - Iteration 3: 1000 & 0111 = 0000 Loop runs 3 times, so count = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Number of set bits in 13 = 3 [OK]

Hint: Count set bits in binary 1101 = 3 [OK]

Common Mistakes:

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

4. Identify the error in the following Java code that attempts to count set bits using Brian Kernighan's algorithm:

int countSetBits(int n) {
  int count = 0;
  while (n != 0) {
    n = n & (n + 1);
    count++;
  }
  return count;
}

medium

A. Using n + 1 instead of n - 1 in bit clearing step

B. Incorrect loop condition should be n > 0

C. Missing initialization of count variable

D. Using bitwise OR instead of AND

Solution

1. Step 1: Check the bit clearing operation

   The correct operation to clear the least significant set bit is n = n & (n - 1), not n & (n + 1).

2. Step 2: Effect of incorrect operation

   Using n + 1 does not clear the least significant set bit and leads to incorrect counting or infinite loop.

3. Final Answer:

   Using n + 1 instead of n - 1 in bit clearing step -> Option A

4. Quick Check:

   Use n & (n - 1) to clear bits [OK]

Hint: Always use n & (n - 1) to clear bits [OK]

Common Mistakes:

• Using n + 1 instead of n - 1
• Wrong loop condition causing infinite loop
• Confusing AND with OR operators

5. Given an array of integers, which Java method correctly uses Brian Kernighan's algorithm to return the total count of set bits in all elements?

int totalSetBits(int[] arr) {
  int total = 0;
  for (int num : arr) {
    while (num > 0) {
      num = num & (num - 1);
      total++;
    }
  }
  return total;
}

What is the output of totalSetBits(new int[]{3, 5, 7})?

hard

A. 7

B. 6

C. 8

D. 5

Solution

1. Step 1: Count set bits for each element

   3 (binary 11) has 2 set bits, 5 (binary 101) has 2 set bits, 7 (binary 111) has 3 set bits.

2. Step 2: Sum all set bits

   Total = 2 + 2 + 3 = 7.

3. Step 3: Verify code logic

   The code correctly counts set bits for each number and sums them in total.

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Sum of set bits in 3,5,7 = 7 [OK]

Hint: Sum set bits of each number using Brian Kernighan [OK]

Common Mistakes:

• Miscounting set bits in numbers
• Adding counts incorrectly
• Using wrong bit clearing logic