Leetcode 191  Number of 1 Bits
Problem Statement
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
Example 1:
Input: 11
Output: 3
Explanation: Integer 11 has binary representation 00000000000000000000000000001011
Example 2:
Input: 128
Output: 1
Explanation: Integer 128 has binary representation 00000000000000000000000010000000
Solution


Time: O(N) in the worst case where all bits are 1
Space: O(1)
Explanation
If you’ve looked at the EPI Chapter 1 post I did, it explains an algorithm where by you can loop through until n is 0 and skip the unset bits. This is what is going on here. If you have 12 = 1100
then the LSB (least significant bit) is at position 3 from the right. Then n  1
is simply 1011
and when you & those two you get 1100 & 1011 = 1000
. Do that one more time and you’ll get 2 for r.