Given a non-negative integer n, return how many bits are set to 1 in its binary representation — its population count.
Examples
Example 1:
Input: n = 11
Output: 3
Explanation: 1011.
Example 2:
Input: n = 128
Output: 1
Explanation: 10000000.
Example 3:
Input: n = 1
Output: 1
Example 4:
Input: n = 2147483647
Output: 31
Constraints
0 <= n <= 2^31 - 1
Prerequisites
Binary and two's complement — how a negative number is stored, and what a shift does at the edges. The trick worth memorising: n & (n-1) clears the lowest set bit.
How to think about it
1. Clear the Lowest Set Bit Optimal
Intuition
n & (n-1) clears exactly the lowest set bit — subtracting one flips that bit off and turns everything below it on, and the AND wipes those. So the number of times you can do it before reaching zero IS the number of set bits, and you never look at the zeros.
Algorithm
1. While n is not zero, replace n with n & (n-1). 2. Count the iterations.
Time & Space
Time O(set bits) rather than O(32). Space O(1). Built-ins exist; the follow-up is always to do it by hand.