Number of 1 Bits
EasyBit manipulation
Given an unsigned 32-bit integer n, return how many of its 32 bits are 1.
JavaScript has no unsigned 32-bit type, so the page passes n as an ordinary number from 0 to 4294967295 (2³² − 1). The bitwise operators treat numbers as signed 32-bit: >> copies the sign bit in from the left, while >>> shifts in zeros.
Examples
Input: n = 13 Output: 3
13 is 1101 in binary: three 1 bits.
Input: n = 4294967295 Output: 32
2³² − 1 has all thirty-two bits set.
Constraints
0 ≤ n ≤ 4294967295nis a whole number.
Stuck?
Hint 1
Look at the lowest bit with n & 1, then shift the next bit down. Pick the shift that does not drag the sign bit along.
Hint 2
A neater trick: n & (n - 1) clears the lowest 1 bit, so count how many times you can do that before n reaches 0.
The idea
Read the bits one at a time from the bottom: n & 1 is the lowest bit, and a shift right brings the next one down. The care needed is in the shift. A number from 2³¹ up has its top bit set, which the bitwise operators read as a minus sign, so the shift has to fill in zeros.
Time O(1): at most 32 stepsExtra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
count adds up the 1 bits found so far.
function hammingWeight(n) { let count = 0; while (n !== 0) { count += n & 1; n >>>= 1; } return count;}The trap
>> keeps the sign: it copies the top bit in from the left. A number from 2³¹ up has its top bit set, so after the first shift it reads as negative, n > 0 turns false, and the loop stops with most of the bits uncounted. Smaller numbers never set the top bit, so they all come out right.
function hammingWeight(n) { let count = 0; while (n > 0) { count += n & 1; n >>= 1; // signed shift: a set top bit makes n negative and stops the loop } return count;}