Number of 1 Bits
Number of 1 Bits is an easy Bit Manipulation problem from the Blind 75. The key pattern is bit tricks, and a good solution runs in O(set bits) time.
Problem
Treat the input as an unsigned 32-bit integer and return its number of set bits.
Examples
Example 1
Input
29Output
4Example 2
Input
22Output
3Example 3
Input
256Output
1Approach
n & (n − 1) clears the lowest set bit, so count how many times you can do it before n reaches 0.
| Pattern | Bit tricks |
|---|---|
| Time | O(set bits) |
| Space | O(1) |
Watch out for
Treat the input as unsigned 32-bit; in JavaScript use >>> rather than >>.