DSA problem
Number of 1 Bits
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 optimal technique is Brian Kernighan's algorithm: the expression n & (n - 1) always clears the lowest set bit of n. By repeatedly applying this until n becomes 0 and counting the iterations, you count exactly the number of set bits — performing only as many iterations as there are 1 bits rather than looping over all 32 bit positions.
Examples
Example 1
Input:
n = 11Output:
3Explanation: The binary representation of 11 is 1011, which has a total of three set bits.
Example 2
Input:
n = 128Output:
1Explanation: The binary representation of 128 is 10000000, which has a single set bit.
Example 3
Input:
n = 2147483645Output:
30Explanation: The binary representation of 2147483645 is 1111111111111111111111111111101, which has thirty set bits.
Constraints
- 1 <= n <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.