位操作秘籍
在计算机的远古时代，机器都是巨无霸，处理器的性能和内存的容量相对于它的身躯就显得很渺小，它就像一个块头很大但心脏却很脆弱的人。为了保证它不会经常性地因为心脏衰竭崩溃，远古的大神们都会在程序中首选二进制位操作来进行计算，所以他们对二进制位操作的使用可谓是信手拈来。但随着处理器越来越强、内存越来越大，我们也逐渐忘记了这项绝技，正所谓生于安乐，死于安逸啊！这篇文章的目的就是重新把这些位操作的秘籍传授给大家。
从我们刚开始学习程序起，就知道计算机处理位操作运算比一般的算术运算要快，而很多算术运行都可以转化为位操作，例如左移可以实现乘以2的运算，而右移可以实现除2运算。考虑到性能通常会选择位操作来实现算术运算，这些都是位运算的小技巧，除了这些技巧外，还有很多其他的小技巧。
这篇文章会介绍一些类似的位操作的技巧，这不会是一篇介绍二进制位操作的理论的文章，所以为了保持在同一个频道，我先假设你了解整数的二进制补码的表示法，以及所有位运算法则。
我将在这篇文章中使用下面的二进制运算符：
& - 二进制与运算 | - 二进制或运算 ^ - 二进制异或运算 ~ - 二进制求非运算 << - 二进制左移运算 >> - 二进制右移运算
在这篇文章中所有的数（特别说明除外）都是用二进制补码表示的8位有符号整数（这些运算其实也适用于任意长度）。'x'表示操作数，'y'表示结果。x的二进制位表示我们一般命名为b7,b6,b5,b4,b3,b2,b1和b0，b7是符号位，最重要的一位，第0位的b0是最不重要的，从左到右，也被定义为由高位到低位。
整数的二进制表示还有原码和反码两种表示法，这两种表示法都有一些缺陷。现代的计算机基本都是用补码表示的，这些都不在这篇文章的讨论范围内，另外这篇文章也只会以整数的运算为例，而不会考虑浮点数的运行。
注意，由于二进制运算跟数理逻辑的理论是一致的，在数理逻辑中通常将值为1位定义为已置位，将把1设置0叫做重置或者关闭，将0设置为1叫做置位或者打开，这篇文章会沿用这些术语。
秘籍1：判断一个整数是奇数还是偶数
if (( x & 1) == 0 ) {
//x是偶数
} else {
//x是奇数
}
大家也许都知道这个技巧。这个方法的理论基础是一个整数如果是奇数，那么它的二进制表示的最低位，也就是b0必须为1，相应的如果它是偶数，那么它的最低位必须为0。
二进制表示中b0只可能是0或者1，而x跟1的与运算可会将其他位置0，而最低位b0还是保持原样，所以当b0为0的时候，也就是x为偶数的时候，x&1会等于0，反之就是奇数。
来看一个具体的例子：整数43，它是奇数。它的二进制表示为00101011，最低位是1，再来看看它跟1的与运算：
00101011
& 00000001 (注意1的二进制表示是 00000001)
--------
00000001
43与1的与运算消除了高位数的1，最终b7-b1所有位的值都是0，而b0会被保留，最终结果为1，所以它是奇数。
再来看看-43。首先我们要记住一个规则，负数的二进制补码表示是对它对应的正数（就是它的绝对值）的二进制位全部求反，然后再加1。所以-43的二进制表示就是11010101，b0位为1，依旧是奇数。（如果用反码表示整数的话，这个技巧将无效）。
再来看一个偶数：98，它的二进制位表示为01100010，它与1的与运算为：
01100010
& 00000001
--------
00000000
运算结果为0。这意味着98的b0位为0，所以它是偶数。
再看看-98，它的二进制表示是10011110，b0位依旧为0，与1进行与运算的结果还是0，偶数！
秘籍2：判断第n位是否已置位
if ( x & ( 1<<n)) {
//第n位已设置
} else {
//第n位未设置
}
在秘籍1中x & 1 可以判断最低位是否置位。这个秘籍会对第一个秘籍做一点改进从而可以判断任意位是否置位。它的实现方式就是将1左移n位，然后与x进行与运算，得到的结果除了第n位外，其他都都为0。先看几个示例：
1 00000001 (相对于1<<0) 1<<1 00000010 1<<2 00000100 1<<3 00001000 1<<4 00010000 1<<5 00100000 1<<6 01000000 1<<7 10000000
如果最终的结果为0，那么说明x的第n位也为0，如果为1的话，那么第n位就为1。
再看几个例子：
122 & (1<<3)
122的二进制表示为01111010，与1左移三位后的数进行与运算的结果为00001000。
01111010
& 00001000
--------
00001000
最终结果不为0，所以122的第三位已置位。
再看看-33的第5位的情况：
11011111 (-33二进制位表示)
& 00100000 (1<<5)
--------
00000000
结果为0，所它的第5位没有置位。
秘籍3：将第n位置位
y = x | (1<<n)
这个秘籍结合了移位(<<)和或(|)运算。1<<n大家都见识过，1左移n位后再与x进行或运行，可以将x的第n位设置为1。
或运算的规则是，与0进行或运算结果保持不变，0与0进行或运算结果还是0，1与0进行或运算结果还是1；与1进行或运算结果总是1。所以上面的运算中x的二进制位中的第n位是与1进行或运算，结果总是为1，而其他位都是与0进行或运算，结果保持不变，所以最终得到的结果是将x的第n位设置为1，其他位保持不变。
将整数120的第2位进行置位：
01111000 (120的二进制表示)
| 00000100 (1<<2)
--------
01111100
再对-120的第6位置位：
10001000 (-120的二进制表示)
| 01000000 (1<<6)
--------
11001000
秘籍4：重置第n位
y = x & ~(1<<n)
这里使用了非运算(~)，对1<<n进行非运算的结果是第n为为0，其他位都为1。
我们来看看n为不同的值时~(1<<n)的运算结果：
~1 11111110 (相对于~(1<<0)) ~(1<<1) 11111101 ~(1<<2) 11111011 ~(1<<3) 11110111 ~(1<<4) 11101111 ~(1<<5) 11011111 ~(1<<6) 10111111 ~(1<<7) 01111111
将x与~(1<<n)进行与运算，得到的结果就是将x的第n位重置为0，而其他位保持不变。这点很容易看出，因为任何数（0或者1）与1进行与运算的结果都会保持不变，而与0进行与运算的结果都是0。
如果要将127的第4位重置为0，只需要127 & ~(1<<4)：
01111111 (127的二进制表示)
& 11101111 (~(1<<4))
--------
01101111
秘籍5：反转第n位
y = x ^ (1<<n)
这里使用了异或运算（^）。异或运算的规则是，如果两个数相同，那么结果为0，如果不同，则结果将为1。那为何上面的运算可以反转第n位呢？
1<<n的第n位为1，其他位都为0。如果x的第n位为1，那么x与1<<进行异或运算后第n会变为0，如果它为0，那么它会变成1。而其他的位与0进行异或运算会保持不变，0还是0，1依旧是1，这样x的第n位就被反转了。
将01110101的第5位反转：
01110101
^ 00100000
--------
01010101
如果第5位开始的时候为0，结果又会是什么样的呢：
01010101
^ 00100000
--------
01110101
秘籍6：关闭右侧第一个为1的位
y = x & (x-1)
前面都是一些简单的位操作技巧，如果你了解基本的位操作运算法则，那么这些技巧都很容易理解，现在开始来一些有意思的！！
这个秘籍会关闭右侧第一个为1的位。先用一个示例说明它是什么意思，假设有一个整数的二进制位表示为00101010（右侧第一个为1的位标为红色），关闭这一位以后它就变成了00101000。如果整数为00010000，那么关闭右侧第一个为1的位以后它将变成0，因为它只有一个为1的位。
下面是一些示例：
01010111 (x)
& 01010110 (x-1)
--------
01010110
01011000 (x)
& 01010111 (x-1)
--------
01010000
10000000 (x = -128)
& 01111111 (x-1 = 127 (溢出))
--------
00000000
11111111 (x = 所有位都为1)
& 11111110 (x-1)
--------
11111110
00000000 (x = 所有位都为0)
& 11111111 (x-1)
--------
00000000
这是怎么实现的呢？
如果你仔细观察上面给出的示例，你会发现上面的运算有一个规律，它只有两种可能的情况：
-
如果一个数有一个为1的位，也就是它非0。假设这个数的二进制表示为n位，第i位为右侧第一个为1的位，那么它的第i-1位到第0都为0，我们用下面的方式来表示这个数：
x ? ? 1 0 0 bn bn-1 ... bi bi-1 ... b0
bnbn-1..bibi-1...b0是x的n位二进制表示，?表示对应位的值不明确，可能是0，也可能是1，我们再看下x-1的二进制表示：
x-1 ? ? 0 1 1 bn bn-1 ... bi bi-1 ... b0
很明显x & (x-1)的结果为：
x & (x-1) ? ? 0 0 0 bn bn-1 ... bi bi-1 ... b0
x的bn...bi+1都保持不变，而bi-1...b0位也保持不变，依旧为0，只是bi位变成了0，这就成功关闭了x的第i位。
-
另外一种特殊情况是这个数为0，没有为1的位。它与1相减的结果为-1，也就是11111111（补码表示），而0与这个数进行与运算结果还是0，而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 = 全部为1)
& 00000001 (-x)
--------
00000001
00000000 (x = 所有位都为0, 不存在右侧第一个为1的位)
& 00000000 (-x)
--------
00000000
这个技巧之所以有效是因为二进制补码的关系。在二进制补码表示中-x就是~x+1，也就是求反加1，这个秘籍跟前一个一样，也有两种不同的情况：
-
首先假设我们的二进制数有n位，而第i位数是右侧的第一个为1的位，我们将其定义为bi，所以第i位将整个数分成了两部分，一部分是第一位右侧的，一共有i个位，我们将其定义为bi-1、bi-2...b0，这些位上面的数值都为0（因为bi是右侧的第一个为1的位），而第i位左侧的位我们定义为bi+1、bi+2....bn。所以我们的x的二进制表示以及它们的值就是（?表示值未知）：
x ? ? ? ? 1 0 0 bn bn-1 … bi+2 bi+1 bi bi-1 … b0我们先来计算-x，-x=~x+1，所以我们先计算~x（~?表示?所代表值的求反）：~x ~? ~? ~? ~? 0 1 1 bn bn-1 … bi+2 bi+1 bi bi-1 … b0再进行进行+1：-x ~? ~? ~? ~? 1 0 0 bn bn-1 … bi+2 bi+1 bi bi-1 … b0所以我们可以查看到-x的bibi-1...b0的值跟x的相同，而它第i位左侧的位(i+1...n)则是对x中相应的位进行求反运算后的值，所以我们用x跟-x进行与运算的结果就是:x &-x 0 0 1 0 0 bn … bi … b0最终只有第i位也就是右侧第一个为1的位是置位的。 - 第二种情况就是x为0的特殊情况，不存在为1的位，所以也不存在右侧第一个为1的位，而-x也为0，0跟0进行与算术最终结果也为0，这是正确的。
秘籍8：将右侧第一个为1的位的右侧所有位置1
y = x | (x-1)
通过上面的几个秘籍，我们可以发现x右侧第一个为1的位的右侧的所有位的值都是0（有点拗口），通过上面的运行可以将这些位全部置为1。来个具体的例子，假设x为01010000，运算之后的结果为01011111。
不过这个秘籍并非总是有效，当x=0的时候的结果为-1，二进制表示就是所有位都为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
现在我们来证明下这个等式，当然证明过程也不会非常严谨，毕竟这也不是一篇论文，只是一篇博客而已。跟之前的证明一样，这有两种情况，我们这次先讨论特殊情况：
- 刚才已经说了，特殊情况下并不能得到我们想要的结果，因为当x=0，x-1=-1，-1的二进制表示为11111111，所以全1与全0进行与运算最终结果还是全1，不过如果我们把这个逻辑改一下，当x=0的时候，如果x有n位，我们假设n+1位为1，那么这个运算结果就是正确的，跟之前的逻辑是相符的，最终都是右侧第一个为1的位的右侧所有位都置1了。
-
在通常情况下，我们假设x有n位，它的二进制位表示为bnbn-1bn-2....b0。假设第i位为1（0<=i<=n)，现在先看下x的n位表示（?代表指定位的值）
x ? ? ? ? 1 0 0 bn bn-1 … bi+2 bi+1 bi bi-1 … b0再看下x-1的n位表示：x-1 ? ? ? ? 0 1 1 bn bn-1 … bi+2 bi+1 bi bi-1 … b0很明显这两个进行或运算之后得到的结果为：x | (x -1) ? ? ? ? 1 1 1 bn bn-1 … bi+2 bi+1 bi bi-1 … b0我们可以一眼看出bi到bn的所有位的值保持不变，而b0到bi-1的位的值都变成了1。
9. 分离右侧第一个为0的位
y = ~x &(x+1)
这个跟第七个秘籍正好相反。在这里是找到右侧第一个为0的位，最终将这一位设置为1，而将其他位都设置为0。例如我们有一个数的二进制表示为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 = 全1，不存在右侧第一个为0的位)
--------
00000000 (~x)
& 00000000 (x+1)
--------
00000000
00000000 (x)
--------
11111111 (~x)
& 00000001 (x+1)
--------
00000001
首先讨论特殊情况——全1的情况，如果全1的话，没有为0的位，~x将为00000000，x+1为00000001，它们进行与运算的结果为00000000，correct！
再来看一般情况，依旧用之前的分析方法：
x
? ? 0 1 1
bn bn-1 … bi … bi-1 … bi
~x
~? ~? 1 0 0
bn bn-1 … bi … bi-1 … bi
x+1
? ? 1 0 0
bn bn-1 … bi … bi-1 … bi
一目了然，~x &(x+1)的结果为：
~x | (x+1)
0 0 1 0 0
bn bn-1 … bi … bi-1 … bi
成功将第i位置位，其他的位都为0。
10. 打开右侧第一个为0的位（设置为1）
y = x | (x+1)
这个秘籍说将右侧第一个为0的位设置为1，其他位保持不变。这是最后一个秘籍，就不多说废话了，直接上例子：
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 = 全1，不存在右侧第一个为0的位)
| 00000000 (x+1)
--------
11111111
00000000 (x)
| 00000001 (x+1)
--------
00000001
还是先看特殊情况，全1的时候x+1的结果为0，11111111与00000000进行或运算结果为11111111，没有需要置位的，结果不变，正确无比！
再来看一般情况：
x
? ? 0 1 1
bn bn-1 … bi … bi-1 … bi
x+1
? ? 1 0 0
bn bn-1 … bi … bi-1 … bi
x | (x+1)
? ? 1 1 1
bn bn-1 … bi … bi-1 … bi
结果也是很显然的。
好了，就到这里了，关于二进制位的运算还有很多有趣的东西，有兴趣可以去看一本名为Hacker's Delight的书，这本书有中文版，名字叫算法心得。