转载

最常见面试算法之位 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，其对应的二进制表示为：

任何数字跟掩码 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技术栈最新文章。

原文 https://semlinker.com/hamming-weight/

正文到此结束

所属分类： Java 编程技术

本文标签： 1111 js http https ask ip TypeScript 2019 node 遍历 id 编译代码 IO java Node.js JavaScript spring 数据文章
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

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

二、题解

2.1 循环和位移动

Java Code：

JavaScript Code：

Java Code：

JavaScript Code：

2.2 位操作的小技巧

Java Code：

JavaScript Code：

Java Code：

JavaScript Code：

三、其他解法

3.1 平衡算法

Java Code：

3.2 正则匹配

JavaScript Code：

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流