191. Number of 1 Bits

计算一串二进制中1的个数

移位法，根据最右边一位是1的奇数n & 1 = 1的性质，每次把n右移一位，累加n & 1的和，最后算出来的就是1的个数。

public int hammingWeight(int n) {
    int res = 0;
    while (n != 0) {
        res += (n & 1);
        n >>>= 1;
    }
    return res;
}

如果n输入的是负数，需要注意下>>>和>>的区别:

• >>是带着符号的右移，左边由于移位空缺出来的数字会由这个数字的符号位补全（正数补0负数补1），所以负数最终会变成-1，举例来说: -1的二进制是11111111 11111111 11111111 11111111如果选择有符号右移，那么移来移去还是它本来的数字-1，结果永远不是0，就会产生死循环。负数的二进制是补码..

-1073741824
-536870912
-268435456
-134217728
-67108864
-33554432
-16777216
...
-1
-1
...

• >>>是无符号右移，左边补0，对于-1来说11111111 11111111 11111111 11111111会变成2^31也就是2147483647，通过循环，最终可以到达0

调库法

public int hammingWeight(int n) {
    return Integer.bitCount(n);
}

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

https://doc.lagout.org/security/Hackers%20Delight.pdf

python字符串

return [c for c in bin(n)[2:]].count('1')