算法练习22：找出二进制为1的个数（leetcode 剑指 Of

题目

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

解法1：二进制右移动，每位与1相与

每一位与1相与，如果为1，结果num+1；否则直接右移，因为只有32位，所以只需要遍历32位

var hammingWeight = function(n) {
    let num = 0;
    for(let i = 0; i < 32; i++) {
        // 如果为1，就代表此位为1
        if(n & 1) {
            num++;
        }
        // 每次比较完后，就比较下一位
        n >>= 1;
    }
    return num;
};

• 时间：O(logn)，因为每右移一位，就要进行n/2操作，要进行32次，所以是log2(n)
• 空间：O(1)，常量级

踩坑：解法1，如果循环条件换成while(n !== 0)时，使用>>右移就会有问题，因为这个二进数有可能是负数，负数单纯右移>>和无符号右移>>>是不一样的，要使用无符号右移才行

var hammingWeight = function(n) {
    let num = 0;
    while(n !== 0) {
        if(n & 1) {
            num++;
        }
        // 如果使用 n >>= 1，那么就会成为死循环， -1 >> 1 === -1
        // 需要使用无符号右移，三个箭头>>>
        n >>>= 1;
    }
    return num;
};

解法2：巧用位运算n&(n-1)

n&(n-1)的结果是最低位的1，会被消去。比如：
3： 011
2： 010 =>
&：010

8：1000
7：0111 =>
&：0000
当其结果为0时，就代表所有二进制位上的1都被消去了

var hammingWeight = function(n) {
    let num = 0
    while(n !== 0) {
        num++;
        n &= n -1
    }
    return num;
};

• 时间: O(M)，M为n中二进制为1的个数，最坏也就是32，因为至少32位
• 空间: O(1)，常量