格雷码计算

格雷码 Gray Code，又叫循环二进制码或反射二进制码，基本特点：

• 任意相邻两个数只有一位二进制数不同
• 首尾两个数也只有一位二进制数不同（所以叫循环二进制码）

LeetCode上两道Gray Code题目：

89. Gray Code

1238. Circular Permutation in Binary Representation

一、格雷码与二进制码转换

Binary –> Gray code

1. G(n-1) = B(n-1)
2. G(i) = B(i+1) xor B(i), i = 0, 1, 2, … n-2

int decimal2Gray(int x) {
  return x ^ x>>1;
}

Gray code –> Binary

1. B(n-1) = G(n-1)
2. B(i-1) = B(i) xor G(i-1), i = 1, 2, 3, … n-1

int gray2Decimal(int x) {
  int b = x;
  while (x > 0) {
    x >>= 1;
    b ^= x;
  }
  return b;
}

二、异或

二进制的位运算，用符号 XOR 或者 ^ 表示，运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。

性质：

1. 交换律，A ^ B = B ^ A
2. 结合律，A ^ (B ^ C) = (A ^ B) ^ C
3. 任意X，X ^ X = 0，X ^ 0 = X
4. 自反性，A ^ B ^ B = A ^ 0 = A

应用：

1. 一个数组存放若干整数，一个数出现奇数次，其余数均出现偶数次，找出这个出现奇数次的数？

   全部异或，偶数次的数X，X ^ X = 0，全部异或的结果即为奇数次的这个数。