每日一道leetcode（python）191. 位1的个数
2021-08-28
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
输入必须是长度为 32 的 二进制串 。
进阶：
如果多次调用这个函数，你将如何优化你的算法？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-1-bits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
用位操作即可，只有1&1才为1
class Solution:
def hammingWeight(self, n: int) -> int:
ans = 0
while n != 0:
if n & 1:
ans += 1
n >> 1
return ans
python整数转二进制数，然后通过String.count获取1即可
class Solution:
def hammingWeight(self, n: int) -> int:
return bin(n)[2:].count('1') # 开头是0b，所以从2开始
课外知识
面试官：计算一下二进制中1的数量？
由于汉明重量的应用领域还是挺多的（反正我也不知道具体什么用 ），所以一些处理器甚至直接带有计算汉明重量的指令。但是，对于不具备这种特殊指令的普通处理器来说，目前已知效率最好的通用算法为variable-precision SWAR算法，通过一系列位移和与运算操作，可以在常数时间内计算多个字节的汉明重量，并且不需要使用任何额外的内存。 以计算32位长度的二进制数为例，下面是variable-precision SWAR算法的实现：
uint32_ t swar (uint32_ t i) {
//步骤1
i = (i & 0x55555555) + ((i >> 1) & 0x55555555) ;
//步骤2
i = (i & 0x33333333) + ((i >> 2) & 0x33333333) ;
//步骤3
i = (i & 0x0F0F0FOF) + ((i >> 4) & 0x0F0F0F0F) ;
//步骤4
i = (i*(0x01010101) >> 24) ;
return i;
}
整体思路就是先将相邻2位的1的数量计算出来，结果存放在这2位（步骤1）。然后将相邻4位的结果相加，结果存放在这4位（步骤2），将相邻8位的结果相加，结果存放在这8位（步骤3）。最后计算整体1的数量，记录在高8位，然后通过右移运算，将结果放到低8位，得到最终结果（步骤4）。
举个例子，计算0x5F70F21B中1的数量，首先转为二进制是01011010011100001111001000011011，然后执行步骤1，计算相邻两位中1的数量，计算结果覆盖到原数中：
执行步骤2，把存储结果相邻累加，计算相邻4位中1的数量，结果覆盖到原数：
执行步骤3，把存储结果相邻累加，计算相邻8位中1的数量，结果覆盖到原数：
执行步骤4，首先计算0x04030504 * 0x01010101。0x01010101其实就是(1<<24)+(1<<16)+(1<<8)+1 。i * (0x01010101)=(i<<24)+(i<<16)+(i<<8)+i，相当于把i的所有8位一起的分组都左移并相加，将结果聚合到了高8位。然后执行整体的右移24位，将结果转移到了低8位。
SWEAR算法通过先将数字进心最细力粒度的拆分，然后每一步都对上一次的计算结果进行整合，最终得到整体结果。由于这里处理的是32位数，所以这个算法比遍历算法快32倍，也不需要消耗额外内存空间。