其实就当是 Hacker’s Delight 的读书笔记啦w 代码用 C 来表示
操作最右侧位
考虑如何用位运算将 x 最右侧的 1 变为 0，显然，这个操作的目的一定会减少 1 的数量，考虑所有的位运算符，唯一符合要求的就是 &，那么这个操作的样子应该是
x & a
其中 a 要在 x 最右侧 1 的位为 0，并且保持其他 1 的位。那么就很显然啦
x & (x-1)
如果 x 是 2^n 的话那么这个式子应该得到 0，所以可以用来判断 x 是否为 2^n
同样的思路，要将 x 最右侧的 0 变成 1 的话就是
x | (x+1)
& 与 |，+ 与 - 是对偶的关系，一般来说把对 1 的操作换成对偶的表达式之后就是对 0 的操作。
现在来考虑如何析出最右侧的 1 位，考虑要将除了最右侧的 1 以外都变成 0，第一反应可能是用 ^，那么构造的表达式是
((x ^ (x-1))+1)»1
虽然可行可是太麻烦啦，除了异或，其他能将 1 都变为 0 且保持 0 的操作就只有 & 了，注意到 x & ~x 恒为 0，后面就很显然了
x & ~(x-1)
上式还能化简，补码表示里 ~(x-1) 等价于 -x，所以最终得到
x & (-x)
前面失败的尝试中也有一个有趣的式子
x ^ (x-1)
这个式子将析出最右侧的 1 和后缀 0 的掩码
最后举一个上面式子的应用，如何穷举一个位向量表示的集合中选取 n 个元素的所有组合，换句话说，如何获得与给定 x 具有相同数量 1 的下一个比 x 大的数
如果 x 最右侧的 1 能够左移，也就是说最右侧的 1 相邻的位为 0，那么显然左移最右侧 1 得到的数是所求的数
如果 x 最右侧的 1 左侧为 1，那么向左直到找到第一个能够左移的 1 后左移，把右侧所有的 1 移到最右侧。比如 0001 1011 0000 将变为 0001 1100 0011
其实第一种情况只是第二种的特例，根据以上描述得到操作如下
// 析出最右侧的 1
s = x & -x
// 所有连续的 1 都会被进位直到第一个 0
ret = x + s
// 析出最右侧的连续 1 以及进位的 1，比需要的 1 多了两个
t = x ^ ret
// 除以 s 将 t 对齐至最低位，左移 2 去掉多余的两个 1
ret |= (t»2)/s
ret 就是所求的数
嘛 我发现学了东西还是要写下来不然会忘 而且我的表达能力太差了正好锻炼下 .-.
