Count Set Bits Brian Kernighan Algorithm in DSA Java - 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 clever way to count these 1s quickly by removing the rightmost 1 bit one by one. Instead of checking every bit, it jumps directly to the next set bit. This makes it faster than simple methods that look at each bit individually.

Why it matters

Counting set bits is important in many computer tasks like error detection, cryptography, and optimization problems. Without an efficient way to count bits, programs would run slower and waste resources. The Brian Kernighan algorithm helps computers do this counting quickly, saving time and energy especially when working with large numbers or many calculations.

Where it fits

Before learning this, you should understand binary numbers and basic bitwise operations like AND and subtraction. After this, you can explore more advanced bit manipulation tricks and algorithms that use set bits for solving complex problems efficiently.

Mental Model

Core Idea

Each step of the Brian Kernighan algorithm removes the rightmost 1 bit from the number until none remain, counting how many times this happens.

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 all candles are out, and the count tells you how many candles were lit.

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

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn what binary numbers are and how they represent values using 0s and 1s.

Binary numbers use only two digits: 0 and 1. Each position represents a power of 2, starting from the right with 2^0. For example, the binary number 1011 means 1*8 + 0*4 + 1*2 + 1*1 = 11 in decimal. The 1s in binary are called set bits.

Result

You can read and write numbers in binary and identify which bits are set (1) or unset (0).

Understanding binary is essential because the algorithm works directly on the binary form of numbers.

2

Foundation

Basics of Bitwise Operations

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

Bitwise AND compares two binary numbers bit by bit and returns 1 only if both bits are 1. For example, 1010 & 1001 = 1000. Subtraction in binary works like decimal but with borrowing. The algorithm uses n & (n-1) to remove the rightmost set bit.

Result

You can perform bitwise AND and understand how subtracting 1 affects binary numbers.

Knowing how n & (n-1) clears the rightmost set bit is the key to the algorithm.

3

Intermediate

How Brian Kernighan Algorithm Works

🤔Before reading on: do you think the algorithm checks every bit or skips some bits? Commit to your answer.

Concept: The algorithm repeatedly removes the rightmost set bit until the number becomes zero, counting how many times this happens.

Start with a number n. While n is not zero, do n = n & (n-1). Each operation removes one set bit. Count how many times this loop runs. This count is the number of set bits in n.

Result

For example, for n=13 (binary 1101), the algorithm runs 3 times, so there are 3 set bits.

This method is faster because it only loops as many times as there are set bits, not total bits.

4

Intermediate

Implementing in Java

🤔Before reading on: do you think the code needs to check all bits or just loop until zero? Commit to your answer.

Concept: Write a Java method that uses the Brian Kernighan algorithm to count set bits.

public class SetBitsCounter { public static int countSetBits(int n) { int count = 0; while (n != 0) { n = n & (n - 1); // remove rightmost set bit count++; } return count; } public static void main(String[] args) { int number = 29; // binary 11101 System.out.println("Set bits count: " + countSetBits(number)); } }

Result

Output: Set bits count: 4

Implementing the algorithm shows how simple and efficient it is in practice.

5

Advanced

Performance Comparison with Naive Method

🤔Before reading on: do you think the Brian Kernighan algorithm is faster or slower than checking each bit? Commit to your answer.

Concept: Compare the Brian Kernighan algorithm with a naive method that checks every bit one by one.

Naive method loops through all bits (usually 32 or 64) and checks if each bit is set. Brian Kernighan loops only as many times as there are set bits. For numbers with few set bits, Brian Kernighan is much faster. For numbers with many set bits, performance is similar but never worse.

Result

Brian Kernighan algorithm runs in O(k) time where k is number of set bits, naive runs in O(n) where n is total bits.

Understanding time complexity helps choose the right method for different scenarios.

6

Expert

Using Brian Kernighan in Bit Manipulation Problems

🤔Before reading on: do you think this algorithm can help solve other bit problems beyond counting? Commit to your answer.

Concept: The algorithm's technique of removing set bits is useful in many bit manipulation problems like finding parity, subsets, or optimizing bit operations.

For example, to find parity (whether number of set bits is odd or even), you can use Brian Kernighan to count bits and then check if count is odd. It also helps in generating subsets by iterating over set bits efficiently.

Result

This approach reduces complexity and improves performance in many bit-related algorithms.

Knowing this algorithm unlocks a powerful toolset for solving complex bit manipulation challenges.

Under the Hood

The algorithm works by exploiting the property that subtracting 1 from a number flips all bits after the rightmost set bit, including that bit itself. When you do n & (n-1), it clears the rightmost set bit because that bit changes from 1 to 0 and all bits after it become 1 in (n-1), so ANDing clears it. This process repeats until no set bits remain.

Why designed this way?

This method was designed to avoid checking every bit individually, which is slow. By directly jumping to the next set bit, it reduces the number of operations. Alternatives like looping through all bits were simpler but inefficient, especially for sparse numbers.

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

Repeat:
10100 & 10011 = 10000
10000 & 01111 = 00000

Loop ends when n becomes 0.

Myth Busters - 3 Common Misconceptions

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

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

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

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

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

Common Belief: Subtracting 1 from a number always clears the rightmost set bit.

Reality: Subtracting 1 flips bits after the rightmost set bit, but the key is that n & (n-1) clears that bit; subtraction alone doesn't clear it.

Why it matters: Misunderstanding this can cause confusion when trying to implement or explain the algorithm.

Quick: Is this algorithm slower for numbers with many set bits? Commit to yes or no.

Common Belief: The algorithm is slower than naive methods when many bits are set.

Reality: It is never slower; at worst, it matches naive method speed but usually faster.

Why it matters: This misconception might prevent using the algorithm in performance-critical code.

Expert Zone

1

The algorithm's efficiency depends on the density of set bits, making it especially powerful for sparse bit patterns.

2

In some architectures, hardware instructions exist that perform similar operations even faster, but understanding this algorithm helps in software fallback scenarios.

3

Combining this algorithm with lookup tables or parallel bit counting can optimize performance further in large-scale applications.

When NOT to use

Avoid using this algorithm when you need to process all bits regardless of their value, such as when you must examine unset bits too. In such cases, a simple loop over all bits or built-in functions like Integer.bitCount() in Java might be preferable.

Production Patterns

Used in low-level system code, cryptography, compression algorithms, and graphics where bit manipulation speed is critical. Also common in competitive programming and interview problems to quickly count bits or optimize bitmask operations.

Connections

Hamming Weight

Brian Kernighan algorithm is a method to compute the Hamming weight (number of set bits) of a binary number.

Understanding this algorithm deepens comprehension of Hamming weight, which is fundamental in error detection and coding theory.

Parity Checking

The algorithm helps efficiently determine parity by counting set bits and checking if the count is odd or even.

Knowing this connection shows how bit counting algorithms support data integrity checks in communication systems.

Population Ecology (Biology)

Counting set bits is analogous to counting individuals in a population; removing one set bit is like removing one individual from a group.

This cross-domain link highlights how counting discrete units efficiently is a universal problem across fields.

Common Pitfalls

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

Wrong approach:

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

Correct approach:

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

Root cause:

Not knowing that n & (n-1) clears the rightmost set bit leads to inefficient bit counting.

#2 Assuming subtraction alone clears the rightmost set bit.

Wrong approach:

n = n - 1; // expecting rightmost set bit cleared

Correct approach:

n = n & (n - 1); // actually clears rightmost set bit

Root cause:

Confusing subtraction effect with bitwise AND operation causes incorrect implementation.

#3 Not handling negative numbers correctly in signed integer representation.

Wrong approach:

Using the algorithm directly on negative numbers without considering two's complement.

Correct approach:

Use unsigned integers or mask the number to avoid infinite loops with negative values.

Root cause:

Misunderstanding how signed integers are represented and how bitwise operations behave on them.

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 because it loops only as many times as there are set bits.

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

This algorithm is widely used in performance-critical applications involving bit manipulation.

Misconceptions about how subtraction and bitwise operations interact can lead to incorrect implementations.

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