比x大的最小的且和x含有同样数目个1的整数

子集枚举中经常用到的，求按字典序，从n个元素中取k个元素的所有子集序列，其核心就是求比x大的最小的且和x含有同样数目个1的整数。
有一个很神奇的位操作可以做到这一点，算法的C语言代码如下：

unsigned int next(unsigned int x){
    unsigned int s,r;
    s = x & (-x);
    r = s + x;
    x = r | (((x ^ r)>>2)/s);
    return x;
}

我们分析一下这个算法。

设next为所求，显然 s = lowbit(x) 。

然后分情况讨论：

1. 如果x是$\underbrace{\ldots}_{\text{r}} \,0 \,1 \, \underbrace{0\ldots 0}_{\text{t}}$的形式，
   那么next应该为 $\underbrace{\ldots}_{\text{r}} \,1 \,0 \,\underbrace{0\ldots 0}_{\text{t}}$，
   显然， next = x + lowbit(x) 。
2. 如果x是$\underbrace{\ldots}_{\text{r}} \,0 \,\underbrace{1\ldots 1}_{\text{k}} \underbrace{0\ldots 0}_{\text{t}}$ 的形式，
   那么 next应该是 $\underbrace{\ldots}_{\text{r}} \,1 \,\underbrace{0\ldots 0}_{\text{t}}\, \underbrace{1\ldots1}_{\text{k-1}} $。
   观察第一种情况可知，其相当于第一种情况下，把最后$k-1$位置成$1$。

最后就是那个神奇的操作 (((x ^ r)>>2)/s) 。

假设$s$的$1$位于从后往前数的第$t+1$位，那么$n / s$这个操作，相当于去掉$n$的最后$t$位，所以右移$2$位并除$s$的话，相当于去掉$n$的最后$2+t$位。

我们看一下两种不同的情况：

第一种情况时，这个操作的值恒定为$0$，因为$((x \oplus r)>>2) < s $

第二种情况时，我们需要将$r$的最后$k-1$位置成$1$，但是无法很方便地求出$k$。

我们利用 $x \oplus r$ 可以获得$k+1$ 个 1，

$$\begin{array}{ccc}\, x & = & \underbrace{\ldots}_{\text{r}} & 0 & \underbrace{1\ldots 1}_{\text{k-1}} & 1 & \underbrace{0\ldots 0}_{\text{t}} \\ s & = & \underbrace{0.0}_{\text{r}} & 0 & \underbrace{0\ldots 0}_{\text{k-1}} & 1 & \underbrace{0\ldots 0}_{\text{t}} \\ r & = & \underbrace{\ldots}_{\text{r}} & 1 & \underbrace{0\ldots 0}_{\text{k-1}} & 0 & \underbrace{0\ldots 0}_{\text{t}} \\ x \oplus r & = & \underbrace{0.0}_{\text{r}} & 1 & \underbrace{1\ldots 1}_{\text{k-1}} & 1 & \underbrace{0\ldots 0}_{\text{t}} \end{array}$$

可知$x \oplus r$ 中有$k+1$个1，且最高位的$1$和next对应位是一致的。 剩下的，我们只要把$k-1$个$1$给挪到最后$k-1$位即可。

从而(((x ^ r)>>2)/s) 能得到一个前面全是$0$，末尾为$k-1$个$1$的数。