题目
Create functions to encode a number to and decode
a number from Gray code. Display the normal binary
representations, Gray code representations, and
decoded Gray code values for all 5-bit binary
numbers (0-31 inclusive, leading 0's not necessary).
There are many possible Gray codes. The following
encodes what is called "binary reflected Gray code."
Encoding (MSB is bit 0, b is binary, g is Gray code):
if b[i-1] = 1
g[i] = not b[i]
else
g[i] = b[i]
Decoding (MSB is bit 0, b is binary, g is Gray code):
b[0] = g[0]
for other bits:
b[i] = g[i] xor b[i-1]
背景
典型的二进制格雷码（Binary Gray Code）简称格雷码，因1953年公开的弗兰克·格雷（Frank Gray，18870913-19690523）专利“Pulse Code Communication”而得名，当初是为了通信，现在则常用于模拟－数字转换和位置－数字转换中。法国电讯工程师波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用过的波特码相当于它的一种变形。1941年George Stibitz设计的一种8元二进制机械计数器正好符合格雷码计数器的计数规律。
二进制码→格雷码 说明
此方法从对应的n位二进制码字中直接得到n位格雷码码字，步骤如下：
对n位二进制的码字，从右到左，以0到n-1编号
如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变） [4]
公式表示：
关注点：
- 顺序是右到左，和我们通常使用的序号是反的。
- 第n-1位不变，比如 011 0是第n-1位，第n位认为是0，相当于在前面加了0变成 0011，0和 0 or 1 异或不会改变原来的值。
输入 - B : 011 转换 过程 1^1 =1 1^0=0 0^0=0(第n-1位不变) 输出 G : 010
格雷码→二进制码 说明
从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
公式表示：
（G：格雷码，B：二进制码）
关注点
- 顺序不变， n-1不变。b[n-1] 异或 g[n-2] = b[n-2] 以此类推到第0位。
- 输入G: 111 b[n-1] = g[n-1] b[n-2] = b[n-1] 异或 g[n-2] 输出 B: 101
测试代码
public class GrayCodeTest {
@Test
public void should_001_encode_001(){
String input="001";
String except ="001";
String result = GrayCode.encode(input);
assertEquals(except,result);
}
@Test
public void should_010_encode_011(){
String input="010";
String except ="011";
String result = GrayCode.encode(input);
assertEquals(except,result);
}
@Test
public void should_0111_encode_0100(){
String input="0111";
String except ="0100";
String result = GrayCode.encode(input);
assertEquals(except,result);
}
@Test
public void should_0100_decode_0111(){
String input="0100";
String except ="0111";
String result = GrayCode.decode(input);
assertEquals(except,result);
}
@Test
public void should_100_decode_111(){
String input="100";
String except ="111";
String result = GrayCode.decode(input);
assertEquals(except,result);
}
@Test
public void should_001_decode_001(){
String input="001";
String except ="001";
String result = GrayCode.decode(input);
assertEquals(except,result);
}
}
实现代码
public class GrayCode {
public static String encode(String input) {
int len = input.length();
String[] result = new String[len];
for (int i = len-1; i>0 ; i--) {
result[i]=String.valueOf(input.charAt(i)^input.charAt(i-1));
}
result[0]=String.valueOf(input.charAt(0));
return String.join("",result);
}
public static String decode(String input) {
int len = input.length();
String[] result = new String[len];
for (int i = 0; i<=len-1 ; i++) {
if(i==0){
result[i] = String.valueOf(input.charAt(0));
}else {
result[i] = String.valueOf(result[i-1].charAt(0)^input.charAt(i));
}
}
return String.join("",result);
}
}
Gray Code 理解如何转码编码需要花些时间，实现代码并不复杂。写代码就是需要理解问题，通常需要手工实现然后代码实现。
