最常见面试算法之位 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、TypeScriptNode.js/Java和Spring技术栈最新文章

原文 

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

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 最常见面试算法之位 1 的个数

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址