Sail


手在键盘敲很轻


leetcode191-位1的个数

题目

这是一道easy难度的题,先看看题目

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 ‘1’。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 ‘1’。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 ‘1’。

提示:

  • 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
  • 在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。

解答

当然在JavaScript中,也是没有无符号整数类型的,都是32位有符号整数类型。所以这里我们的输入都是有符号整数类型。那么我们的问题就转换成了输入一个整数,返回其二进制表达式中数字位数为‘1’的个数

十进制转二进制

这里我们很容易想到,将数字处理成二进制,然后统计其1的个数。从十进制转成二进制,不断除以2,直到为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
let count = 0;
while (n) {
count += n % 2;
n = n >> 1;
// n = Math.floor(n / 2);
}
return count;
};

位运算

循环和位移动

将输入的数字n与位掩码(初始值为1)的二进制做与运算,即可以得到n的最低位。举个例子

已知 0 & 1 = 0, 1 & 1 = 1

1的二进制表示是0000 0000 0000 0000 0000 0000 0000 0001
3的二进制表示是0000 0000 0000 0000 0000 0000 0000 0011

则 1 & 3,
结果二进制表示是0000 0000 0000 0000 0000 0000 0000 0001,即为1,得到了3的最低位。

检查下一位时,我们将掩码左移一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
let counts = 0;
let mask = 1;
for (let i = 0; i < 32; i++) {
if ((n & mask) !== 0) {
counts++;
}
mask <<= 1;
}
return counts;
};

位运算更简洁的做法

前面一种算法,需要检查数组的每一位。接下来的这种做法,不需要检查完每一位。而是通过不断的把数字的最后一个1进行反转。

核心思想是想法是对于任意数字 n ,将 n 和 n - 1 做与运算,会把最后一个 1 的位变成 0

1
2
3
n           ...1110100 // 倒数第3位是1
n - 1 ...1110011
n & (n -1) ...1110000 // 倒数第3位为0
1
2
3
4
5
6
7
8
9
10
11
12
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
let counts = 0;
while(n) {
counts++;
n &= n - 1
}
return counts;
};

leetcode链接

https://leetcode-cn.com/problems/number-of-1-bits/

© 2016-2020. | 由Hexo强力驱动 | 主题Huno | 渝ICP备17002561号 | 不装弱了,我要做大佬