Number of 1 Bits

Concept

LeetCode #191.
Problem: Write a function that takes the binary representation of an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Input: n = 11
Binary of 11: 0000 1011
Output: 3 (There are three 1s in the binary representation).

The Naive Approach (Bit Shifting)

How do we check if the absolute right-most bit is a 1? We AND it with 1! (n & 1).
Once we check the right-most bit, how do we check the next bit? We physically shift the entire number to the right by 1 position (n = n >>> 1), pushing the next bit into the right-most slot!
We just loop 32 times.

function hammingWeightNaive(n: number): number {
    let count = 0;
    
    // Loop exactly 32 times for a 32-bit integer
    for (let i = 0; i < 32; i++) {
        // Does the right-most bit equal 1?
        if ((n & 1) === 1) {
            count++;
        }
        // Shift the entire binary to the right, ignoring the sign bit
        n = n >>> 1;
    }
    
    return count;
}

The Brian Kernighan Optimization

The naive approach always takes exactly 32 iterations, even if the number is 000...0001. It wastes 31 loops checking empty 0s!

Can we skip the 0s and ONLY jump directly to the 1s?
Yes, using Brian Kernighan’s Algorithm.

The Magic Math: n = n & (n - 1)
If you take a number n, subtract 1 from it, and AND them together, the mathematical result permanently deletes the absolute right-most 1 bit from the number.

Let’s test it on n = 12 (1100).

• n - 1 is 11 (1011).
• 1100 & 1011 = 1000.
• The right-most 1 was flawlessly deleted! The rest of the bits were completely untouched.

We just run a while loop that executes n = n & (n - 1) until the number becomes 0. The number of times the loop runs is exactly equal to the number of 1 bits!

// Time Complexity: O(1) (Technically O(K) where K is the number of 1s. Max 32).
// Space Complexity: O(1)

function hammingWeight(n: number): number {
    let count = 0;
    
    while (n !== 0) {
        // Brian Kernighan's Hack: Delete the right-most 1!
        n = n & (n - 1);
        count++;
    }
    
    return count;
}

Interview Questions

Q: A developer uses .toString(2) to solve this: n.toString(2).split('1').length - 1. Is this acceptable in an interview?
A: It will pass LeetCode, but it is an instant failure in an interview. .toString(2) forces the V8 engine to allocate heap memory, instantiate a string, parse the binary, and .split() creates a brand new array in RAM. You took a problem that runs in a single CPU hardware clock cycle ($O(1)$ space/time) and bloated it with massive memory allocations and string manipulation overhead. Bit manipulation questions are strictly testing your ability to use Bitwise Operators.

Q: Why does Brian Kernighan’s algorithm n = n & (n - 1) work?
A: Think about standard subtraction. When you subtract 1 from a binary number ending in 000, it triggers a “borrow” cascade. It flips all the trailing 0s to 1s, and flips the very first 1 it finds into a 0!
11000 - 1 = 10111.
Notice that the right-most 1 and everything to its right have been perfectly inverted! When you AND the original number against the inverted number, 1 & 0 = 0, so the target 1 and the cascade both mathematically annihilate themselves, deleting the 1.