Number of 1 Bits
The key idea
Count set bits by repeatedly clearing the lowest set bit with
n & (n - 1). Each clear removes exactly one 1, so the number of iterations equals the answer and the loop runs only as many times as there are set bits.Problem
Write a function that takes the binary representation of a positive integer n and returns the number of set bits it has (also known as the Hamming weight).
The number of set bits is the count of 1s in the binary form of n.
Constraints
1 <= n <= 2^31 - 1
Examples
Input: n = 11
Output: 3
Input: n = 128
Output: 1
Input: n = 2147483645
Output: 30
Complexity
Time: O(1) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization