qrcode

加入前端交流群,阿里、腾讯和京东大佬都在的群里

最常见面试算法之位 1 的个数

创建了一个 “重学TypeScript” 的微信群,想加群的小伙伴,加我微信 “semlinker”,备注 “1” 。阿里、京东、腾讯的大佬都在群里等你哟。

semlinker/awesome-typescript 1.6K

一、题目描述

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

汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中,它是 1 的个数。

汉明重量是以理查德·卫斯里·汉明的名字命名的,它在包括信息论编码理论密码学等多个领域都有应用。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

二、题解

2.1 循环和位移动

这个方法比较直接。我们遍历数字的 32 位。如果某一位是 1 ,将计数器加一。

我们使用位掩码来检查数字的第 i 位。一开始,掩码为 1,其对应的二进制表示为:

1
0000 0000 0000 0000 0000 0000 0000 0001

任何数字跟掩码 1 进行与运算,都可以获得这个数字的最低位。若需要检查次低位,我们将掩码左移 1 位,然后再与该数字进行与运算即可。

Java Code:

1
2
3
4
5
6
7
8
9
10
11
public int hammingWeight(int n) {
int bits = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
bits++;
}
mask <<= 1;
}
return bits;
}

JavaScript Code:

1
2
3
4
5
6
7
8
9
10
11
function hammingWeight(n) {
let bits = 0;
let mask = 1;
for(let i = 0;i < 32;i++){
if((n & mask) != 0){
bits++;
}
mask <<= 1;
}
return bits;
}

以上算法实现,无论 1 的个数为几个总得循环 32 次。这里我们可以通过无符号右移运算符来优化一下循环次数:

Java Code:

1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1;
}
return count;
}

JavaScript Code:

1
2
3
4
5
6
7
8
function hammingWeight(n) {
let count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1;
}
return count;
}

当然以上优化过的代码,在复杂的情况下也是要经过 32 次循环。下面我们来看一个循环次数只与 1 的个数有关的解法。

2.2 位操作的小技巧

这里我们介绍一种方法,可以把数字 n 二进制表达式中最右边的 1 置为 0。举个具体的例子,比如十进制 2020,然后我们把它和 2019 进行按位与操作,也就是 2020 & 2019

1
2
3
4
  0000 0111 1110 0100 // 2020
& 0000 0111 1110 0011 // 2019
---------------------
0000 0111 1110 0000 // 2016

通过观察上述结果和多次验证,我们可以发现一个规律:对于任意一个数 nn & (n - 1) 的结果就是把 n 的最右边的 1 置为 0 也比较好理解,当我们对一个数减 1 的话,比如原来的数是 80(01010000),然后减一就会向前借位,直到遇到最右边的第一个 1,变成 79(01001111),然后我们把它和原数按位与,就会把从原数最右边 1 开始的位置全部置零了 0100 0000。

有了这个技巧,我们只需要把原数依次将最右边的 1 置为 0,直到原数变成 0,记录总共操作了几次即可。

Java Code:

1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}

JavaScript Code:

1
2
3
4
5
6
7
8
function hammingWeight(n) {
let count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}

还有一种方法与上述的算法的复杂度是一样的,实现方式如下:

Java Code:

1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n -= n & (~n + 1);
count++;
}
return count;
}

JavaScript Code:

1
2
3
4
5
6
7
8
function hammingWeight(n) {
let count = 0;
while (n != 0) {
n -= n & (~n + 1);
count++;
}
return count;
}

每次进行 n-=n & (~n+1) 操作时,这也是移除最右侧 1 的过程。等号右边 n & (~n+1) 的含义是得到 n 中最右侧的 1。例如,n=0000 1010,n & (~n+1)=0000 0010, n - (n & (~n+1))=0000 1000。而当 n=0000 1000 时,n & (~n+1)=0000 1000,n - (n & (~n+1))=0000 0000。之后就不用继续处理了,因为已经没有 1 了。

三、其他解法

3.1 平衡算法

Java Code:

1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555); // 32 组向 16 组合并,合并前每组 1 个数
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333); // 16 组向 8 组合并,合并前每组 2 个数
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f); // 8 组向 4 组合并,合并前每组 4 个数
n = (n & 0x00ff00ff)+ ((n >>> 8) & 0x00ff00ff); // 4 组向 2 组合并,合并前每组 8 个数
n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff); // 2 组向 1 组合并,合并前每组 16 个数
return n;
}

3.2 正则匹配

JavaScript Code:

1
2
3
function hammingWeight(n) {
return ((n.toString(2).match(/1/g)) ||[]).length;
}

四、参考资源


欢迎小伙伴们订阅全栈修仙之路,及时阅读 TypeScript、Node/Deno、Angular 技术栈最新文章。

qrcode