在这里，我们将讨论一些高级别的位操作技巧，如果巧妙地使用，真的可以加快你的程序执行时间。
我们已经讨论了一些简单的位操作方法，如果你还不熟悉位操作可以先浏览一下【你必须知道的简单的位操作技巧】，这里我们接着往下说：
我们在这篇文章中讨论了一些基本的位操作方法： - 你必须知道简单的位操作技巧。请通过这个帖子来了解一些事情是如何工作的,这里我们接着往下说:
案例 6:将最右边的1位的bit设为0
y = x & (x-1)
现在它终于变得更有趣了！比特从案例1到案例5真的很无聊。
这条语句将从右至左看值为1的比特位置为0。例如，给定一个整数00101010（最右边的1位粗体）将它变成00101000.经过操作给定00010000将它变成0，因为只有一个比特值为1。
这里有更多的例子：
01010111 (x)
& 01010110 (x-1)
--------
01010110
01011000 (x)
& 01010111 (x-1)
--------
01010000
10000000 (x = -128)
& 01111111 (x-1 = 127 (with overflow))
--------
00000000
11111111 (x = all bits 1)
& 11111110 (x-1)
--------
11111110
00000000 (x = no rightmost 1-bits)
& 11111111 (x-1)
--------
00000000
为什么它工作？
如果你看一下例子并思考一段时间，你会发现有两种可能的情况：
1.这个数值存在值为1的比特位。在这种情况下，从中减去一个，将所有低位设置为1，并将最右边的位更改为0（这样，如果现在添加一个，则返回原始值）。这一步已经屏蔽掉了最右边的1位，现在用最右边1位的原始值零进行&操作,得到的结果就是这一位置为0。
2.该值没有最右边的1位（全0）。在这种情况下，减去一个下溢值（因为它是有符号的整数）并将所有位设置为1.全0和全1做与运算结果为0。
案例 7: 隔离最右边的1位比特
y = x & (-x)
找到最右边的为1的比特位,并将所有其他位设置为0.最终结果只有一个最右边的为1比特位。例如，01010100（最右边的位用粗体表示）变成00000100。
以下是一些例子：
10111100 (x)
& 01000100 (-x)
--------
00000100
01110000 (x)
& 10010000 (-x)
--------
00010000
00000001 (x)
& 11111111 (-x)
--------
00000001
10000000 (x = -128)
& 10000000 (-x = -128)
--------
10000000
11111111 (x = all bits one)
& 00000001 (-x)
--------
00000001
00000000 (x = all bits 0, no rightmost 1-bit)
& 00000000 (-x)
--------
00000000
这是一个比特位操作,因为二补。在二进制补码系统中,x与〜x + 1相同。
现在我们来看两个可能的情况：
1.有一个最右边值为的1比特位。在这种情况下，让我们在这个位上进行转换，并将所有其他位分成两个侧面 - 位右侧和位左侧。请记住，右边的bi-1，bi-2 … b0的所有位都是0（因为bi是最右边的1位）。而位左边是他们的方式。我们称它们为bi + 1，…，bn。
现在，当我们计算-x时，我们首先将bit bi变成0，比特bi-1 … b0变成1，接着反转比特bi + 1，…，bn，然后我们给这个结果+1。
由于比特bi-1 … b0全部为1，所以加1都为0,直到遇到bi位。
如果把它们放在一起，则计算-x的结果是比特bi + 1，…，bn得到反转，比特bi保持不变，并且比特bi-1，…，b0都是0。
现在，使用x & (-x)使得比特bi + 1，…，bn全部为0，比特bi保持不变，并且将比特bi-1，…，b0设置为0.只留下一个比特，它是比特bi - 最右边的1位。
2.不存在值为1的比特位。该值为0.二进制补码中的0的负数也为0. 0＆0 = 0。运算结果还是0。
我们已经严格证明这个技巧是正确的。
案例 8：右传播最右边值为1的比特位。
y = x | (x-1)
这是一个例子最好的理解。给定一个值01010000将它变成01011111.所有0位到最右边的1位变成了1。
这是技巧有个缺陷，因为如果x = 0，结果全为1。
让我们看看更多的例子：
10111100 (x)
| 10111011 (x-1)
--------
10111111
01110111 (x)
| 01110110 (x-1)
--------
01110111
00000001 (x)
| 00000000 (x-1)
--------
00000001
10000000 (x = -128)
| 01111111 (x-1 = 127)
--------
11111111
11111111 (x = -1)
| 11111110 (x-1 = -2)
--------
11111111
00000000 (x)
| 11111111 (x-1)
--------
11111111
让我们来证明这一点，尽管不像以前那样严格（因为这太浪费大家时间了，这也不是学术论文不是吗）。还有两个例子。我们先从最简单的开始。
1.没有最右边值为1的比特位。在这种情况下，x = 0，x-1 = -1。-1的二进制补码是11111111和0与11111111产生相同的11111111.（不是想要的结果，但是结果就是这样）。
2.最右边值为1的比特位。我们再把所有的比特分成两组（如前面的例子）。计算x-1只修改右边的比特位，将bi变成0，将所有的低位(右边)变成1。现在将x与x-1进行或运算，所有更高的位（左边）保持不变，离开位bi，因为它是1，并且由于低位(右边)都是低1。结果是最右边值为1比特位向低位(向右)传播。
案例 9：隔离最右边值为0的比特位。
y = ~x & (x+1)
这个案例9和案例7相反。首先找到最右边值为0比特位，将其他位置设为0，并将结果中的这一位置设置为1。例如，它在这个数字10101011中找到粗体零，产生00000100。
更多例子：
10111100 (x)
--------
01000011 (~x)
& 10111101 (x+1)
--------
00000001
01110111 (x)
--------
10001000 (~x)
& 01111000 (x+1)
--------
00001000
00000001 (x)
--------
11111110 (~x)
& 00000010 (x+1)
--------
00000010
10000000 (x = -128)
--------
01111111 (~x)
& 10000001 (x+1)
--------
00000001
11111111 (x = no rightmost 0-bit)
--------
00000000 (~x)
& 00000000 (x+1)
--------
00000000
00000000 (x)
--------
11111111 (~x)
& 00000001 (x+1)
--------
00000001
证明：假设有一个最右边值为0的比特位。然后-x和x+1将这一位变位1（因为右边0位的位是1）。x + 1和〜x会将所有位全部设置到最右边的0位。这是结果中设置的最高位。那么最右边0位右边的低位呢？他们也被蒸发了，因为x + 1把它们变成了0（他们是1），并且把它们变成了0。他们得到0和蒸发,因此只剩下bi位为1。
#案例 10：将最右边值为0的比特取反
y = x | (x+1)
这个破解将最右边的0位变成1.例如，给定一个整数10100011，它把它变成10100111。
更多例子：
10111100 (x)
| 10111101 (x+1)
--------
10111101
01110111 (x)
| 01111000 (x+1)
--------
01111111
00000001 (x)
| 00000010 (x+1)
--------
00000011
10000000 (x = -128)
| 10000001 (x+1)
--------
10000001
11111111 (x = no rightmost 0-bit)
| 00000000 (x+1)
--------
11111111
00000000 (x)
| 00000001 (x+1)
--------
00000001
这是一个真实的陈述证明。x与x + 1不会丢失任何信息。将1添加到x填充第一个最右边的0.结果是max {x，x + 1}。如果x + 1溢出，那么x就没有值为0比特位。如果没有溢出的话，那就是x + 1，最右边的0比特被设置为1。
原文来自http://www.studyalgorithms.com/theory/advacned-level-bit-hacks/