格雷码（Gray code）

网上很多文章和视频提到格雷码（Gray code），和计算公式(^ 表示异或, >> 是右移位):

 num ^ (num >> 1) 

但是没看到解释为什么，这里尝试用一种简单的方式理解一下（不是严谨的数学方法）

我们先来看看怎么产生格雷码

从一位的开始，这个简单：

Decimal	Binary	Gray
0	0	0
1	1	1

利用1位的格雷码扩展到2位很简单， 先把现有的格雷码镜像一下，然后在上半部分前面加0，下半部分前面加1, 我们先来镜像：

Decimal	Binary	Gray
0	00	0
1	01	1
2	10	1
3	11	0

然后加0和1

Decimal	Binary	Gray
0	00	00
1	01	01
2	10	11
3	11	10

从这个过程我们可以看到

1. 上下两部分中，相邻的代码只有一位变化。原因很简单，我们用的是已有的格雷码，即便镜像了，相邻位变一位这个属性不会变
2. 通过添加0和1，我们把原来格雷码表示的范围加倍了。而且不会产生重复
3. 上半部分的最后一个编码和下半部分第一个编码，只有最高位不同

同时考虑这三点，这个格雷码的产生方法是正确的

扩展到3位也一样，先镜像现有的，然后结果的上半部分前缀0，下半部分前缀1:

Decimal	Binary	Gray
0	000	000
1	001	001
2	010	011
3	011	010
4	100	110
5	101	111
6	110	101
7	111	100

我们可以用这个方法继续产生4位，5位，到任意位数的格雷码

现在我们来看看num ^ (num >>1 ) 是为什么

我们用3位的数字(0-7)来演示，原因是我们可以用之前产生的表来对照。

考虑数字2和6。6的二进制是0b110（我在二进制前面放0b，这样不会混淆），通过查表，6应该在表格的下半部分，2的二进制是0b010，在表的上半部分。然后你会发现，这个6和2的二进制表示的第一个bit和格雷码的第一个bit一样。其实当然是一样的，想一下，3位二进制数一半以0开始，一半以1开始，我们产生格雷码的时候，上一半是0，下一半是1。

现在来看剩下的位数，对于6，我们要看0b10（0b110去掉第一位），对于2，我们要看0b10(0b010去掉第一位）。这两个数碰巧一样。

如果查看2位的格雷码表，0b10的在下半部分(因为第一位是1)。对于数字2，第二位的格雷码和二进制码一样。

现在关键来了，对于数字6，由于它在3位格雷码的下半部分，所以第二位的0和1位置和正常的顺序是反过来的（因为从第二位开始，下半部分都是是镜像的结果），所以0b10在虽然在2位的格雷码上第二位是1，反过来之后就变成0了。如果第二位是0，比如数字4，同样的，由于它在下半部分，第二位要反过来，变成1。 

我们可以重复这个过程，看到前一位是1，就把下一位反过来，如果前一位是0，就不变。直到最后一位。列一个表格更加清晰：

前一位	当前位	格雷码
0	0	0
0	1	1
1	0	1
1	1	0

这不就是异或（XOR）吗!!
所以每一位的格雷码就是二进制码的前一位异或当前位，也就是

num ^ ( num >> 1)