如何快速从一群 0 中找到 1

首先，这不是在找成都人。

这是一个很常见的算法问题：计算一个二进制的数字中 1 的数量。 最近看到一个很有趣的算法，但是解释得不太明白，我尝试解释一下。

有兴趣的话你可以自己先想想自己会怎么做，然后看看能不能一下理解这个算法的原理。 我假设读者没有编程和算法的基础，所以会尽量从基础开始讲起。 你可以直接跳过基础阅读后面「一个有趣的算法」的部分。

一些基础

二进制

我们平时使用的是十进制数， 比如 234 这个数字有三位，分别是百位，十位和个位。 每一位上的数字实际上代表着 $10^{n}$。

$$234 = 2\times 10^{2} + 3\times 10^{1} + 4\times 10^{0}$$

每一位的数字只能是0～9，满 10 就会向上进 1 位。

相对的二进制则是每一位只能有 0～1 两个数字，满 2 就要向上进 1 位。 比如 $(101)_2$ 就是一个二进制数，如果按照类似十进制的说法， 这里的三位就分别是四位，二位和个位。 同样的，每一位上的数字代表着 $2^n$。

$$(101)_{2}=1\times2^{2} + 0\times2^{1} + 1\times2^{0}=5$$

移位

这是一个编程之外的领域比较少提到的操作。 我们把 $234 \rightarrow 2340$ 这样的操作叫做左移；把 $234 \rightarrow 23$ 这样的操作叫做右移。 可以看到，左移其实就是 $\times 10$，右移就是 $\div 10$（整除并舍弃余数）。

同样的，二进制也有同样的操作。比如 $(101)_2\rightarrow(10)_2$ 就是 $\div 2$， 而$(101)_2\rightarrow(1010)_2$则是$\times 2$。

一个无聊的算法

好了，有了这些基础，我们可以考虑怎么解决这个问题了。 我觉得最直觉的一个方法是利用优移操作，反复确认各位数字是不是 1。

以 $(1011)_2$ 为例：

1. $(1011)_2$ 的个位是 1
2. $(1011)_2 \rightarrow (101)_2$ ，个位是 1
3. $(101)_2 \rightarrow (10)_2$ ，个位是 0
4. $(10)_2 \rightarrow (1)_2$ ，个位是 1

于是我们就能计算出有三个 1 。

需要注意的是，我们不能直接取出一位数来做比较， 所以「判断个位是不是1」其实也需要额外的计算。 你可能已经想到了，如果一个数是奇数，那么它的二进制个位就是1， 否则它的二进制个位数就是 0。 所以，我们可以直接用对 2 取余数的方法来解决这个问题。

这个问题的完整解法就变成了下面这样：

1. 把 $(1011)_2$ 转变成十进制

   $$ (1011)_{2} = 1\times2^{3} + 0\times2^{2} + 1\times2^{1} + 1\times2^{0} = 11 $$

2. 用 2 整除 11，商5 余1 （奇数，二进制个位为 1）

3. 用 2 整除 5，商 2 余 1（奇数，二进制个位为 1）

4. 用 2 整除 2，商 1 余 0（偶数，二进制个位为 0）

5. 用 2 整除 1，商0 余 1（奇数，二进制个位为 1）

6. 将所有余数相加，就得到了结果 3。

一个有趣的算法

对于有编程基础的读者，我先贴出算法的 C 代码，你可以尝试思考一下它的原理。

1
2
3
4
5
6
7
8

unsigned popcnt(unsigned x) {
	unsigned diff = x;
	while (x) {
		x >>= 1;
		diff -= x;
	}
	return diff;
}

如果这个有些难懂，它还可以写作下面的样子

1
2
3
4
5
6
7
8
9

    unsigned popcnt(unsigned x) {
        unsigned sum = 0;
        unsigned remaining = x;
        while (remaining) {
            remaining >>= 1;
            sum += remaining;
        }
        return x - sum;
    }

好了，下面就是对这个算法的解释了。

算法的解释

这些代码做的事情可以这么描述 (公式1)： $$x-x/2-x/4-x/8-…=x-(x/2+x/4+x/8+…)$$

注意，这里的除法都是整除，比如 $5/2=2$。 相应地，我们用 $\frac{x}{2}$ 来表示普通的实数除法，即 $\frac{5}{2}=2.5$。

事实上，如果不是整除的话，上面的式子的结果是 0 。也就是说

$$ x = \sum^{\infty}_{n=1}\frac{x}{2^{n}} $$

这其实就是《庄子》中的「一尺之捶，日取其半，万世不竭」。

那么公式1的结果是什么呢？由于 $ x/2^{i}=x/2^{i-1}/2 $ 是整除，所以公式1的结果其实就是前面无聊算法中余数的和。也就是说，一尺之捶，日取其半（其半不是整数的时候就把余数存起来），这样最后存起来的部分就是答案了。