CSP-J 2024 第一轮 第 4 题：以下哪个序列对应数组0 至8 的4 位二进制格雷码（Gr...

题目

以下哪个序列对应数字 $0$ 至 $8$ 的 $4$ 位二进制格雷码（Gray code）？（  ）

选项

• A. 0000, 0001, 0011, 0010, 0110, 0111, 0101, 1000
• B. 0000, 0001, 0011, 0010, 0110, 0111, 0100, 0101
• C. 0000, 0001, 0011, 0010, 0100, 0101, 0111, 0110
• D. 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100

答案

D

题解

选 D。格雷码的特点是：相邻两个编码只有一位二进制位不同。

逐项检查：

• A：0101 → 1000，有 3 位不同，不符合。
• B：0111 → 0100，有 2 位不同，不符合。
• C：0010 → 0100，有 2 位不同，不符合。
• D：每相邻两个编码都只有 1 位不同，符合。

标准二进制格雷码也可以用公式计算： \[ G(n)=n\oplus(n\gg1) \] 即把 \(n\) 的二进制与它右移一位后的结果进行异或（相同为 0，不同为 1）。

例如 \(n=7\)： ``text 0111 ⊕ 0011 ------ 0100 ``

注意：题面有一处笔误，\(0\) 至 \(8\) 应有 9 个编码，而每个选项只有 8 个。D 实际列出的是 \(0\) 至 \(7\)；若包含 \(8\)，还应在末尾加上 1100。