191.Number of 1 Bits

1- Bit Shifting

O(1) for limited length of int

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

Then we shift the input Integer by one on the right, to check for the

n = n>>>1;

We need to use bit shifting unsigned operation>>>(while>>depends on sign extension)

• We keep doing this until the input Integer is 0.

In Java we need to put attention on the fact that the maximum integer is 2147483647. Integer type in Java is signed and there is no unsigned int. So the input 2147483648 is represented in Java as -2147483648 (in java int type has a cyclic representation, that meansInteger.MAX_VALUE+1==Integer.MIN_VALUE).
This force us to use

n!=0

in the while condition and we cannot use

n>0

because the input 2147483648 would correspond to -2147483648 in java and the code would not enter the while if the condition is n>0 for n=2147483648.

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        while(n != 0){
            cnt += n & 1;
            n = n >>> 1;
        }
        return cnt;
    }
}

2-

n & (n - 1) drops the lowest set bit. It’s a neat little bit trick.

Let’s use n = 00101100 as an example. This binary representation has three 1s.

If n = 00101100, then n - 1 = 00101011, so n & (n - 1) = 00101100 & 00101011 = 00101000. Count = 1.

If n = 00101000, then n - 1 = 00100111, so n & (n - 1) = 00101000 & 00100111 = 00100000. Count = 2.

If n = 00100000, then n - 1 = 00011111, so n & (n - 1) = 00100000 & 00011111 = 00000000. Count = 3.

n is now zero, so the while loop ends, and the final count (the numbers of set bits) is returned.

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        while(n != 0){
            n &= (n - 1);
            cnt++;
        }
        return cnt;
    }
}