因为19级某位大佬提出了补码的存在意义这个问题，回想了一下在初次接触补码时自己对这个问题的思考只停留在了去除了重复的0以及方便了相反数相加得到0这一点上，却没有进一步思考为什么会有这样的需求，遂谷歌后从 stackoverflow上的相关问题处得到了较为完备的答案：为了降低加法器电路的复杂度，具体来说就是免除了重复的0的判断以及使用加法电路来同时实现加减法。

然而，这也不禁让我开始好奇起当初补码的设计者们是怎样从这样的需求出发，并最终出这么一套精妙的编码系统的。

我一直坚信，要想把一套知识体系真正消化透彻，其中最为重要而往往也是最为困难的一步就是要去理解这套体系的设计者是如何把它设计出来的。换句话说，就是要尝试去理解这个体系的设计者的设计思路。(在这里偷偷安利一下Computer Networking: A Top-Down Approach这本教材，我特别喜欢这本书在讲解TCP协议时根据需求的升级一步步改进设计方案的讲解思路，能更好地帮助学习者理解协议中引入的每个变量的意义)虽说在面对一些复杂而又精妙的体系时，往往凭着我这榆木脑袋是怎么也想不出个所以然来，但我还是希望尽力地去理解这背后奥妙。

废话不多说，现在就试着来理解补码的设计者的设计思路吧。简洁起见，下面只讨论用补码表示整数以及机器数的位数 n=8 的情况。

正如在第一段所说，在设计补码之前，我们面对的是消去重复的0以及用同一套简单电路同时实现加减法这两个需求。但其实第一个需求还可以延申一下，变成没有两个不同的码点用于表示同一个值。

所谓编码，其实就是给每一个机器中表示的码点人为地赋上一个意义而已，因此，我们现在的任务就可以用如下的数学语言来描述：

设 C=\{ 0, 1, 2, ..., 2^n-2, 2^n-1 \}，即n位机器数的所有码点所构成的集合。设 V 为整数集 \mathbb{Z} 的一个基数为 2^n 的同时包含了 0、正数、负数的子集，它是我们编码后码点集所能表示的所有整数。

现要求一个定义在 C 上具有封闭性、结合律、交换律的运算 \oplus，以及一个从C 到 V 之间的双射 f，使得对于任意满足 a, b \in V 且 a+b \in V 的数对 a,b 都有 f^{-1}(a) \oplus f^{-1}(b) = f^{-1}(a+b)。

现在对上面的数学语言描述做出一定解释：

首先，之所以要求 V 同时包含 0和正负数是出于实用起见，毕竟表示自然数的话原码就已经够用了，要设计新的编码方案就是为了解决负数的表示问题。
其次，之所以要求 V 的基数为 2^n，为的就是满足 f 为双射的基本条件，而要求双射则是因为我们既不想浪费任何一个码点又不想有两个码点同时表示同一个值。(这样就解决的了第一个需求)
然后，运算 \oplus 实际上代表的就是那个用于同时实现加减法的电路的所做的运算。之所以要求它具有封闭性是因为机器数只有有限的数位，只能表示有限的值；之所以要求它具有结合律和交换律是为了能用它来模拟整数加法，故需要满足整数加法所具有的性质。(模拟整数加法而不是整数减法是因为在数学分析中由自然数集扩展到整数集时就是用的“加上相反数”来定义减法的)
最后，之所以要求映射f 拥有那个“类似同构”的性质(简介起见，下文都将这样称呼这个性质)，则是为了通过这样来确定 C 上的运算\oplus 确实可以模拟整数集上的加法，而因为整数加法正如上一点中的括号部分所述，已经通过引入相反数或者说加法逆元这个概念同时实现了加法和减法的功能，故 \oplus 就可以说也同时实现了加减法。举例来说的话,比如在真正的现有补码系统中2的编码为0000 0010，-1的编码为1111 1111，1的编码为0000 0001的，而 \oplus 被定义为了模 2^n 加法，那么 f^{-1}(2) + f^{-1}(-1) = (0000 0010 + 1111 1111) \mod 2^n = 0000 0001 = f^{-1}(2+(-1)) = f^{-1}(1)，即两个整数的编码经过运算\oplus 处理后得到的新的编码应该等于这两个整数的和对应的编码。~~这一点因为 \sout{V} 上的加法不封闭构不成一个代数，故不是真正的同构，总感觉还不太能令人信服的样子....~~

因此，现在我们需要做的，就是明确好运算\oplus 和映射f 到底是什么了，只要它们满足以上描述的要求，这样就定义好了一套符合我们需求的编码系统。

考虑到运算\oplus 需要满足的那一堆属性恰好都被我们非常熟悉也非常适合只有n位的机器数的模2^n加法所满足，因此我们可以尝试以它作为运算\oplus 并试着找出一个满足剩下的要求的映射f 来。(这里算是数学直觉加上进一步测试？)

考虑到实际需求，我们希望所表示的正数的范围是从1开始递增的某段连续范围，同理，所希望表示的负数范围也是从-1开始递减的某段连续范围。从这里可以看出0和1都将会被收入 V 中，而其余的正数的编码其实都可以由1的编码再加上“类似同构”的性质一一得出，如 f^{-1}(2)=f^{-1}(1) \oplus f^{-1}(1), f^{-1}(3)=f^{-1}(2) \oplus f^{-1}(1), ...而-1的编码也可以由f^{-1}(0)=f^{-1}(-1) \oplus f^{-1}(1)得出，再然后其余的负数的编码也可以由-1的编码按类似的方法得出。于是，可以说，我们只需要指定0和1的编码各是多少就可以了。~~实际上用于构建自然数集的Peano公理中最初也只定义了0和后缀这两个概念，然后再通过数学归纳原理把剩下的数逐个纳入到自然数集中。~~

一个很常见也很直观的想法就是把0的编码设为0000 0000，把1的编码设为0000 0001(又是一个直觉)，然后-1的编码根据“类似同构”性质可得出是1111 1111，然后我们就可以按上一段所述的方法一样不断把其余的数的编码推断出来。

经过观察可得知正数的编码是从0000 0001开始随着所表示的值递增而递增，而负数的编码是从1111 1111开始随着所表示的值的递减而递减，现在的问题在于如何给这两个会相遇的数列划分一个边界。为了对齐起见，我们让它们在0111 1111和1000 0000之间划分开来，使得非负数和负数的数量一样多，同时也方便我们通过最高位的0/1来判断是不是负数。故最后我们会得出这样的一个映射：

f^{-1}(x) = \begin{cases} x & 0 \le x \le 2^{n-1}-1 \\ 2^n+x & -2^{n-1} \le x < 0 \end{cases}

即f^{-1}(x)=(2^n+x) \mod 2^n, (-2^{n-1} \le x \le 2^{n-1}-1)

最后，我们只需要验证这个映射是否满足“类似同构”性质即可：

对于 \forall a,b \in V 且a+b \in V，有：

\begin{aligned} f^{-1}(a) \oplus f^{-1}(b) & = (((2^n+a) \mod 2^n) + ((2^n+b) \mod 2^n)) \mod 2^n \\ & = (2*2^n + (a + b)) \mod 2^n \\ & = (a + b) \mod 2^n \\ & = (2^n + (a + b)) \mod 2^n \\ & = f^{-1}(a+b) \end{aligned}

由此，我们就得出了这样一套满足了我们的需求的编码方案。

如果仅仅考虑加减法的话，按照上面的思考框架，得出另一套和现有的补码不一样但也满足需求的编码方案似乎也是可行的。~~虽说我也没试过也没证明过就是了。~~

按照维基百科的描述：

Compared to other systems for representing signed numbers (e.g., ones' complement), two's complement has the advantage that the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers (as long as the inputs are represented in the same number of bits as the output, and any overflow beyond those bits is discarded from the result).

似乎补码的设计者们在设计时还额外考虑到了乘法的问题？如果引入乘法之后是不是上面描述的思考框架里的很多靠直觉和测试的部分就能够被确定下来了呢？还是说这套框架会被推翻呢？这个就等以后有空再思考吧。(逃

Invent UTF-8 From Scratch | 从头发明 UTF-8

补码设计思路的探索

关于 32-bit fixed-point number 的编码规则

iconv无法转换ascii表示的utf-8编码

发现个好玩的——社会主义核心价值观编码器