Count Set Bits Brian Kernighan Algorithm in DSA Javascript - 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 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 large numbers.

Why it matters

Without an efficient way to count set bits, programs that rely on bit operations would be slow and waste resources. This algorithm helps in tasks like error detection, cryptography, and graphics where bit manipulation is common. It makes software faster and more efficient, saving time and energy.

Where it fits

Before learning this, you should understand binary numbers and basic bitwise operations like AND and subtraction. After mastering 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 (1s) and unlit candles (0s). Instead of checking each candle one by one, you blow out the rightmost lit candle each time and count how many you blow out until none are left.

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

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn how numbers are represented in binary using 0s and 1s.

Every number can be shown as a series of bits (0s and 1s). For example, the number 5 in binary is 101, which means 1*2^2 + 0*2^1 + 1*2^0 = 5. Each bit position represents a power of two.

Result

You can convert any decimal number to binary and understand its bit pattern.

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

2

Foundation

Basics of Bitwise AND Operation

Concept: Learn how the AND operation compares bits and returns 1 only if both bits are 1.

Bitwise AND compares two bits: 1 & 1 = 1, otherwise 0. For example, 6 (110) & 3 (011) = 2 (010). This operation helps isolate bits and is key to the Brian Kernighan algorithm.

Result

You can predict the result of AND between two binary numbers.

Knowing how AND works lets you understand how bits can be turned off or checked efficiently.

3

Intermediate

Naive Method to Count Set Bits

🤔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.

You can check each bit by shifting the number right and testing the last bit with AND 1. For example, for number 5 (101), check bits one by one: 1, 0, 1, total 2 set bits.

Result

This method works but takes time proportional to the number of bits.

Understanding the naive method shows why a faster approach like Brian Kernighan's is valuable.

4

Intermediate

Brian Kernighan Algorithm Introduction

🤔Before reading on: do you think subtracting 1 from a number changes all bits or just some? Commit to your answer.

Concept: Using n & (n-1) to remove the rightmost set bit.

Subtracting 1 flips bits from right to left until it hits the first set bit. ANDing n with n-1 removes that rightmost set bit. Repeat until n becomes zero, counting how many times you do this.

Result

Each iteration removes one set bit, so the count equals the number of set bits.

This trick skips zero bits and jumps directly between set bits, making counting faster.

5

Advanced

Implementing Brian Kernighan in JavaScript

🤔Before reading on: do you think the loop runs as many times as the number's bit length or the count of set bits? Commit to your answer.

Concept: Writing code that uses the algorithm to count set bits efficiently.

function countSetBits(n) { let count = 0; while (n !== 0) { n = n & (n - 1); count++; } return count; } Example: countSetBits(22) returns 3 because 22 in binary is 10110 with three 1s.

Result

The function returns the number of set bits quickly, running only as many times as there are 1s.

Knowing the loop runs only for set bits explains why this method is faster than checking every bit.

6

Expert

Performance and Use Cases of Brian Kernighan Algorithm

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

Concept: Understanding when and why this algorithm is preferred in real systems.

This algorithm is efficient for sparse numbers with few set bits. For dense numbers, other methods like lookup tables or built-in CPU instructions may be faster. It is widely used in embedded systems and low-level programming where performance and memory are critical.

Result

You can choose the best bit counting method based on the problem context.

Knowing the algorithm's strengths and limits helps you write optimal code in different scenarios.

Under the Hood

The algorithm works by exploiting how subtracting 1 flips bits from the rightmost set bit to the end. When you do n & (n-1), it clears that rightmost set bit. This reduces the number of iterations to the count of set bits instead of total bits.

Why designed this way?

Brian Kernighan designed this to optimize bit counting by avoiding checking every bit. Earlier methods were slower and less efficient. This approach balances simplicity and speed without extra memory.

Start: n = 0b10110 (22)
  ├─ Subtract 1: 0b10101 (21)
  ├─ AND: 0b10110 & 0b10101 = 0b10100 (20)
  ├─ Subtract 1: 0b10011 (19)
  ├─ AND: 0b10100 & 0b10011 = 0b10000 (16)
  ├─ Subtract 1: 0b01111 (15)
  ├─ AND: 0b10000 & 0b01111 = 0b00000 (0)
End: count = 3

Myth Busters - 3 Common Misconceptions

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

Common Belief: Many think n & (n-1) removes the leftmost set bit.

Reality: It actually removes the rightmost set bit.

Why it matters: Misunderstanding this leads to incorrect bit manipulation and bugs in algorithms relying on this trick.

Quick: Is Brian Kernighan's algorithm always faster than built-in CPU instructions? Commit yes or no.

Common Belief: Some believe this algorithm is the fastest way to count bits in all cases.

Reality: Modern CPUs have special instructions that count bits faster than this algorithm.

Why it matters: Ignoring hardware capabilities can cause suboptimal performance in critical applications.

Quick: Does this algorithm work correctly for negative numbers in JavaScript? Commit yes or no.

Common Belief: People often assume it works the same for negative numbers.

Reality: JavaScript uses signed 32-bit integers, so negative numbers have infinite leading 1s in two's complement, causing incorrect counts.

Why it matters: Using this algorithm without handling negatives can cause infinite loops or wrong results.

Expert Zone

1

The algorithm's runtime depends on the number of set bits, not the total bit length, making it efficient for sparse bit patterns.

2

In JavaScript, bitwise operations work on 32-bit signed integers, so large numbers or negatives need special handling to avoid errors.

3

Combining this algorithm with lookup tables for small chunks can optimize counting in dense bit patterns.

When NOT to use

Avoid this algorithm when working with negative numbers in JavaScript without masking or when hardware supports faster built-in bit counting instructions. For dense bit patterns, consider lookup tables or parallel bit counting methods.

Production Patterns

Used in embedded systems, graphics programming, and cryptography where fast bit counting is critical. Often combined with other bit tricks for performance. Also used in competitive programming for efficient solutions.

Connections

Bitwise Operations

Builds-on

Understanding bitwise AND and subtraction is essential to grasp how the algorithm removes set bits efficiently.

Two's Complement Representation

Related concept

Knowing how negative numbers are stored helps avoid pitfalls when applying this algorithm in languages like JavaScript.

Error Detection in Communication

Application domain

Counting set bits quickly is crucial in parity checks and error detection codes, showing how this algorithm impacts real-world systems.

Common Pitfalls

#1 Using the algorithm directly on negative numbers in JavaScript.

Wrong approach:

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

countSetBits(-3); // Infinite loop or wrong result

Correct approach:

function countSetBits(n) {
n = n >>> 0; // Convert to unsigned 32-bit
let count = 0;
while (n !== 0) {
n = n & (n - 1);
count++;
}
return count;
}

countSetBits(-3); // Correctly returns 31

Root cause:

JavaScript bitwise operators treat numbers as signed 32-bit, so negative numbers have infinite leading 1s causing the loop to never end.

#2 Assuming the algorithm removes the leftmost set bit.

Wrong approach:

Using n & (n-1) expecting it to clear the highest set bit first.

Correct approach:

Understanding that n & (n-1) clears the rightmost set bit, so use accordingly.

Root cause:

Misunderstanding how subtraction affects binary bits leads to wrong assumptions about which bit is cleared.

#3 Using this algorithm for very dense numbers expecting it to be fastest.

Wrong approach:

Applying Brian Kernighan's method on numbers with many set bits without considering alternatives.

Correct approach:

Use lookup tables or hardware instructions for dense bit patterns for better performance.

Root cause:

Not recognizing that the algorithm's speed depends on the number of set bits, so dense numbers cause many iterations.

Key Takeaways

Brian Kernighan's algorithm counts set bits by repeatedly clearing the rightmost set bit using n & (n-1).

This method is faster than checking each bit because it only loops as many times as there are set bits.

Understanding binary representation and bitwise operations is essential to grasp this algorithm.

In JavaScript, special care is needed for negative numbers due to signed 32-bit integer behavior.

Choosing the right bit counting method depends on the number's bit density and available hardware features.

Practice

1. What does the Brian Kernighan algorithm do when counting set bits in a number?

easy

A. It converts the number to a string and counts characters

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

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

D. It shifts the number to the right and counts zeros

Solution

1. Step 1: Understand the algorithm's main operation

   The 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 set bit, counting how many times this happens gives the total set bits.

3. Final Answer:

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

4. Quick Check:

   Clearing bits counts set bits [OK]

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

Common Mistakes:

• Counting total digits instead of set bits
• Counting zeros instead of ones
• Using string length instead of bit operations

2. Which of the following is the correct syntax to clear the least significant set bit in JavaScript using Brian Kernighan's method?

easy

A. n = n | (n - 1);

B. n = n & (n - 1);

C. n = n & (n + 1);

D. n = n ^ (n - 1);

Solution

1. Step 1: Identify the bit clearing operation

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

2. Step 2: Verify other options

   Other options do not clear the least significant set bit correctly.

3. Final Answer:

   n = n & (n - 1); -> Option B

4. Quick Check:

   Use AND with (n-1) to clear bit [OK]

Hint: Use n & (n-1) to clear least set bit [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Adding instead of subtracting 1
• Confusing bitwise operators

3. What is the output of the following JavaScript code?

function countSetBits(n) {
  let count = 0;
  while (n > 0) {
    n = n & (n - 1);
    count++;
  }
  return count;
}
console.log(countSetBits(13));

medium

A. 3

B. 2

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's algorithm

   Each loop clears one set bit, so count increments 3 times before n becomes 0.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   13 (1101) has 3 set bits [OK]

Hint: Count set bits by clearing one bit each loop [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Miscounting binary representation
• Off-by-one errors in loop

4. Identify the error in the following code snippet that uses Brian Kernighan's algorithm:

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

medium

A. Not initializing count to 1

B. Using while loop instead of for loop

C. Missing return statement

D. Using n & (n + 1) instead of n & (n - 1)

Solution

1. Step 1: Check the bit clearing operation

   The code uses n = n & (n + 1), which does not clear the least significant set bit correctly.

2. Step 2: Correct operation

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

3. Final Answer:

   Using n & (n + 1) instead of n & (n - 1) -> Option D

4. Quick Check:

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

Hint: Use n & (n-1), not n & (n+1) [OK]

Common Mistakes:

• Using n & (n + 1) which is incorrect
• Confusing loop types
• Forgetting to return count

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

const arr = [3, 5, 7];
// Choose the correct code to count all set bits

A) let total = 0;
for(let n of arr) {
  while(n > 0) {
    n = n & (n - 1);
    total++;
  }
}
console.log(total);

B) let total = 0;
for(let n of arr) {
  total += n.toString(2).length;
}
console.log(total);

C) let total = 0;
for(let n of arr) {
  while(n > 0) {
    n = n | (n - 1);
    total++;
  }
}
console.log(total);

D) let total = 0;
for(let n of arr) {
  total += n & (n - 1);
}
console.log(total);

hard

A. Correctly counts set bits using Brian Kernighan's method

B. Counts total binary digits, not set bits

C. Uses OR instead of AND, incorrect bit clearing

D. Adds bitwise AND result directly, incorrect counting

Solution

1. Step 1: Identify the correct implementation

   The implementation using while(n > 0) { n = n & (n - 1); total++; } correctly applies Brian Kernighan's algorithm by clearing the least significant set bit repeatedly for each array element and incrementing the total count each time.

2. Step 2: Eliminate incorrect options

   The option using n.toString(2).length counts all bits including zeros; using n | (n - 1) does not clear set bits correctly; adding n & (n - 1) directly does not count the number of set bits.

3. Final Answer:

   Correctly counts set bits using Brian Kernighan's method -> Option A

4. Quick Check:

   Clear bits and count in loop [OK]

Hint: Loop clearing bits per number to sum counts [OK]

Common Mistakes:

• Counting total binary length instead of set bits
• Using OR instead of AND for clearing bits
• Adding bitwise results instead of counts