首先声明这篇博客的创作过程，大部分文本来自“笨笨阿林”的原创文章。我在看完后加入了部分自己的理解，有些地方做了略微调整，比如将有些不易理解的地方重新解释，多余的话删除等；也在最后加入了一个例子来证实了一下在GB2312编码下从区位码到实际在计算机中存储的二进制字节流的转换过程。因此我将这篇文章定为原创，望理解。

下面是正文。

        GB2312等GB类汉字编码方案的具体实现方式是怎样的？区位码是什么？国标码是什么？内码、外码、字形码又是什么意思？它们是如何转换的，又为什么要这样转换？

        下面以GB2312为例来加以说明(由于GBK、GB18030是以GB2312为基础扩展而来，因此编码实现方式与GB2312一样)。

一、区位码

        整个GB2312字符集分成94个区，每区有94个位，每个区位上只有一个字符，即每区含有94个汉字或符号，用所在的区和位来对字符进行编码(实际上就是字符编号、码点编号)，因此称为区位码。
换言之，GB2312将包括汉字在内的所有字符编入一个94 * 94的二维表，行就是“区”、列就是“位”，每个字符由区、位唯一定位，其对应的区、位编号合并就是区位码。比如“中”字
在54区48位，所以“中”字的区位码是：5448（注意，GB类汉字编码为双字节编码，因此，45相当于高位字节，82相当于低位字节）。

（笨笨阿林原创文章，转载请注明出处）

二、国标码(交换码)

虽然GB2312为中文编码，我们也要使用到英文字母等字符，况且当时ASCII已经通用，所以要使GB2312能够兼容ASCII才行。so,为了兼容,GB2312在设计时避开了ASCII字符中的不可显示字符0000 0000 ~ 0001 1111(十六进制为0 ~ 1F，十进制为0 ~ 31)及空格字符0010 0000(十六进制为20，十进制为32)（为什么只避开ASCII中0~32的不可显示字符和空格字符，不避开其他字符呢？后面解释），国标码(又称为交换码)规定表示汉字的范围为(0010 0001，0010 0001) ~(0111 1110，0111 1110)，十六进制为(21，21) ~ (7E，7E)，十进制为(33，33) ~ (126，126)。

因此，必须将“区码”和“位码”分别加上(注意，一定是分别加上，因为区码和位码分别代表一个字节)20H(十六进制数，代表十进制中的32，H为十六进制数的后缀:Hexadecimal)，作为国标码。也就是说，国标码相当于将区位码向后偏移了32，以避免与ASCII字符中0~32的不可显示字符和空格字符相冲突。例如“中”字的区位码为5448，转为国标码的过程为，区码:(54+32)=86,位码:(48+32)=80，所以“中”字的国标码表示为：(86, 80)。十六进制为(56H, 50H)。

三、内码(机内码)

国标码还不能直接在计算机上使用，因为这样还是会和ASCII中的除控制字符外的其他字符冲突(冲突的结果就是导致乱码)。
拿“中”字举个例子，它的国标码中的高位字节为86，这会与ASCII中大写字母'V'冲突，低位字节为80，与'P'冲突。因此为避免这种情况，规定国标码中的每个字节的最高位都从0换成1，即相当于每个字节都再加上128(十六进制为80，即80H；二进制为1000 0000)，从而得到国标码的“机内码”表示，简称“内码”。由于ASCII码只用了一个字节中的低7位，利用这个特性，这个首位(最高位)上的“1”就可以作为识别汉字编码的标志，计算机在处理到首位是“1”的编码时就把它理解为汉字，在处理到首位是“0”的编码时就把它理解为ASCII字符。
“中”字从国标码转换为内码的过程为，高位字节:(86+128)=214,低位字节:(80+128)=208，所以“中”字的内码十进制表示为：(214,208)，十六进制表示为：(D6, D0)。
此时已经不再与ASCII冲突，完全兼容ASCII。因此，内码才是字符用GB2312编码后的在计算机中存储的形式。

总结一下：

    从区位码(国家标准定义) ---> 区码和位码分别+32(即+20H)得到国标码 ---> 再分别+128(即+80H)得到机内码(与ACSII码不再冲突)。

四、为什么要加上20H和80H？

首先谈谈为什么要加上20H：
当时在制定GB2312时，决定对ASCII中的可打印字符，也就是英文字母、数字和符号部分(33~126，127为不可打印的DEL)重新编入GB2312中，以两个字节表示，称之为全角字符 (全角字符在屏幕上的显示宽度为ASCII字符的两倍，后来也因此而将对应的ASCII字符称之为半角字符)。而对于ASCII中前32个不可显示也不可打印的控制字符(ASCII码为0~31)， 以及第33个可显示但不可打印的空格字符(ASCII码为32)等共33个不可打印字符的编码则直接沿用，不再重新编码。因为要保留这33个不可打印字符，就不能直接采用区位码作为计算机 直接处理的机内码，需要将区位码向后偏移32以避开冲突(为什么是偏移32，而不是偏移33？因为区位码中的区码和位码都是从1开始计数的，不像ASCII码是从0开始计数的)。
（笨笨阿林原创文章，转载请注明出处）

再谈谈为什么要加上80H：
很显然，如果直接采用国标码作为计算机直接处理的机内码的话，还将会产生另一个弊端，即用ASCII码编码的英文字符在GB2312编码环境中无法打开，一打开就会乱码。
因为国标码虽然相较于区位码避开了ASCII码中0~32的前33个不可打印字符，但并没有避开ASCII码中的英文字母、数字和符号(33~126，共94个字符，127为不可打印的DEL)等可打印字符。也就是说，国标码并不是完全兼容ASCII码的。
为了解决这个弊端，考虑到ASCII码只使用了一个字节中的低7位，最高位(即首位)为0，于是决定将国标码每个字节的最高位设为1(国标码的两个字节中的最高位都恒为0，即国标码中的每个字节实际上也只用了一个字节中的低7位)，这就是GB2312的机内码(即内码)，简称GB2312码。 这样一来就彻底区分开了ASCII码和GB2312码。这也是为什么国标码还要加上(80H，80H)才能得到机内码。

（笨笨阿林原创文章，转载请注明出处）

五、外码(输入码、输入法编码)

1.外码也叫输入码、输入法编码，是用来将汉字输入到计算机中的一组键盘符号，是作为汉字输入用的编码。
英文字母只有26个，可以把所有的字符都放到键盘上，而使用这种办法把所有的汉字都放到键盘上，是不可能的。所以汉字系统需要有自己的输入码体系，使汉字与键盘能建立对应关系。

2.目前常用的外码分为以下几类：
1）数字编码，比如区位码；
2）拼音编码，比如全拼、双拼、自然码等；

3）字形编码，比如五笔、表形码、郑码等。

六、字形码(字型码、字模码、输出码)

1.字形码，又称为字型码、字模码、输出码，属于点阵代码的一种。

        为了将汉字在显示器或打印机上输出，把汉字按图形符号设计成点阵图，就得到了相应的点阵代码(字形码)。也就是用0、1表示汉字的字形，将汉字放入n行*n列的正方形(点阵)内，该正方形共有n^2个小方格，每个小方格用一位二进制表示，凡是笔划经过的方格值为1，未经过的值为0。

2.显示一个汉字一般采用16×16点阵或24×24点阵或48×48点阵。已知汉字点阵的大小，可以计算出存储一个汉字所需占用的字节空间。
        比如，用16×16点阵表示一个汉字，就是将每个汉字用16行，每行16个点表示，一个点需要1位二进制代码，16个点需用16位二进制代码(即2个字节)，共16行，所以需要16行×2字节/行=32字节，即16×16点阵表示一个汉字，字形码需用32字节。

        因此，字节数=点阵行数×(点阵列数/8)。

3.为了将汉字的字形显示输出或打印输出，汉字信息处理系统还需要配有汉字字形库，也称字模库，简称字库，它集中了汉字的字形信息。
        字库按输出方式可分为显示字库和打印字库。用于显示输出的字库叫显示字库，工作时需调入内存。用于打印输出的字库叫打印字库，工作时无需调入内存。
        字库按存储方式也可分为软字库和硬字库。软字库以文件的形式存放在硬盘上，现多用这种方式。硬字库则将字库固化在一个单独的存储芯片中，再和其它必要的器件组成接口卡，插接在计算机上，通常称为汉卡。这种方式现已淘汰。

七、小结

        可以这样理解，为了在计算机内表示汉字而采取统一的编码方式所形成的汉字编码叫内码。为方便汉字输入而形成的汉字编码为外码，也叫输入码。为显示输出和打印输出汉字而形成的汉字编码为字形码，也称为字模码、输出码。

        计算机通过键盘输入的外码(重码时还需附加选择编号)对应于汉字内码，将汉字外码转换(即映射)为汉字内码，以实现输入汉字的目的；通过汉字内码在字模库(即字库)中找出汉字的字形码，将汉字内码转换(即映射)为汉字字形码，以实现显示输出和打印输出汉字的目的。

        事实上，英文字符的输入、处理和显示过程大致上也差不多，只不过英文字符不需要输入码(即外码)，直接在键盘上输入对应的英文字母即可。

（笨笨阿林原创文章，转载请注明出处）

八、实例证明区位码与内码之间的转换关系是成立的

解释：
首先调用“中”这个字符串的getBytes方法，我们使用的它的重载形式：

这个方法的作用是：使用参数指定的字符集，来编码这个String，称为一个字节序列，并把结果保存在一个字节数组中。

这里我们使用GB2312来编码“中”字，输出后得到结果：

            

为什么是负数呢？因为java中对数字的保存采用补码的形式(不了解补码的请看我的这篇博客)。将负数转换为正数为(214, 208)。将其转换为国标码为(214-128,208-128),也就是(86,80).再将国标码转换为区位码：(86-32, 80-32),(54,48)。

现在来查看一下“中”字的区位码：

        

完全相同，说明区位码和内码之间的转换关系成立。

GB2312、GBK、GB18030等GB系列汉字编码方案的具体实现方式是怎样的？区位码是什么？国标码是什么？内码、外码、字形码又是什么意思？它们是如何转换的，又为什么要这样转换？

下面以GB2312为例来加以说明。

 

一、区位码

1.

整个GB2312字符集分成94个区，每区有94个位，每个区位上只有一个字符，即每区含有94个汉字或符号，用所在的区和位来对字符进行编码(实际上就是码点值、码点编号、字符编号)，因此称为区位码(或许叫“区位号”更为恰当)。

换言之，GB2312将包括汉字在内的所有字符编入一个94*94的二维表，行就是“区”、列就是“位”，每个字符由区、位唯一定位，其对应的区、位编号合并就是区位码。

比如“万”字在45区82位，所以“万”字的区位码是：45 82（注意，GB类汉字编码为双字节编码，因此，45相当于高位字节，82相当于低位字节）。

2.

GB2312字符集中：

1）01~09区(682个)：特殊符号、数字、英文字符、制表符等，包括拉丁字母、希腊字母、日文平假名及片假名字母、俄语西里尔字母等在内的682个全角字符；

2）10~15区：空区，留待扩展；

3）16~55区(3755个)：常用汉字(也称一级汉字)，按拼音排序；

4）56~87区(3008个)：非常用汉字(也称二级汉字)，按部首/笔画排序；

5）88~94区：空区，留待扩展。

 

二、国标码(交换码)

1.

为了避开ASCII字符中的不可显示字符0000 0000 ~ 0001 1111(十六进制为0 ~ 1F，十进制为0 ~ 31)及空格字符0010 0000(十六进制为20，十进制为32)（至于为什么要避开、又为什么只避开ASCII中0~32的不可显示字符和空格字符，后文有解释），国标码(又称为交换码)规定表示汉字的范围为(0010 0001，0010 0001) ~ (0111 1110，0111 1110)，十六进制为(21，21) ~ (7E，7E)，十进制为(33，33) ~ (126，126)。

因此，必须将“区码”和“位码”分别加上32(十六进制为20，可写作20H或0x20，后缀H或前缀0x都可表示十六进制)，作为国标码。也就是说，国标码相当于将区位码向后偏移了32，以避免与ASCII字符中0~32的不可显示字符和空格字符相冲突。

2.

注意，国标码中是分别将区位码中的“区”和“位”各自加上32(20H)的，因为GB2312是DBCS双字节字符集，因此国标码属于双字节码。

这样我们可以算出“万”字的国标码十进制为：(45+32，82+32) = (77，114)，十六进制为：(4D，72)，二进制为：(0100 1101，0111 0010)。

（笨笨阿林原创文章，转载请注明出处）

 

三、内码(机内码)

1.

不过国标码还不能直接在计算机上使用，因为这样还是会和早已通用的ASCII码冲突，从而导致乱码。

比如，“万”字国标码中的高位字节77与ASCII的“M”冲突，低位字节114与ASCII的“r”冲突。因此，为避免与ASCII码冲突，规定国标码中的每个字节的最高位都从0换成1，即相当于每个字节都再加上128(十六进制为80，即80H；二进制为1000 0000)，从而得到国标码的“机内码”表示，简称“内码”。

2.

由于ASCII码只用了一个字节中的低7位，所以，这个首位(最高位)上的“1”就可以作为识别汉字编码的标志，计算机在处理到首位是“1”的编码时就把它理解为汉字，在处理到首位是“0”的编码时就把它理解为ASCII字符。

比如：

　　77 + 128 = 205(二进制为1100 1101，十六进制为CD)

　　114+ 128 = 242(二进制为1111 0010，十六进制为F2)

3.

我们可以来检验一下。打开记事本输入“万”字，编码选择为ANSI(Windows记事本中的ANSI编码在简体中文版操作系统中默认为GB类编码，详见后文解释)，保存，如下图所示。

然后用二进制编辑器(比如UltraEdit)打开刚才保存的文件，切换到十六进制模式，会看到：CD F2，这就是“万”字的内码，如下图所示。

4.

小结一下：

从区位码(国家标准定义) ---> 区码和位码分别+32(即+20H)得到国标码 ---> 再分别+128(即+80H)得到机内码(与ACSII码不再冲突)。

因此，区位码的区和位分别+160(即+A0H，32+128=160)可直接得到内码。用十六进制表示就是：

　　　区位码(区码, 位码) + (20H, 20H) + (80H, 80H)
　　= 区位码(区码, 位码) + (A0H, A0H)
　　= 内码(高字节, 低字节)。

（注：十六进制数既可通过添加后缀H来表示，也可通过添加前缀0x来表示）

 

四、为什么要加上20H和80H？

1.

区位码、国标码、内码的转换非常简单，但令人迷惑的是为什么要这么转换？

首先，需要注意到一点，GB2312虽说是汉字编码方案，但其实里面也有针对26个英文字母和一些特殊符号的编码，按理说这些和ASCII重合的字符(33~127)应该无需再重新编码，直接沿用ASCII编码不就行了？

2.

原来，当时在制定GB2312时，决定对ASCII中的可打印字符，也就是英文字母、数字和符号部分(33~126，127为不可打印的DEL)重新编入GB2312中，以两个字节表示，称之为全角字符(全角字符在屏幕上的显示宽度为ASCII字符的两倍，后来也因此而将对应的ASCII字符称之为半角字符)。

而对于ASCII中前32个不可显示也不可打印的控制字符(ASCII码为0~31)，以及第33个可显示但不可打印的空格字符(ASCII码为32)等一共33个不可打印字符的编码则直接沿用，不再重新编码。

3.

因为要保留这33个不可打印字符，就不能直接采用区位码作为计算机直接处理的机内码，需要将区位码向后偏移32以避开冲突(为什么是偏移32，而不是偏移33？因为区位码中的区码和位码都是从1开始计数的，不像ASCII码是从0开始计数的)。

十进制数字32的十六进制表示就是20H，这也就是区位码的区码和位码都分别要加上20H才能得到国标码的原因。

（笨笨阿林原创文章，转载请注明出处）

4.

不过，如果直接采用国标码作为计算机直接处理的机内码的话，还是会与ＡSCII编码产生冲突，导致乱码。

因为国标码虽然相较于区位码避开了ASCII码中0~32的前33个不可打印字符，但并没有避开ASCII码中的英文字母、数字和符号等可打印字符(33~126，共94个字符)以及不可打印的DEL(127)。也就是说，国标码并不是完全兼容ASCII码的。

5.

为了彻底避免与ASCII码的冲突，考虑到ASCII码只使用了一个字节中的低7位，其最高位(即首位)总是为0，于是决定将国标码中每个字节的最高位设为1(国标码的两个字节中的最高位都总是为0，即国标码中的每个字节与ASCII码一样实际上也只用了一个字节中的低7位)，这就是GB2312的机内码(即内码)，简称GB2312码。

这样一来就彻底区分开了ASCII码和GB2312码。这也是为什么国标码还要加上(80H，80H)才能得到机内码的原因。

6.

看到这里，有人或许又要问了：如果仅仅是为了避免与ASCII码相冲突，为什么最初不直接将区位码的区码和位码的最高位从0改为1(相当于各自直接加上128)，这样不就无需经过国标码多此一举的中间转换了吗？而且还无需后移32，也就不用浪费这部分编码空间。

对此本人也很困惑，在网上搜了很久也没找到答案，因此具体原因不得而知。或许是一开始考虑不周？或许是为了未来扩展所需而预留一部分空间？又或许是有其他不得已的原因？有知道的朋友还望能指点迷津。

GB2312区位码、国标码、内码对照表(其中汉字内码B0A1~F7FE，共6763个)

 

五、外码(输入码、输入法编码)

1.

外码也叫输入码、输入法编码，是用来将汉字输入到计算机中的一组键盘符号，是作为汉字输入用的编码。

英文字母只有26个，可以把所有的字符都放到键盘上，而使用这种办法把所有的汉字都放到键盘上是不可能的。所以汉字系统需要有自己的输入码体系，使汉字与键盘能建立起对应关系。

2.

目前常用的汉字外码分为以下几类：

1）数字编码，比如区位码；

2）拼音编码，比如全拼、双拼、自然码等；

3）字形编码，比如五笔、表形码、郑码等。

3.

汉字外码往往会出现重码。

所谓重码，指的是同一个汉字外码对应于多个汉字，反过来说，也就是可能有多个汉字的外码是相同的，相当于重复了，所以称之为“重码”。比如使用拼音作为外码时(即使用拼音输入法输入汉字时)，重码现象是相当普遍的。

当出现重码时，往往需要附加选择编号以具体确定所要输入的汉字，这种情况下，可认为外码实际上相当于隐式地包括了选择编号在内。

 

六、字形码(字型码、字模码、输出码)

1.

字形码，又称为字型码、字模码、输出码，属于点阵代码的一种。

为了将汉字在显示器或打印机上输出，把汉字按图形符号设计成点阵图，就得到了相应的点阵代码(字形码)。

也就是用0、1表示汉字的字形，将汉字放入n行*n列的正方形(即点阵)内，该正方形共有n^2个小方格，每个小方格用一位二进制数表示，凡是笔划经过的方格其值为1，未经过的方格其值为0。

2.

显示一个汉字一般采用16×16点阵或24×24点阵或48×48点阵。已知汉字点阵的大小，可以计算出存储一个汉字所需占用的字节空间。

比如，用16×16点阵表示一个汉字，就是将每个汉字用16行，每行16个点表示，一个点需要1位二进制数，16个点需用16位二进制数(即2个字节)，所以需要16行×2字节/行=32字节，即以16×16点阵来表示一个汉字，字形码需要32字节。

因此，字节数=点阵行数×(点阵列数/8)。

3.

显然，字形码所表示的字符，相对于抽象字符表ACR里的“抽象”字符，可称之为“具体”字符，因为已经具有了“具体”的外形。

4.

为了将汉字的字形显示输出或打印输出，汉字信息处理系统还需要配有汉字字形库，也称字模库，简称字库，它集中存储了汉字的字形信息。

字库按输出方式可分为显示字库和打印字库。用于显示输出的字库叫显示字库，工作时需调入内存。用于打印输出的字库叫打印字库，工作时无需调入内存。

字库按存储方式也可分为软字库和硬字库。软字库以字体文件(即字形文件)的形式存放在硬盘上，现多用这种方式。硬字库则将字库固化在一个单独的存储芯片中，再和其它必要的器件组成接口卡，插接在计算机上，通常称为汉卡。这种方式现已淘汰。

 

七、总结

1.

可以这样理解，为在计算机内表示汉字而采取统一的编码方式所形成的汉字编码叫内码。为方便汉字输入而形成的汉字编码为外码，也叫输入码。为显示输出和打印输出汉字而形成的汉字编码为字形码，也称为字模码、输出码。

通过键盘输入汉字外码，然后输入法将汉字外码转换为当前操作系统所默认采用的字符编码方案的字符编号(即码点值)，再根据字符编号通过代码页查表的方式转换为汉字内码(代码页详见前文的介绍)，以实现输入汉字的目的；然后根据所选择的字体，通过汉字内码在字模库(即字库)中找出与字体相对应的字形码，从而将汉字内码转换为汉字字形码，以实现显示输出和打印输出汉字的目的。

事实上，英文字符的输入、处理和显示过程大致上也差不多，只不过英文字符不需要输入码(即外码)，直接在键盘上输入对应的英文字母即可。

2.

注意，ASCII码，以及EASCII、ISO 8859系列、GB系列、Big5和Shift JIS等既兼容ASCII码又互相之间不兼容的ANSI编码(“ANSI编码”是对世界上各个国家和地区所制定的既兼容ASCII码又互相之间不兼容的各种字符编码的统称，下一篇文章将详细介绍这个统称的来龙去脉)，都属于传统字符编码模型，而不属于现代字符编码模型，很难直接简单套用现代字符编码模型中的概念来表述。

如果一定要套用的话，就GB系列编码而言，勉强来说，区位码相当于现代字符编码模型中编号字符集CCS的字符编号，国标码相当于字符编码方式CEF的码元序列，而机内码则相当于字符编码模式CES的字节序列。

不过，由于GB系列编码虽然是多字节编码，但码元却是单字节码元(码元的概念后文有详细介绍)，因此不存在字节序问题，也就不存在字符编码模式CES中的大端序、小端序的概念(字节序以及大端序、小端序的概念后文有详细介绍)。

（笨笨阿林原创文章，转载请注明出处）

 

 

【预告：下一篇将重点剖析非常容易令人困惑的所谓ANSI编码与代码页(Code Page)，敬请关注！】

 

 

0x80~0x9f 在ISO 8859中是C1控制字符，兼容原因

 

 

 

 

 

 

 

1 格雷码：

1.1 格雷码引言：

在数字系统中，常要求代码按一定顺序变化。

在机器视觉里面，编码结构光也是按照一定的顺序进行变化，最常用的就是Binary,但是，二进制的纯粹的编码，由于二进制的进制关系(每个位是有权的），如果发生一个错码（在机器视觉里面，错码的发生可能是一个背景的干扰，也可能是测试物体的一个比较陡峭的轮廓变更），一个错码往往他的数字权重不是一位，比如二进制的最高为，错了一位，那么就是整个数值发生一半的变化。

去掉权重的好处就是，如果模拟量或者是采样的数据发生了一个微小的变化，在整个测量的范围内，这个微小的变化都只能变更一个格雷码数位，而不论这个测量的数值位于整个测量量程的哪个位置：

【案】在上面这个例子中，假设测量的量程为16，我们测量到7和8之间的模拟量，你看看二进制，红色表示要变更所有的数位来表示，而格雷码只要变更一位。

那么，在我们表示这个数据的时候，二进制码所有的位都必须不能出错，否则数据会大变化。而格雷码就不会出现这个问题。 

后来，弗兰克·格雷（Frank Gray，18870913-19690523）专利“Pulse Code Communication” 发明了一种新的顺序编码的方式，这个方式也是每个数值是唯一的二进制标识，但是，每个相邻的位只有一个位值的变化，这样就极大的减少了测量可能发生误差。

1.2 格雷码的定义：

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。

格雷码是一种具有反射特性和循环特性的单步自补码，其循环和单步特性消除了随机取数时出现重大错误的可能，其反射和自补特性使得对其进行求反操作也非常方便，所以，格雷码属于一种可靠性编码，是一种错误最小化的编码方式，因此格雷码在通信和测量技术中得到广泛应用。

Gray Code(格雷码) C++多方法实现_越前浩波的博客-CSDN博客

3位格雷码的顺序编码_几种简单的编码（为什么使用ASCII码）_乔拉爵士的博客-CSDN博客

1.3 认识格雷码

下为3位元的Gray Code：Gray Code是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数好了，任两个数之间只有一个位元值不同

000 001 011 010 110 111 101 100

1.3.1 位元

位元就是数列的基础数是由几个二进位数来表示，就是几个位元。

上面的例子里面：000 是3个二进制数，那么就是3个位元，那么2^3 = 8,总共8个位值

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

上面，0000 等是4个 二进制数，那么就是4个位元，那么4^3 = 16,总共16个位值

1.3.2 （格雷）码值

001 就是一个码值

---

2 格雷码的生成：

2.1 方法1：按照定义排列生成格雷码

回到前面的3位元的格雷码：

000 001 011 010 110 111 101 100

如果推广到N个位元，那么码值的数量应该是2^N个

2.1.1 产生的基本规律原则和标准做法

其实就是3个步骤，

第一步，改变最右边的位元值；

第二步，改变右起第一个为1的位元的左边位元；

第三步，第四步重复第一步和第二步，直到所有的格雷码产生完毕（换句话说，已经走了(2^n) - 1 步）。

举例3位元的产生步骤：

　　假设产生3位元的格雷码，原始值位 000
　　第一步：改变最右边的位元值： 001
　　第二步：改变右起第一个为1的位元的左边位元： 011

重复1：
　　第三步：改变最右边的位元值： 010
　　第四步：改变右起第一个为1的位元的左边位元： 110

重复2：
　　第五步：改变最右边的位元值： 111
　　第六步：改变右起第一个为1的位元的左边位元： 101

重复3：
　　第七步：改变最右边的位元值： 100 #已经走了(2^n) - 1  = 7步，完成所有码字的产生。

 2.1.2 实现算法如下：

#include <stdio.h> 
#include <stdlib.h>
#define MAXBIT 20
#define TRUE 1
#define CHANGE_BIT(x) x = ((x) == '0' ? '1' : '0')
#define NEXT(x) x = (1 - (x))

    int main(void) {
        char digit[MAXBIT]; int i, bits, odd;

        printf("输入位元数："); scanf("%d", &bits);

        for(i = 0; i < bits; i++) { digit[i] = '0';
            printf("0");
        }
        printf("\n"); odd = TRUE; while(1) {
            if(odd)
                CHANGE_BIT(digit[0]);
            else {
                // 计算第一个1的位置
                for(i = 0; i < bits && digit[i] == '0'; i++) ; if(i == bits - 1) // 最后一个Gray Code
                    break; CHANGE_BIT(digit[i+1]);
            }
            for(i = bits - 1; i >= 0; i--)
                printf("%c", digit[i]);

            printf("\n"); NEXT(odd);
        }

        return 0;
    }

方法2：

///产生n位格雷码(直接排列方法构建)
void generateGraycode2(int n)
{
	int i;
	char code[20];
 
	for (i = 0; i < n; i++)
		code[i] = '0';
	code[n] = '\0';
	printf("%s\n", code);
 
	while (1)
	{
		if (code[n - 1] == '0')
			code[n - 1] = '1';
		else
			code[n - 1] = '0';
		printf("%s\n", code);
 
		i = n - 1;
		while (code[i] == '0') i--;
		if (i == 0)
			break;
 
		if (code[i - 1] == '0')
			code[i - 1] = '1';
		else
			code[i - 1] = '0';
 
		printf("%s\n", code);
	}
}
 

方法3：

vector<int> grayCode(int n) {
        int count = 1 << n;
        vector<int> res(count,0);
        for(int i = 1 ; i < count; i ++)
        {
            int cur = res[i - 1];
            if(i % 2 == 1)
                cur  = cur ^ 1;
            else
            {
                int k = 0;
                while(((cur >> k) & 1) == 0) 
                    k ++;
                cur = cur ^ (1 << (k + 1));
            }
            res[i] = cur;
        }
        return res;
    }

  C++经典算法题-格雷码（Gray Code）_逍遥云恋-CSDN博客_c++格雷码

---

2.2 方法2：通过二进制和格雷码的转码规律生成：

格雷码（从零基础讲解，C++版）_不负AC不负卿的博客-CSDN博客

 Gray Code(格雷码) C++多方法实现_越前浩波的博客-CSDN博客

观察上表，我们可以得出格雷码和二进制码之间的基本换算逻辑如下：

 

 2.2.1 二进制转码为格雷码（编码）

原理：如果二进制码字的第 i 位和 i+1 位（从右边开始数）相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）

/*编码模板 */
#include <iostream>
using namespace std;

int gray_encode(int num)
{
	return num ^ (num >> 1);		// >>是位移运算符，^是异或运算符
}

方法2：

class Solution {
public:
    vector<int> grayCode(int n) {
        int num = 1 << n;
        vector<int> ret;
        ret.reserve(num);
        
        for(int i = 0; i < num; i++)
        {
            ret.push_back(i ^ (i >> 1));
        }
        
        return ret;
    }
};

 

 2.2.1 格雷码转成二进制（解码）

 

 原理：从左边第二位起，将每位与左边一位解码后的值进行异或，作为该位解码后的值（最左边一位依然不变），直到最低位。

 这里因为转成二进制的权重的位，所以要取对数log，并以2为底，用数值去除log2

/*解码模板 */
#include<math.h>		// log对数函数需要用到的头文件
#include <iostream>
using namespace std;

int gray_decode(int num)
{
	int head;
	if(!num) return 0;
	head = 1 << int(log(num) / log(2));	//C++没有直接以2为底的对数，我们创造一个以2为底的对数
   return head + gray_decode((num^head) ^ (head>>1));

---

2.3 镜像排列生成格雷码（对称法）

格雷码编解码学习(一)：格雷码编码原理与C++代码实现_Color Space的博客-CSDN博客

上面这个列表，分别给出位元为1,2,3的三组格雷码，其中灰色的部分是镜像分割线，黑色的格雷码码字和蓝色的格雷码码字是针对镜像分割线对称的。

算法原理：

C++ 递归产生格雷码_永远在路上啊的博客-CSDN博客

当只有一位的时候，格雷码要么是0,要么是1.
        如果有两位的时候，格雷码是首先由  0
                                    1
        然后镜像对称得到后两位:            1
                                    0
        然后再在上面两行前面加上0，下面两行加1得到:
                                    00
                                    01
                                    11
                                    10
        这就是二位的格雷码产生的过程。所以可以使用递归的方法去产生格雷码：
                        {    0,1                                n==1
                f(n)  = {   f(n-1)                            n >=2
                        {    对称翻转，然后上一半加0，后一半加1

2.3.1 实现算法1，C++,二维数组

template<typename T,unsigned int N> void recursive::grayCodeGeneration(T (*list)[N],std::size_t size)const{
    if(size==1){//最后需要翻转输出
        list[0][size-1]=0;
        list[1][size-1]=1;
    }
    else{
        grayCodeGeneration(list,size-1);
        //下面做的是对称翻转
        for(int i= std::pow(2,size-1),j=std::pow(2,size)-1;i < std::pow(2,size);++i)
            for(int k = 0;k<N;k++)
                list[i][k] = list[j-i][k];//对应的逆序的行进行保存，这个时候用到的是
                                        //需要逆序保存的两个行之和是pow(2,size)-1;
        //这一步做的是前一部分加0，后一步分加1
        for(int i = 0;i < std::pow(2,size);i++){
            if(i <= (std::pow(2,size)/2-1))
                list[i][size-1]=0;
            else
                list[i][size-1]=1;
        }
    }
}

pow 就是求某数的指数的函数 

2.3.2 实现算法2，C++,

 C++ 生成代码如下：

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
///产生n位格雷码(镜像排列方法构建)
vector<string> generateGraycode(int n)
{
	vector<string> nGraycode;
	if (n == 1)
	{
		nGraycode.push_back("0");
		nGraycode.push_back("1");
	}
	else
	{
		vector<string> mid_ans = generateGraycode(n - 1);
		for (vector<string>::iterator iter = mid_ans.begin(); iter != mid_ans.end(); ++iter)
		{
			string temp = *iter;
			temp.insert(0, "0");
			nGraycode.push_back(temp);
		}
		for (int i = mid_ans.size() - 1; i >= 0; --i)
		{
			string temp = mid_ans[i];
			temp.insert(0, "1");
			nGraycode.push_back(temp);
		}
	}
	return nGraycode;
}
 
int main()
{
	vector<string>nGraycode;
	nGraycode = generateGraycode(3);
	for(int i = 0; i < nGraycode.size(); i++)
		cout << nGraycode.at(i) << endl;
	return 0;
}

 C++ 另一种表述为：

#include <iostream>
#include<vector>
using namespace std;

vector<string> getGray(int n) {
        // write code here
    vector<string> result;
    if(n == 1){
      result.push_back("0");
      result.push_back("1");
       return result;
    }else{
        result = getGray(n-1);
        int currentsize = (int)result.size();
        for(int i = 0; i < currentsize; i++){
            result.push_back(result.at(i));
        }
        for(int i = 0; i < currentsize; i++){
                 result.at(i) = "0" + result.at(i);
        }
        for(int i = currentsize; i < (int)result.size(); i++){
            result.at(i) = "1" + result.at(i);
        }
         return result;
        }
    }
int main(){
    vector<string> v;
    v = getGray(2);
    for(int i = 0; i < v.size(); i++){
        cout << v.at(i) << " ";
    }
    cout << endl;
    return 0;
}

实现算法另一种表述、

[C++]LeetCode: 86 Gray Code （格雷码）_cindy_niu的专栏-CSDN博客

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret{0};
        
        for(int i = 0; i < n; i++)
        {
            int curCnt = ret.size();
            //把当前数字按照逆序顺序添加到ret中
            while(curCnt)
            {
                curCnt--;
                int curNum = ret[curCnt];
                curNum += (1 << i);
                ret.push_back(curNum);
            }
        }
        
        return ret;
    }
};

 

2.3.3 实现算法3，C，二维数组

c 语言表述：

算法实验-格雷码_中位数问题 分治法-CSDN博客_格雷码分治

//用分治策略设计一个算法对任意的n构造相应的Gray码。
#include<iostream>
#include<fstream>
using namespace std;
//构造n位格雷码，格雷码数m个
//利用格雷码除第一位外对称的原理
char** countgary(int n)
{
	int  m = 1;
	for (int a = 0; a < n; a++)
		m = m * 2;
	char** garycode = new char *[m];
	for (int a = 0; a < m; a++)
		garycode[a] = new char[n];
	if (n == 1)
	{
		garycode[0][0] ='0';
		garycode[1][0] ='1';
		return garycode;
	}//1的格雷码为0和1
	char** temp = countgary(n - 1);
	for (int a = 0; a < m / 2; a++)
	{
		garycode[a][0] = '0';
		garycode[a + m / 2][0] = '1';
		//m个格雷码前一半的第一位为0，后一半第一位为1
		for (int b = 1; b < n; b++)
		{
			garycode[a][b] = temp[a][b - 1];
			garycode[m-a-1][b] = temp[a][b - 1];
			//将n-1的格雷码呈上下对称放在n格雷码的前半段和后半段
		}
	}
	return garycode;
}
int main()
{
	ifstream f1("C:\\Data\\3.txt");
	ofstream f2("C:\\Data\\4.txt");
	int n; int m = 1;
	f1 >> n;
	for (int a = 0; a < n; a++)
		m = m * 2;
	char **garycode = countgary(n);
	for (int a = 0; a < m; a++)
	{
		for (int b = 0; b < n; b++)
		{
			f2 << garycode[a][b] << "\t";
			cout << garycode[a][b] << "\t";
		}
		cout << "\n";
		f2 << "\n";
	}
	f1.close();
	f2.close();
	return 0;
}

---

格雷码的算法实现_(っ°Д°)っ　　＃-CSDN博客_格雷码算法

2.4 正序逆序生成格雷码（对称法）

在正序的基础上将1左移n-1位，再加在逆序上，即得green code 格雷码。

算法返回的是10进制的值

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        int c=1;
        res.push_back(0);
        for(int i=0;i<n;i++){
            for(int j=res.size()-1;j>=0;j--)
                res.push_back(res[j]+c);
            c<<=1;
        }
        return res;
    }
    
};

C++经典算法题-格雷码（Gray Code）_逍遥云恋-CSDN博客_c++格雷码

(1条消息) [C++]LeetCode: 86 Gray Code （格雷码）_cindy_niu的专栏-CSDN博客

---

本文重要参考：

C++经典算法题-格雷码（Gray Code）_逍遥云恋-CSDN博客_c++格雷码