Math & Bits · 088Easy
Number of 1 Bits
Write a function that takes an unsigned integer and returns its Hamming weight: the number of 1 bits in its binary representation.
Constraints
- The input is a 32-bit unsigned integer.
Examples
hammingWeight(11) -> 3 // 1011 hammingWeight(128) -> 1 // 10000000 hammingWeight(4294967293) -> 31 hammingWeight(0) -> 0 // no bits set hammingWeight(2147483648) -> 1 // only the sign bit, 2^31 hammingWeight(4294967295) -> 32 // all 32 bits set
Edge cases
- Zero has weight 0.
- In JS, bitwise operators coerce to a SIGNED 32-bit integer.
- All-ones input gives 32.
- FOLLOW-UP
- If this function is called many times, how would you optimize it?
Show the target complexity (spoiler)
- Naive
- O(32) time — shift through all 32 positions regardless of how few bits are set.
- Target
- O(number of set bits) time — n &= (n - 1) clears the lowest set bit each iteration, so the loop runs only as many times as there are 1s.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/12-math-bits/088-number-of-1-bits.js ./practice c 088