Count Set Bits Brian Kernighan Algorithm in DSA Typescript - 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 smart 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 until none are left. This makes counting faster and more efficient.

Why it matters

Without efficient bit counting, programs that rely on binary data, like graphics, encryption, or error checking, would run slower and waste resources. The Brian Kernighan algorithm speeds up these tasks, making software more responsive and saving energy. It helps computers handle large data or real-time tasks smoothly.

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 used in competitive programming and system design.

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 representing set bits. Each time you blow out the rightmost lit candle, you count one. You keep blowing out candles until none are left, counting how many were lit in total.

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 - 7 Steps

1

Foundation

Understanding Binary Numbers

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

Every number can be shown in base 2, called binary. For example, decimal 6 is 110 in binary, meaning 1*2^2 + 1*2^1 + 0*2^0. Each position shows if a bit is set (1) or not (0).

Result

You can convert any decimal number to binary and identify which bits are set.

Understanding binary is essential because bit counting works directly on this representation.

2

Foundation

Basics of Bitwise AND Operation

Concept: Learn how the AND operation compares bits of two numbers.

Bitwise AND compares each bit of two numbers. It returns 1 only if both bits are 1, else 0. For example, 110 & 101 = 100.

Result

You can predict the result of AND operations and understand how bits interact.

Knowing AND helps understand how Brian Kernighan's algorithm clears bits efficiently.

3

Intermediate

Naive Set Bit Counting Method

🤔Before reading on: do you think checking every bit one by one is fast or slow? Commit to your answer.

Concept: Counting set bits by checking each bit individually.

Start from the least significant bit, check if it is 1 by ANDing with 1, then right shift the number by 1. Repeat until the number is zero.

Result

This method counts all set bits but takes time proportional to the number of bits in the number.

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 in each step.

Subtracting 1 flips bits from right to left until the first set bit is flipped. ANDing n with n-1 clears the rightmost set bit. Repeat this until n becomes zero, counting steps.

Result

Each iteration removes one set bit, so the loop runs only as many times as there are set bits.

This method is faster because it skips zero bits and jumps directly between set bits.

5

Advanced

Implementing Brian Kernighan in TypeScript

🤔Before reading on: do you think the loop count equals the number of set bits? Commit to your answer.

Concept: Writing a complete function to count set bits using the algorithm.

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

Result

The function returns the exact count of set bits efficiently.

Seeing the code solidifies understanding and shows practical use.

6

Advanced

Time Complexity Analysis

🤔Before reading on: do you think the algorithm runs in time proportional to total bits or set bits? Commit to your answer.

Concept: Analyzing how the algorithm's speed depends on the number of set bits.

Each loop iteration removes one set bit. So if there are k set bits, the loop runs k times. This is faster than checking all bits (which is fixed by number size).

Result

The algorithm runs in O(k) time, where k is the number of set bits.

Knowing this helps choose the right method based on input characteristics.

7

Expert

Surprising Behavior with Zero and Negative Numbers

🤔Before reading on: do you think the algorithm works the same for negative numbers? Commit to your answer.

Concept: Understanding how two's complement and zero affect the algorithm.

For zero, the loop never runs, returning 0. For negative numbers in two's complement, the algorithm counts set bits in their binary form, which includes sign bits. This can lead to unexpected results if not handled carefully.

Result

The algorithm counts set bits in the binary representation, including sign bits for negatives.

Knowing this prevents bugs when using the algorithm with signed integers.

Under the Hood

The algorithm works by exploiting how subtracting 1 flips bits from right to left until the first set bit is cleared. When ANDed with the original number, this clears the rightmost set bit. This process repeats, removing one set bit per iteration until the number becomes zero.

Why designed this way?

Brian Kernighan designed this to avoid checking every bit, which is slow for large numbers. By jumping directly to set bits, it optimizes counting. Alternatives like looping through all bits were simpler but less efficient.

n (binary):  1 0 1 1 0
n-1:         1 0 1 0 1
AND (&):     1 0 1 0 0  ← rightmost set bit cleared
Repeat until n = 0

Myth Busters - 3 Common Misconceptions

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

Common Belief: n & (n-1) clears the leftmost set bit of n.

Reality: It actually clears the rightmost set bit, not the leftmost.

Why it matters: Misunderstanding this leads to incorrect reasoning about how the algorithm works and can cause errors in bit manipulation tasks.

Quick: Does this algorithm run in time proportional to the total number of bits? Commit yes or no.

Common Belief: The algorithm always runs in time proportional to the total number of bits in the number.

Reality: It runs in time proportional to the number of set bits, which can be much less.

Why it matters: This misconception causes people to underestimate the efficiency gain of the algorithm.

Quick: Does the algorithm work the same for negative numbers as positive? Commit yes or no.

Common Belief: The algorithm counts set bits the same way for negative and positive numbers.

Reality: For negative numbers, it counts set bits in two's complement form, including sign bits, which may not be intended.

Why it matters: Ignoring this can cause bugs when counting bits in signed integers.

Expert Zone

1

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

2

In some architectures, hardware instructions exist that perform similar operations even faster, but this algorithm is portable and simple.

3

When used in parallel or vectorized code, the algorithm can be adapted to count bits in multiple numbers simultaneously.

When NOT to use

Avoid using this algorithm when you need to count bits in fixed-width signed integers without handling sign bits properly. Instead, use built-in functions that handle signedness or mask the number first. Also, for very dense bit patterns, a lookup table method might be faster.

Production Patterns

This algorithm is widely used in low-level system code, cryptography, compression algorithms, and graphics processing where fast bit counting is critical. It is also a common interview question to test understanding of bit manipulation.

Connections

Bitwise Operations

Builds-on

Mastering Brian Kernighan's algorithm deepens understanding of bitwise AND and subtraction, which are fundamental to many low-level programming tasks.

Two's Complement Representation

Related concept

Knowing how negative numbers are stored in two's complement helps explain why the algorithm behaves differently with signed integers.

Error Detection Codes (Hamming Weight)

Application

Counting set bits is the same as calculating Hamming weight, which is crucial in error detection and correction in communication systems.

Common Pitfalls

#1 Counting bits by checking all bits even when many are zero.

Wrong approach:

function countBitsNaive(n: number): number {
let count = 0;
for (let i = 0; i < 32; i++) {
if ((n & (1 << i)) !== 0) count++;
}
return count;
}

Correct approach:

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

Root cause:

Not realizing that clearing set bits directly is faster than checking every bit.

#2 Using the algorithm directly on negative numbers without masking.

Wrong approach:

countSetBits(-5); // returns unexpected count including sign bits

Correct approach:

countSetBits(-5 >>> 0); // mask to treat as unsigned

Root cause:

Ignoring two's complement representation and sign extension in negative numbers.

Key Takeaways

Brian Kernighan's algorithm counts set bits by repeatedly clearing the rightmost set bit until the number is zero.

It runs in time proportional to the number of set bits, making it faster than checking every bit individually.

Understanding bitwise AND and subtraction is key to grasping how the algorithm works.

Special care is needed when using the algorithm with negative numbers due to two's complement representation.

This algorithm is a fundamental tool in efficient bit manipulation used in many real-world applications.

Practice

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

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

C. It shifts the number to the right until it becomes zero without checking bits.

D. It adds all bits of the number without any bitwise operation.

Solution

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

   The Brian Kernighan algorithm clears the least significant set bit in each iteration by doing n = n & (n-1).

2. Step 2: Effect of clearing bits

   Each clearing reduces the number of set bits by one until the number becomes zero, counting how many set bits were present.

3. Final Answer:

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

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:

• Confusing bit count with digit count
• Using simple right shifts without bit checks
• Ignoring bitwise AND operation

2. Which of the following is the correct TypeScript syntax to clear the least significant set bit of a number n?

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 bitwise operation to clear least set bit

   The operation n = n & (n - 1) clears the least significant set bit in n.

2. Step 2: Verify other options

   OR, XOR, and addition do not clear the least significant set bit correctly.

3. Final Answer:

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

4. Quick Check:

   AND with (n-1) clears least set bit [OK]

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

Common Mistakes:

• Using OR or XOR instead of AND
• Adding numbers instead of bitwise operations
• Missing parentheses around (n - 1)

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

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

console.log(countSetBits(13));

medium

A. 3

B. 4

C. 2

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 steps

   Each iteration clears one set bit, so count increments 3 times until n becomes 0.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Number of 1s in 1101 = 3 [OK]

Hint: Count 1s in binary using n & (n-1) loop [OK]

Common Mistakes:

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

4. Identify the error in this TypeScript function that tries to count set bits using Brian Kernighan's algorithm:

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

medium

A. Return statement is missing.

B. Using != instead of > in the while condition.

C. Incorrect initialization of count variable.

D. Missing parentheses around (n - 1) in the expression.

Solution

1. Step 1: Analyze the expression inside the loop

   The expression n = n & n - 1 lacks parentheses, so it is evaluated as (n & n) - 1, which is incorrect.

2. Step 2: Correct expression

   It should be n = n & (n - 1) to correctly clear the least significant set bit.

3. Final Answer:

   Missing parentheses around (n - 1) in the expression. -> Option D

4. Quick Check:

   Parentheses ensure correct order of operations [OK]

Hint: Use parentheses: n = n & (n - 1) [OK]

Common Mistakes:

• Using != 0 causing potential infinite loop for negatives
• Assuming both conditions always equivalent
• Operator precedence confusion causing wrong calculation

5. Given an array of numbers [5, 7, 10], which TypeScript code correctly uses Brian Kernighan's algorithm to return an array of their set bit counts?

hard

A. const counts = arr.map(n => {
let count = 0;
while (n > 0) {
n = n >> 1;
count++;
}
return count;
});

B. const counts = arr.map(n => n.toString(2).length);

C. const counts = arr.map(n => {
let count = 0;
while (n > 0) {
n = n & (n - 1);
count++;
}
return count;
});

D. const counts = arr.map(n => {
let count = 0;
for (let i = 0; i < 32; i++) {
if ((n & (1 << i)) !== 0) count++;
}
return count;
});

Solution

1. Step 1: Understand Brian Kernighan's algorithm usage

   const counts = arr.map(n => { let count = 0; while (n > 0) { n = n & (n - 1); count++; } return count; }); uses the correct loop with n = n & (n - 1) to count set bits for each number.

2. Step 2: Check other options for correctness

   const counts = arr.map(n => n.toString(2).length); counts total binary digits, not set bits. const counts = arr.map(n => { let count = 0; while (n > 0) { n = n >> 1; count++; } return count; }); counts total bits by shifting, not set bits. const counts = arr.map(n => { let count = 0; for (let i = 0; i < 32; i++) { if ((n & (1 << i)) !== 0) count++; } return count; }); uses a loop checking each bit, which works but is not Brian Kernighan's algorithm.

3. Final Answer:

   const counts = arr.map(n => { let count = 0; while (n > 0) { n = n & (n - 1); count++; } return count; }); -> Option C

4. Quick Check:

   Use n & (n-1) loop inside map for set bits [OK]

Hint: Use map with n & (n-1) loop for each number [OK]

Common Mistakes:

• Counting binary string length instead of set bits
• Using right shift without bit check
• Confusing bitwise loop with simple iteration