算法练习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;
};
- 时间: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),常量