图解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：

publicclassSolution {
publicinthammingWeight(intn) {
intresult=0, bit=0;
while (bit++<32) 
if ((n& (1<<bit)) !=0) result++;
returnresult;
    }
}

4.2> 实现2：

publicclassSolution {
publicinthammingWeight(intn) {
intresult=0, bit=32;
while (bit-->=0) {
if ((n&1) ==1) result++;
n>>>=1;
        }
returnresult;
    }
}

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

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

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