Given a non-negative integer n, return the number of 1 bits in its binary representation (also called its Hamming weight).
Example 1:
Input: n = 11 Output: 3 Explanation: 11 in binary is 1011, which has three 1 bits.
Example 2:
Input: n = 128 Output: 1 Explanation: 128 in binary is 10000000, which has a single 1 bit.
Example 3:
Input: n = 2147483645 Output: 30 Explanation: 2147483645 in binary is 1111111111111111111111111111101: thirty-one digits, and all but one of them are 1.
Constraints:
0 <= n <= 231 - 1
Your algorithm should run in O(k) time, where k is the number of 1 bits in n, and use O(1) extra space.
Look at what subtracting 1 does to a number in binary: its lowest 1 bit turns into 0, every 0 below it turns into 1, and the higher bits stay the same. For example, 12 is
1100 and 11 is 1011.
So
n AND n - 1 is n with its lowest 1 bit removed: 1100 AND 1011 is 1000. Keep doing it until n becomes 0, and count how many times you did it.
Each pass of the loop removes one 1 bit, so the loop runs
k times, at most 31 for these values: O(k) time.We keep only the count and the number we change, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
