每日一道 LeetCode (44)：位1的个数
共 1159字，需浏览 3分钟
·
2020-09-15 09:21
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：位 1 的个数
题目来源：https://leetcode-cn.com/problems/number-of-1-bits/
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3 。
解题方案一：暴力验证
这道题和昨天那道题比有点小巫见大巫的感觉，还是在考察二进制运算。
要知道一个二进制中有多少个 1 ，可以从最后一位开始循环，和 1 进行比较，前面有过类似的题目，一种常见的套路是取模运算，可以得到最后一位的值，但是如果是一个 32 位的二进制，那么它的第一位是正负号。
所以取二进制的最后一位通常情况下不适用取模的操作，而是使用位运算 &1 。
我们可以通过 &1 来验证最后一位是不是 1 ，同理可以使用 &10 来验证倒数第二位是不是 1 ，同理一顿往前推导。
这道题的答案就有了：
public int hammingWeight(int n) {
int count = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
count++;
}
mask <<= 1;
}
return count;
}
解题方案二：专属方案
这道题的答案上是这么描述这个方案的，这属于二进制数处理的一个小技巧。
当一个二进制数 n 同 n - 1 进行位运算 & 时，总是可以把最后一位由 1 变成 0 而其他位保持不变。
这个很好理解，因为是二进制数， n - 1 和 n 的最后一位肯定一个是 0 另一个是 1 ，他们两个进行一次 & 运算，相当于 0 和 1 进行一次 & 运算，结果当然是 0 。
而 n 如果最后一位是 0 的话，它需要和高位借一个 1 过来，这感觉有点像十进制运算时候的借位。
这么循环下去，总有一次会把高位的 1 全都借完，整个 n 变成 0 ，这时循环也就结束了，循环的次数就是我们这个 n 中拥有 1 的个数。
public int hammingWeight_1(int n) {
int count = 0;
while (n != 0) {
count++;
n &= (n - 1);
}
return count;
}
有了昨天那道题打底，今天的题讲道理感觉难度上没有那么高了，主要考察的是二进制的位运算，位运算除了有 & 以外，常用的还有 | 和 ^ 操作，遇到二进制的题可以优先考虑与一些特殊值的位运算。
