算法简介
Gray Code（格雷码）是一种二进制编码系统，由Frank Gray于1947年申请专利。其核心特性是：任意两个相邻的编码之间只有一位二进制数不同。这一特性使得格雷码在数字电路、通信协议、编码器设计、组合数学和算法竞赛中有着广泛的应用。
与普通的二进制编码相比，格雷码在状态转换时只会翻转一位，从而避免了多比特同时变化导致的竞争冒险（Race Condition）问题。
本文用Java实现格雷码的多种生成算法，重点讲解二进制反射法、位运算直接构造以及格雷码在组合枚举中的应用。
核心算法设计
1. 格雷码的基本性质
对于n位格雷码，共有2^n个编码，满足：
– G(0) = 0
– 相邻两个格雷码的汉明距离为1
– 首尾两个格雷码的汉明距离也为1（循环格雷码）
public class GrayCodeGenerator {
private int n; // 位数
public GrayCodeGenerator(int n) {
if (n < 1 || n > 31) {
throw new IllegalArgumentException("位数n必须在1-31之间");
}
this.n = n;
}
/**
* 打印格雷码列表
* @param codes 格雷码数组
*/
public void printCodes(List<Integer> codes) {
for (int i = 0; i < codes.size(); i++) {
String binary = String.format("%" + n + "s",
Integer.toBinaryString(codes.get(i))).replace(' ', '0');
System.out.printf("G(%d) = %s = %d%n", i, binary, codes.get(i));
}
}
/**
* 计算两个整数的汉明距离（不同位的数量）
* 用于验证格雷码的正确性
*/
public int hammingDistance(int a, int b) {
return Integer.bitCount(a ^ b);
}
/**
* 验证一个编码序列是否为合法的格雷码
* @param codes 编码序列
* @return 是否合法
*/
public boolean validate(List<Integer> codes) {
if (codes.size() != (1 << n)) return false;
// 检查相邻编码的汉明距离是否为1
for (int i = 0; i < codes.size(); i++) {
int next = codes.get((i + 1) % codes.size());
if (hammingDistance(codes.get(i), next) != 1) {
return false;
}
}
return true;
}
}
2. 二进制反射法生成格雷码
最经典的格雷码生成方法是二进制反射法：
1. 1位格雷码：[0, 1]
2. n位格雷码：先列出n-1位格雷码，然后将其镜像翻转并在前面补1
public class GrayCodeGenerator {
/**
* 使用二进制反射法递归生成n位格雷码
* 时间复杂度：O(2^n)，空间复杂度：O(2^n)
*/
public List<Integer> generateByReflection() {
List<Integer> result = new ArrayList<>();
generateReflectionHelper(n, result);
return result;
}
private void generateReflectionHelper(int bits, List<Integer> result) {
if (bits == 0) {
result.add(0);
return;
}
// 先递归生成n-1位格雷码
generateReflectionHelper(bits - 1, result);
// 获取当前已生成的编码数量
int size = result.size();
// 镜像反射：倒序遍历已有编码，并在最高位补1
for (int i = size - 1; i >= 0; i--) {
int reflected = result.get(i) | (1 << (bits - 1));
result.add(reflected);
}
}
/**
* 使用迭代方式实现二进制反射法
* 避免递归深度过大
*/
public List<Integer> generateByReflectionIterative() {
List<Integer> result = new ArrayList<>();
result.add(0);
result.add(1);
for (int bits = 2; bits <= n; bits++) {
int size = result.size();
// 镜像反射并在最高位补1
for (int i = size - 1; i >= 0; i--) {
result.add(result.get(i) | (1 << (bits - 1)));
}
}
return result;
}
}
3. 位运算直接构造法
格雷码与二进制码之间存在直接的数学转换关系：
– 二进制码转格雷码：G(i) = i ^ (i >> 1)
– 格雷码转二进制码：通过逐位异或还原
public class GrayCodeGenerator {
/**
* 使用位运算公式直接生成第i个格雷码
* 公式：G(i) = i ^ (i >> 1)
* 这是最高效的单个格雷码计算方法
*/
public int grayCodeOf(int i) {
return i ^ (i >> 1);
}
/**
* 使用位运算公式生成所有n位格雷码
* 时间复杂度：O(2^n)，空间复杂度：O(2^n)
* 这是最高效的批量生成方法
*/
public List<Integer> generateByFormula() {
List<Integer> result = new ArrayList<>(1 << n);
for (int i = 0; i < (1 << n); i++) {
result.add(grayCodeOf(i));
}
return result;
}
/**
* 将格雷码转换回普通二进制码
* 原理：从最高位开始，每一位等于格雷码该位与二进制前一位的异或
* @param gray 格雷码
* @return 对应的二进制码
*/
public int grayToBinary(int gray) {
int binary = gray;
// 逐位恢复：binary ^= binary >> k，k = 1, 2, 4, 8, 16
binary ^= binary >> 1;
binary ^= binary >> 2;
binary ^= binary >> 4;
binary ^= binary >> 8;
binary ^= binary >> 16;
return binary;
}
/**
* 将二进制码转换为格雷码
* @param binary 二进制码
* @return 对应的格雷码
*/
public int binaryToGray(int binary) {
return binary ^ (binary >> 1);
}
}
4. 格雷码在子集枚举中的应用
格雷码的一个经典应用是高效枚举子集。由于相邻子集只相差一个元素，可以在O(1)时间内从一个子集切换到下一个子集，而不需要重新构建整个子集。
public class GrayCodeGenerator {
private String[] elements; // 集合元素
public GrayCodeGenerator(int n, String[] elements) {
this(n);
this.elements = elements;
}
/**
* 使用格雷码顺序枚举集合的所有子集
* 相邻两个子集只相差一个元素，切换时间为O(1)
*/
public void enumerateSubsets() {
int total = 1 << n;
int prevMask = 0;
System.out.println("空集");
for (int i = 1; i < total; i++) {
int gray = grayCodeOf(i);
int prevGray = grayCodeOf(i - 1);
// 找出发生变化的位
int diff = gray ^ prevGray;
int changedBit = Integer.numberOfTrailingZeros(diff);
boolean added = ((gray >> changedBit) & 1) == 1;
String action = added ? "加入" : "移除";
System.out.printf("步骤%d: %s元素 '%s'%n",
i, action, elements[changedBit]);
System.out.println(" 当前子集: " + maskToSet(gray));
}
}
/**
* 将掩码转换为元素集合的字符串表示
*/
private String maskToSet(int mask) {
StringBuilder sb = new StringBuilder("{");
boolean first = true;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
if (!first) sb.append(", ");
sb.append(elements[i]);
first = false;
}
}
sb.append("}");
return sb.toString();
}
/**
* 生成 Gray Code 顺序的掩码列表
* 适用于需要按格雷码顺序遍历所有状态的场景
*/
public int[] generateMaskSequence() {
int total = 1 << n;
int[] sequence = new int[total];
for (int i = 0; i < total; i++) {
sequence[i] = grayCodeOf(i);
}
return sequence;
}
}
5. 格雷码在旋转编码器中的应用
在实际的旋转编码器（如机械旋钮、电机编码器）中，格雷码被用来避免读取时的跳变错误。假设编码器有n个光电传感器读取n位编码，如果使用普通二进制编码，在边界位置（如0111→1000）多个位会同时翻转，可能导致短暂的错误读数。而格雷码保证每次只翻转一位，消除了这种不确定性。
public class GrayCodeGenerator {
/**
* 模拟旋转编码器的读取过程
* 展示格雷码如何避免多比特同时变化导致的错误
*/
public void simulateEncoder() {
System.out.println("=== 模拟3位旋转编码器 ===");
System.out.println("角度\t二进制\t格雷码\t变化位");
int prevBinary = 0;
int prevGray = 0;
for (int angle = 0; angle < 360; angle += 45) {
int step = angle / 45; // 8个位置
int binary = step;
int gray = grayCodeOf(step);
int binaryChanges = Integer.bitCount(binary ^ prevBinary);
int grayChanges = Integer.bitCount(gray ^ prevGray);
String binStr = String.format("%3s", Integer.toBinaryString(binary)).replace(' ', '0');
String grayStr = String.format("%3s", Integer.toBinaryString(gray)).replace(' ', '0');
System.out.printf("%d°\t%s\t%s\t二进制变化:%d 格雷码变化:%d%n",
angle, binStr, grayStr, binaryChanges, grayChanges);
prevBinary = binary;
prevGray = gray;
}
}
/**
* 演示汉诺塔问题与格雷码的对应关系
* n层汉诺塔的最优解恰好对应n位格雷码的遍历顺序
* 移动第k个盘子的步数 = 格雷码中第k位翻转的位置
*/
public void hanoiWithGrayCode(int disks) {
System.out.println("=== 汉诺塔与格雷码的对应关系（" + disks + "层）===");
int totalSteps = (1 << disks) - 1;
for (int step = 1; step <= totalSteps; step++) {
int gray = grayCodeOf(step);
int prevGray = grayCodeOf(step - 1);
int diff = gray ^ prevGray;
int disk = Integer.numberOfTrailingZeros(diff); // 移动的盘子编号
// 确定移动方向
int direction = ((step >> (disk + 1)) & 1) == 0 ? 1 : -1;
String[] pegs = {"A", "B", "C"};
int from = ((step >> (disk + 1)) * 2 + disk) % 3;
int to = (from + direction + 3) % 3;
System.out.printf("第%d步: 移动盘子%d 从%s到%s (格雷码变化位:%d)%n",
step, disk + 1, pegs[from], pegs[to], disk);
}
}
}
6. 完整测试与演示
public class GrayCodeGenerator {
public static void main(String[] args) {
System.out.println("=== Gray Code 格雷码生成器 ===\n");
// 1. 生成3位格雷码
GrayCodeGenerator gen3 = new GrayCodeGenerator(3);
System.out.println("3位格雷码（反射法）：");
List<Integer> codes3 = gen3.generateByReflection();
gen3.printCodes(codes3);
System.out.println("验证结果：" + gen3.validate(codes3));
System.out.println();
// 2. 生成4位格雷码（公式法）
GrayCodeGenerator gen4 = new GrayCodeGenerator(4);
System.out.println("4位格雷码（公式法）：");
List<Integer> codes4 = gen4.generateByFormula();
gen4.printCodes(codes4);
System.out.println("验证结果：" + gen4.validate(codes4));
System.out.println();
// 3. 二进制与格雷码互转演示
System.out.println("二进制与格雷码互转演示：");
for (int i = 0; i < 8; i++) {
int gray = gen3.binaryToGray(i);
int back = gen3.grayToBinary(gray);
System.out.printf("Binary %d -> Gray %d -> Binary %d%n", i, gray, back);
}
System.out.println();
// 4. 旋转编码器模拟
gen3.simulateEncoder();
System.out.println();
// 5. 子集枚举
String[] fruits = {"苹果", "香蕉", "橙子"};
GrayCodeGenerator genSubset = new GrayCodeGenerator(3, fruits);
System.out.println("格雷码顺序枚举子集：");
genSubset.enumerateSubsets();
System.out.println();
// 6. 汉诺塔与格雷码
gen3.hanoiWithGrayCode(3);
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 反射法生成 | O(2^n) | O(2^n) |
| 公式法生成 | O(2^n) | O(2^n) |
| 单个格雷码计算 | O(1) | O(1) |
| 格雷码↔二进制转换 | O(1) | O(1) |
| 验证 | O(2^n) | O(1) |
| 子集枚举 | O(2^n) | O(2^n) |
由于位运算在CPU中高度优化，实际运行速度极快。对于n≤20的应用场景，都可以在毫秒级完成。
扩展方向
- 平衡格雷码：在标准格雷码基础上，要求所有位的翻转次数尽可能均匀，适用于需要均衡磨损的存储设备。
- n维超立方体哈密顿回路：n位格雷码对应n维超立方体的一条哈密顿回路，相邻顶点恰好相差一维。
- 卡诺图简化：在数字逻辑设计中，格雷码顺序排列的卡诺图可以更方便地进行布尔函数的最小化。
小结
Gray Code格雷码是一种优雅的二进制编码方案，其核心优势在于相邻编码仅一位之差。通过简单的位运算公式G(i) = i ^ (i >> 1)即可在O(1)时间内计算任意位置的格雷码。这种编码不仅解决了数字电路中的竞争冒险问题，还在组合枚举、子集遍历、旋转编码器等场景中展现出独特的效率优势。理解格雷码的构造原理，是掌握位运算技巧和组合数学思维的重要一步。
