本文题目难度标识：🟩简单，🟨中等，🟥困难。

汉明重量

汉明重量是一串符号中非零符号的个数。对于二进制串来说就是 1 的个数 ^[1]。

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中设置位的个数。

常规算法

常规方法：循环检查二进制位，判断每一位整数是否为 1。

时间复杂度： $O(k)$ ，k 是二进制整数的位数
空间复杂度： $O(1)$ 。

Brian Kernighan 算法

Brian Kernighan 算法发布在 1988 年出版的 The C Programming Language (Second Edition) （由 Brian W. Kernighan 和 Dennis M. Ritchie 编写）的练习中，但是 Donald Knuth 在 2006 年 4 月 19 日指出，该方法第一次是由 Peter Wegner 在 1960 年的 CACM3 上出版。读者可以在上述书籍中找到更多位操作的技巧。

「Brian Kernighan 算法」用于清除二进制串中最右边的 1。

统计数 x 二进制表示中 1 的个数可以使用 Brian Kernighan 算法可以加速统计。

算法核心：记 $f(x)$ 表示 x 和 x-1 进行与运算所得的结果，即 $f(x)=$ x & (x-1)，那么 $f(x)$ 恰为 x 删去其二进制表示中最右侧的 1 的结果。

例子

x = 0b10001000
x-1 = 0b10000111
x&(x-1) = 0b10000000

时间复杂度： $O(\log C)$ 。C 表示元素的数据范围，循环次数等于 x 的二进制位中 1 的个数。当 x 为 32 位整数时，最坏情况下 x 二进制位全部为 1，我们需要循环 $\log 2^{31}=31$ 次。

空间复杂度： $O(1)$ ，我们只需要常数的空间保存若干变量。

相关题目：🟨 201. 数字范围按位与 - 力扣（LeetCode）

MIT HAKM 算法

MIT Hackmem 169

求 32 位无符号数的二进制形式中 1 的个数。

核心原理是分治法。

int bitcount(unsigned int n)
{
    unsigned int tmp;

    tmp = n - ((n >> 1) & 033333333333)
            - ((n >> 2) & 011111111111); // 注意这是8进制表示
    return ((tmp + (tmp >> 3)) & 030707070707)%63;
}