明波的部落格

网上很多文章和视频提到 格雷码（ 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 从这个过程我们可以看到 上下两部分中，相邻的代码只有一位变化。原因很简单，我们用的是已有的格雷码，即便镜像了，相邻位变一位这个属性不会变 通过添加0和1，我们把原来格雷码表示的范围加倍了。而且不会产生重复 上半部分的最后一个编码和下半部分第一个编码，只有最高位不同 同时考虑这三点，这个格雷码的产生方法是正确的 扩展到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。 ...

你很可能听说过，计算机上使用的是二进制，也就是所有的东西都是0和1构成。那么为什么0和1可以表达各种信息呢？比如现在这篇文章，为什么这个也是0和1构成的，为什么看不出来0和1在哪里？ 让我们先换一种方式理解二进制，0和1不是数学上的0和1，而是表示两个不一样的状态，比如灯是不是开着，一个人是男生还是女生。如果用1表示男生，0表示女生，那么10001就表示2个男生，3个女生。如果1表示灯开着，0表示灯关掉，用二进制表示3盏灯的状态就可能是110。也就是说虽然都是0和1，我们可以自己定义他们表达的意思。 要点1：相同数据可以表达不同的意义 那么如果我们需要表达的意思不单单是只有两种呢？比如我们需要表达一年的四个季度，那么需要4中状态，表达一个人的年纪，那就需要可以表示0到150（当然以后也许要200，300甚至更多），只有两个状态不够了，怎么解决？我们可以通过用多个0和1表达一个意思。比如针对四季，我们可以用00，01，10和11分别表示春夏秋冬。 一位的0和1（术语叫一个bit），表示两个状态，在这个两个状态基础上，再增加一位，那么因为新增加的这位也是两个状态，可以把原来能表示的状态增加一倍。比如四季的情况，原来有00，01，10和11四个状态，只需要2位, 现在增加一位，如果新增的位数值是0，那么0和之前的4个状态合起来有4个状态，分别是0(00),0(01), 0(10)和0(11)，括弧里是原来的状态，如果新增的位数值是1，和原来的4个状态合起来，又可以表达4个新状态，分别是1(00),1(01),1(10)和1(11)，总的状态是之前的2倍，也就是4x2=8种状态。再增加一位，变成4个bit，能表达的状态是3个bit的2倍，也就是8x2=16。以此类推，我们可以用16个bit表示2的16次方种状态，也就是65536种（6万5千多），或者我们可以用32个bit表示2的32次方种状态，也就是4294967296种（4百20多万），可以表达足够多的意思，比如所有的汉字，数学符号，英文符号等等。 回到表达年纪的问题，我们可以用7位二进制表达128种状态，8位表示256种状态，也就是8位就足够表达从0到150岁了。 要点2：只要位数够多，我们可以用0和1表达足够多的信息 现在我们知道我们可以用二进制表达任何意思，也知道可以通过增加位数提高可以表...