Q49: Number of 1 Bits (Hamming Weight)
Write a function that takes an unsigned integer and returns the number of '1' bits it has (Hamming Weight).
Brian Kernighan Bit Clearing Algorithm
function hammingWeight(n) {
let count = 0;
while (n !== 0) {
n = n & (n - 1);
count++;
}
return count;
}
console.log(hammingWeight(11)); // 3 (binary 1011 has three 1s)💡 Evaluating
n & (n - 1) drops the rightmost set bit (1) to 0 in each step, incrementing count until all set bits are cleared.Key Takeaways
- Brian Kernighan's bit manipulation trick
n = n & (n - 1)clears the lowest set bit in $O(1)$ operations per set bit. - Loop iterations match the exact count of set bits rather than iterating all 32 bit positions.
Knowledge Check
What effect does executing the bitwise operation `n & (n - 1)` have on binary integer `n`?