位运算之汉明权重

汉明权重是一串符号中不同于（定义在其所使用的字符集上的）零符号的个数，对于一个二进制数，它的汉明权重就等于它的 $1$ 的个数（即 popcount）。

一个二进制数的汉明权重可以通过枚举每一个二进制位来统计，或者通过不断减去 lowbit 来统计。

在状压 $dp$ 中，按照 popcount 递增的顺序枚举有时可以避免重复枚举状态，这是构造汉明权重递增的排列的一大作用。

有一个方法可以在 $O(n)$ 时间内构造汉明权重递增的排列。我们知道一个汉明权重为 $n$ 的最小整数是 $2^n-1$，那么只要能在常数时间内构造出一个汉明权重相等的后继，我们就可以通过枚举汉明权重，从 $2^n-1$ 开始不断寻找下一个数的方式，在 $O(n)$ 的时间内构造出 $0 \sim n$ 的符合要求的排列。

对于一个数 $x$，可以用一个思路来找到其汉明权重相等的后继，从低位开始，找到第一个更高一位是 $0$ 的 $1$，也就是第一个能进位的 $1$，我们让这个 $1$ 进位，然后将低位中的所有 $1$ 都移动到末尾。

举个例子，以 $(10110)_2$ 为例，进位之后就是 $(11010)_2$，此时由于已经进位，因此更低位的数不管是多少，都能保证 $\gt x$，因此将低位中的所有 $1$ 移动到末尾，既能保证汉明权重不变，又能保证数值最小，即 $(11001)_2$

将过程用位运算来优化，如下：

int t = x + (x & -x);
x = t | ((((t & -t) / (x & -x)) >> 1) - 1);

其中 $t$ 用来表示进位后的数，(((t & -t) / (x & -x)) >> 1) - 1 表示进位后，低位中的所有的 $1$，并且此时已经全部移动到末尾，在或上 $t$ 就是 $x$ 的汉明权重相等的后继。

由此可以得出枚举 $0 \sim n$ 按汉明权重递增的排列的代码如下：

for(int i = 0; (1 << i) - 1 <= n; i++)
{
    //0 没有汉明权重相等的后继，需要特判
    for(int x = (1 << i) - 1, t; x <= n; t = x + (x & -x), x = x ? (t | ((((t & -t) / (x & -x)) >> 1) - 1)) : n + 1)
    {
        //执行转移等操作...
    }
}