255. Lit Bits
A row of up to 53 indicator lamps is controlled by a single non-negative number n: the lamp in position k (counting from 0 on the right) is lit exactly when bit k of n in binary is 1. A technician only wants to know how many lamps are currently lit.
Given the integer n, return the number of 1 bits in its binary representation. For example 1000 is 1111101000 in binary, so the answer is 6. The value can be larger than 32 bits, so make sure your language handles it correctly. Your solution should take time proportional to the number of bits and use constant extra space.
Example 1
- Input:
- n = 1000
- Output:
- 6
- Explanation:
1000 is 1111101000 in binary, which has six 1 bits.
Example 2
- Input:
- n = 4399120252929
- Output:
- 3
- Explanation:
4399120252929 is 2^42 + 2^30 + 1, so exactly three bits are set.
Example 3
- Input:
- n = 0
- Output:
- 0
- Explanation:
Zero has no set bits.
Constraints
0 ≤ n ≤ 9 * 1015
In JavaScript and TypeScript the value is a double that is exactly representable; the bit operators there only work on 32 bits.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)