191.Number of 1 Bits

Posted on | In

Solution 1: NC

Have problem with test cases:
4294967295 (11111111111111111111111111111111).
-2147483647 (1000 0000 0000 0000 0000 0000 0000 0000).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
    if (n == 0) 
        return 0;
    if (n < 0) 
        n = -n;
    int maxPow = 0;
    while (Math.pow(2, maxPow) <= n) {
        maxPow++;
    }       
    maxPow--;
    int result = 1;
    while (n > 1) {
        n -= Math.pow(2, maxPow);
        if (n == 0)
            return 1;
        maxPow--;
        result++;
    }
    return result;
}

Solution 2: accepted 2ms

  1. Unsigned: use >>> rather than >>
  2. Cannot use n >= 1, as some test cases will be recognized as negative number in java
1
2
3
4
5
6
7
8
public int hammingWeight(int n) {        
    int count = 0;
    while (n != 0) { // can't use n >= 1, as negative number do exist
      count += n & 1;
      n = n >>> 1; // unsigned, use >>> rather than >>
    }
    return count;
}