Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
Explanation: Integer 11 has binary representation 00000000000000000000000000001011
Explanation: Integer 128 has binary representation 00000000000000000000000010000000
Time: O(N) in the worst case where all bits are 1
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.