图解LeetCode——剑指 Offer 15. 二进制中1的个数

一、题目

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量）。

二、示例

2.1> 示例 1：

【输入】n = 11 (控制台输入 00000000000000000000000000001011)
【输出】3
【解释】输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'

2.2> 示例 2：

【输入】n = 128 (控制台输入 00000000000000000000000010000000)
【输出】1
【解释】输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'

2.3> 示例 3：

【输入】n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
【输出】31
【解释】输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'

提示：

• 输入必须是长度为 32 的 二进制串 。

三、解题思路

3.1> 思路1：

根据题意，我们需要找出某个int类型数字中二进制1的个数，那么首先我们可以通过创建一个变量bit，其初始值为0，它表示向左移动的位数，即：1 << bit；那么就有如下结果：

【当bit=0时】1 << bit等于1 << 0，即：00001；
【当bit=1时】1 << bit等于1 << 1， 即：00010；
【当bit=2时】1 << bit等于1 << 2，即：00100；
【当bit=3时】1 << bit等于1 << 3，即：01000；
以此类推……

那么我们可以根据以上的1 << bit （bit自增到31），并且与int类型的数字执行按位与操作，那么就可以校验32位中每一位是否为1了。好了，解题思路并不复杂，那么下面我们还是按照惯例，以找出二进制0101110有多少个1为例，看一下具体的计算过程。请见下图所示：

3.2> 思路2：

在思路1中，我们是创建了bit变量，然后通过移动bit来进行每一位是否为1的判断的。那么，我们也可以通过移动这个int类型的数字，去跟固定的1执行按位与操作，那么也是可以计算出某个int类型数字中二进制1的个数。具体的操作详情我就不在这里追溯了，我们来看下图，里面已经画出了详细的处理过程。

四、代码实现

4.1> 实现1：

public class Solution {
    public int hammingWeight(int n) {
        int result = 0, bit = 0;
        while (bit++ < 32) 
            if ((n & (1 << bit)) != 0) result++;
        return result;
    }
}

4.2> 实现2：

public class Solution {
    public int hammingWeight(int n) {
        int result = 0, bit = 32;
        while (bit-- >= 0) {
            if ((n & 1) == 1) result++;
            n >>>= 1;
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」