每日算法 — 使用java实现格雷码：二进制反射生成与位运算技巧

算法背景

格雷码（Gray Code）是一种二进制数字系统，其特点是任意两个相邻编码之间仅有一位不同。该编码由Frank Gray于1953年申请专利，在数字通信、卡诺图简化、旋转编码器、遗传算法等领域有广泛应用。n位格雷码共有 $2^n$ 个编码，形成闭环时首尾也仅有一位差异（循环格雷码）。

核心思想

n位格雷码可以通过递归反射构造：先列出n-1位格雷码，然后将其镜像复制并在前半部分最高位补0、后半部分最高位补1。更高效的方法是直接通过位运算将二进制数转换为格雷码：$G(n) = n \oplus (n >> 1)$。逆转换则利用前缀异或还原原始值。

Java实现

import java.util.ArrayList;
import java.util.List;

/**
 * 格雷码（Gray Code）实现
 * 相邻编码仅有一位不同的二进制编码系统
 */
public class GrayCode {

    /**
     * 生成n位格雷码序列（递归反射法）
     * 核心思想：n位格雷码 = (n-1位格雷码前补0) + (n-1位格雷码镜像后前补1)
     */
    public static List<Integer> generateGrayCodeRecursive(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0); // 0位格雷码只有一个值0

        for (int i = 0; i < n; i++) {
            int size = result.size();
            // 镜像复制并在最高位补1
            for (int j = size - 1; j >= 0; j--) {
                result.add(result.get(j) | (1 << i));
            }
        }

        return result;
    }

    /**
     * 生成n位格雷码序列（位运算法，O(2^n)时间）
     * 公式：G(i) = i ^ (i >> 1)
     */
    public static List<Integer> generateGrayCodeFormula(int n) {
        List<Integer> result = new ArrayList<>();
        int total = 1 << n; // 2^n

        for (int i = 0; i < total; i++) {
            result.add(i ^ (i >> 1));
        }

        return result;
    }

    /**
     * 生成n位格雷码的二进制字符串表示
     */
    public static List<String> generateGrayCodeBinary(int n) {
        List<String> result = new ArrayList<>();
        int total = 1 << n;

        for (int i = 0; i < total; i++) {
            int gray = i ^ (i >> 1);
            result.add(toBinaryString(gray, n));
        }

        return result;
    }

    /**
     * 将整数转换为指定位数的二进制字符串
     */
    private static String toBinaryString(int num, int bits) {
        StringBuilder sb = new StringBuilder();
        for (int i = bits - 1; i >= 0; i--) {
            sb.append((num >> i) & 1);
        }
        return sb.toString();
    }

    /**
     * 二进制转格雷码
     * 公式：G = B ^ (B >> 1)
     */
    public static int binaryToGray(int binary) {
        return binary ^ (binary >> 1);
    }

    /**
     * 格雷码转二进制
     * 原理：B[i] = G[i] ^ B[i+1]（从最高位开始逐位还原）
     */
    public static int grayToBinary(int gray) {
        int binary = 0;
        // 从最高位到最低位逐位恢复
        for (int i = 31; i >= 0; i--) {
            int mask = 1 << i;
            // 当前二进制位 = 格雷码当前位 ^ 已恢复的高位前缀异或
            if (i == 31) {
                binary |= (gray & mask);
            } else {
                // 更简洁的方法：不断右移并异或
            }
        }

        // 更简洁的实现：
        binary = gray;
        binary ^= (binary >> 1);
        binary ^= (binary >> 2);
        binary ^= (binary >> 4);
        binary ^= (binary >> 8);
        binary ^= (binary >> 16);

        return binary;
    }

    /**
     * 格雷码转二进制（逐位法，更直观）
     */
    public static int grayToBinarySimple(int gray) {
        int binary = gray;
        int shift = 1;
        while ((gray >> shift) != 0) {
            binary ^= (gray >> shift);
            shift++;
        }
        return binary;
    }

    /**
     * 验证格雷码序列的正确性
     * 检查：1. 所有元素唯一 2. 相邻元素仅有一位不同 3. 首尾仅有一位不同（循环）
     */
    public static boolean isValidGrayCode(List<Integer> grayCodes, int n) {
        int expectedSize = 1 << n;
        if (grayCodes.size() != expectedSize) {
            return false;
        }

        // 检查所有元素唯一
        boolean[] seen = new boolean[expectedSize];
        for (int code : grayCodes) {
            if (code < 0 || code >= expectedSize || seen[code]) {
                return false;
            }
            seen[code] = true;
        }

        // 检查相邻元素仅有一位不同
        for (int i = 0; i < grayCodes.size(); i++) {
            int next = grayCodes.get((i + 1) % grayCodes.size());
            int diff = grayCodes.get(i) ^ next;
            // diff必须是2的幂次（仅有一位为1）
            if (diff == 0 || (diff & (diff - 1)) != 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * 计算两个格雷码之间的海明距离（不同位数）
     */
    public static int hammingDistance(int a, int b) {
        int xor = a ^ b;
        int count = 0;
        while (xor != 0) {
            count++;
            xor &= (xor - 1); // 清除最低位的1
        }
        return count;
    }

    /**
     * 生成汉诺塔问题的移动序列（格雷码与汉诺塔一一对应）
     * 格雷码第i位变化对应移动第i个盘子
     */
    public static List<String> hanoiFromGrayCode(int n) {
        List<String> moves = new ArrayList<>();
        List<Integer> gray = generateGrayCodeFormula(n);

        // 三根柱子：A（源）、B（辅助）、C（目标）
        char[] pegs = {'A', 'B', 'C'};

        for (int i = 1; i < gray.size(); i++) {
            int diff = gray.get(i) ^ gray.get(i - 1);
            int disk = Integer.numberOfTrailingZeros(diff); // 变化的位对应盘子编号

            // 盘子的移动方向取决于盘号的奇偶性和当前步数
            int from = (i >> (disk + 1)) % 3;
            int to = ((i >> (disk + 1)) + 1 + (disk % 2)) % 3;

            moves.add("移动盘子 " + (disk + 1) + " 从 " + pegs[from] + " 到 " + pegs[to]);
        }

        return moves;
    }

    /**
     * 打印格雷码序列及其二进制形式
     */
    public static void printGrayCode(int n) {
        List<Integer> grayCodes = generateGrayCodeFormula(n);
        List<String> binaryCodes = generateGrayCodeBinary(n);

        System.out.println(n + " 位格雷码序列:");
        System.out.println("十进制\t二进制\t与前一项差异");
        System.out.println(grayCodes.get(0) + "\t" + binaryCodes.get(0) + "\t-");

        for (int i = 1; i < grayCodes.size(); i++) {
            int diff = grayCodes.get(i) ^ grayCodes.get(i - 1);
            int bit = Integer.numberOfTrailingZeros(diff);
            System.out.println(grayCodes.get(i) + "\t" + binaryCodes.get(i) + 
                "\t第 " + bit + " 位变化");
        }
    }

    public static void main(String[] args) {
        System.out.println("=== 格雷码生成（3位） ===");
        printGrayCode(3);

        System.out.println("\n=== 递归法与公式法对比（4位） ===");
        List<Integer> recursive = generateGrayCodeRecursive(4);
        List<Integer> formula = generateGrayCodeFormula(4);
        System.out.println("递归法: " + recursive);
        System.out.println("公式法: " + formula);
        System.out.println("结果相同: " + recursive.equals(formula));

        System.out.println("\n=== 转换验证 ===");
        int[] testValues = {0, 1, 2, 3, 4, 5, 6, 7};
        for (int v : testValues) {
            int gray = binaryToGray(v);
            int back = grayToBinary(gray);
            System.out.println("二进制 " + v + " -> 格雷码 " + gray + " -> 还原 " + back);
        }

        System.out.println("\n=== 格雷码序列验证 ===");
        for (int n = 1; n <= 5; n++) {
            List<Integer> codes = generateGrayCodeFormula(n);
            boolean valid = isValidGrayCode(codes, n);
            System.out.println(n + " 位格雷码验证: " + (valid ? "通过" : "失败"));
        }

        System.out.println("\n=== 汉诺塔移动序列（3个盘子） ===");
        List<String> hanoi = hanoiFromGrayCode(3);
        for (String move : hanoi) {
            System.out.println(move);
        }
    }
}

复杂度分析

算法优势与适用场景

优势：
– 位运算公式极其简洁，实现仅需一行代码
– 相邻编码仅一位变化，减少数字电路中的竞争冒险
– 与汉诺塔问题存在一一对应关系，趣味性强

适用场景：
– 数字电路与旋转编码器设计
– 遗传算法中的染色体编码（减少变异距离）
– 卡诺图逻辑化简
– 组合优化问题的状态空间遍历