最常见面试算法之位 1 的个数
一、题目描述
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量)）。
汉明重量是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是 1 的个数。 汉明重量是以理查德·卫斯里·汉明的名字命名的，它在包括信息论、编码理论、密码学等多个领域都有应用。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。
二、题解
2.1 循环和位移动
这个方法比较直接。我们遍历数字的 32 位。如果某一位是 1 ，将计数器加一。
我们使用位掩码来检查数字的第 i 位。一开始，掩码为 1，其对应的二进制表示为：
0000 0000 0000 0000 0000 0000 0000 0001任何数字跟掩码 1 进行与运算，都可以获得这个数字的最低位。若需要检查次低位，我们将掩码左移 1 位，然后再与该数字进行与运算即可。
Java Code：
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：
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：
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1;
}
return count;
}JavaScript Code：
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：
0000 0111 1110 0100 // 2020
& 0000 0111 1110 0011 // 2019
---------------------
0000 0111 1110 0000 // 2016通过观察上述结果和多次验证，我们可以发现一个规律：对于任意一个数 n，n & (n - 1) 的结果就是把 n 的最右边的 1 置为 0。 也比较好理解，当我们对一个数减 1 的话，比如原来的数是 80（01010000），然后减一就会向前借位，直到遇到最右边的第一个 1，变成 79（01001111），然后我们把它和原数按位与，就会把从原数最右边 1 开始的位置全部置零了 0100 0000。
有了这个技巧，我们只需要把原数依次将最右边的 1 置为 0，直到原数变成 0，记录总共操作了几次即可。
Java Code：
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}JavaScript Code：
function hammingWeight(n) {
let count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}还有一种方法与上述的算法的复杂度是一样的，实现方式如下：
Java Code：
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n -= n & (~n + 1);
count++;
}
return count;
}JavaScript Code：
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：
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：
function hammingWeight(n) {
return ((n.toString(2).match(/1/g)) ||[]).length;
}四、参考资源
欢迎小伙伴们订阅前端全栈修仙之路，及时阅读 Angular、TypeScript、Node.js/Java和Spring技术栈最新文章。
腾讯云开发者
