191. Number of 1 Bits

二刷 06/2022

Version #1 Count bits

Time O(32) ~ O(1)

Space O(1)

Runtime: 1 ms, faster than 84.47% of Java online submissions for Number of 1 Bits.

Memory Usage: 42 MB, less than 7.00% of Java online submissions for Number of 1 Bits.

public class Solution {

    // you need to treat n as an unsigned value

    public int hammingWeight(int n) {

        int count = 0;

        while (n != 0) {

            count += (n & 1);

            n >>>= 1;

        }

        return count;

    }

}

Version #2 Bit Manipulation

Time O(Number of bit 1s)

Space O(1)

we repeatedly flip the least-significant 11-bit of the number to 0

by using n & (n - 1)

Runtime: 1 ms, faster than 84.47% of Java online submissions for Number of 1 Bits.

Memory Usage: 41.7 MB, less than 14.98% of Java online submissions for Number of 1 Bits.

public class Solution {

    // you need to treat n as an unsigned value

    public int hammingWeight(int n) {

        int count = 0;

        while (n != 0) {

            count++;

            n = n & (n - 1);

        }

        return count;

    }

}

一刷
一开始写TLE因为写成了n >>= 1这样是arithmetic shift right，负数永远不可能为0

要写成 n >>>= 1才是logical shift right

更简洁的写法 count += (n & 1);
7.79 %
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) != 0) count++;
            n >>>= 1;
        }
        return count;
    }
}