https://leetcode.com/problems/number-of-1-bits/

Version 1

We test the number n with bitwise and 1, if the result is equal 1. We know the right most
bit is 1, otherwise, we right shift one more bit for n: PS: the ending condition for the
while loop is n != 0 since int in java is always a signed number. We know the loop is
over when we right shifted all the 1s for n.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int acc = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                acc++;
            }
            n >>>= 1;
        }
        return acc;
    }
}

Version 2 (using n & (n - 1))

Observing the pattern below:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

The result of n & (n - 1) will remove the right-most 1 for the bit representation of n.
So for example, if we need to count the number of 1s for 1111:

1111 & (1111 - 1) = 1111 & 1110 = 1110
1110 & (1110 - 1) = 1110 & 1101 = 1100
1100 & (1100 - 1) = 1100 & 1011 = 1000
1000 & (1000 - 1) = 1000 & 0111 = 0000

A total of 4 steps, which means that there are 4 1s in the 1111. For the code:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int rst = 0;
        while (n != 0) {
            n &= n - 1;
            rst++;
        }
        return rst;
    }
}