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

2021-05-09  本文已影响0人  miao8862

题目

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 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;
};

踩坑:解法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;
};
上一篇 下一篇

猜你喜欢

热点阅读