序言
计算机使用二进制而非十进制表示数值或可以称其为信息。但是二进制只是由01比特序列构成的，这样自然就引出了一个问题：如何规范二进制的编码表示呢？在计算机科学中，有原码，反码与补码三个基本概念（移码单独列出）。
这篇笔记是基于《计算机组成原理》（高等教育出版社，唐朔飞，第二版）的第六章学习经历的启发，加上先前的一些认识所整合的一篇 助记性笔记（没错我现在记性挺差），当然也可以作为初学者的参考文。但由于本人才学疏浅，如有疏漏错误请谅解。
原码
从循环取模求除数说起
二进制是由0和1组成的，这一点可以从我们十进制的组成里看出。如果把十进制看作由单个数字作为元素生成的字符串的话，数字集合$S={0,1,2,3,4,5,6,7,8,9}$ 。可以注意到这里的$S$ 还可以写作${i \vert i \in k \space mod\space 10 ,\forall k \in N }$ 。所以类似的，二进制的元素集合$Bin$=${i\vert i \in k \space mod \space 2, \forall k \in N }$ =${0,1}$。
接下来实现一个十进制数到二进制的转换：
给定一个十进制整数（注意：这里为unsigned integer)，如11。算法就是将这个数字不断的除2并保留余数，将保留的余数按顺序插入到一个队列中，如最先求出的余数放到队列最右端，接下的余数都依次插入到队列左端直到这个数字变为0结束，最后生成的队列从左往右读其实就是这个十进制整数的二进制原码。
11的变化：$11 \rightarrow 5 \rightarrow 2 \rightarrow 1 \rightarrow 0$
余数队列(-为空): —- $ \rightarrow$ —1 $ \rightarrow$ –11 $ \rightarrow$ -011 $ \rightarrow$ 1011
于是从左至右就是1011，即十进制的11。
数学解释：
对于一个$n$进制的$k$位的数$Num$，可以表示为：$Num=\sum_{i=1}^k num_i*n^{i-1}$，其中$num_i$是第$i$位的值，在1到$k-1$之间
所以刚刚的$1011=1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8+2+1 = 11$
如果这个时候出现了负数该如何表示？
引入符号位，1表示负数，0表示正数。
| 十进制绝对值（取2位数值位） | 正数原码 | 负数原码 |
|---|---|---|
| 0 | 000 | 100 |
| 1 | 001 | 101 |
| 2 | 010 | 110 |
| 3 | 011 | 111 |
反码(1’s Complement)
定义
正数的反码与其原码相同；负数的反码是对其原码逐位取反，不包含符号位。
因此，在原码的基础上，反码可以很容易求出。
| Binary | 反码对应的十进制 | 原码(带符号位表示) |
|---|---|---|
| 000 | 0 | 0 |
| 001 | 1 | 1 |
| 010 | 2 | 2 |
| 011 | 3 | 3 |
| 100 | -3 | -0 |
| 101 | -2 | -1 |
| 110 | -1 | -2 |
| 111 | -0 | -3 |
补码
如何生成补码
首先，如果给了一个数的有符号整数原码表示，那么其补码就是对于负数保持符号位不变，然后将数值部分取反再加1，非负数不变。
| Binary | 反码对应的十进制 | 原码(带符号位表示) | 补码表示 | 原码 |
|---|---|---|---|---|
| 000 | 0 | 0 | 0 | 0 |
| 001 | 1 | 1 | 1 | 1 |
| 010 | 2 | 2 | 2 | 2 |
| 011 | 3 | 3 | 3 | 3 |
| 100 | -3 | -0 | -4 | 4 |
| 101 | -2 | -1 | -3 | 5 |
| 110 | -1 | -2 | -2 | 6 |
| 111 | -0 | -3 | -1 | 7 |
补码机制的类比
假如给你一个钟表，只有1到12的整数表示，现在是10点钟，如何得出5小时后的时间呢，很简单：10+5=15，15 mod 12 =3,所以是三点钟（上午还是下午，那无所谓）。那么如何算出十一个小时前的时间呢？由于10-11=-1，所以有些麻烦。我们换个角度考虑：10-11=10+（-11），由于时钟在前一个10+5的例子中已经显示出了同余性，我们便在这里凑一个同余，即$10+(-11) \equiv 10 +(-11) +12 \space mod \space (12)$，那么在时钟的例子中，-11的编码就可以写成1。在是一个例子，3-11在时钟里就是3+1=4点整，结论依旧成立！
回到二进制补码：对于一个二进制数，如上表所示，两个数值位，一个符号位，时钟的12在这里是什么呢？答案是$2^{3}=8$ 。同时，和时钟的例子不同的是，由于加上符号位，不会出现-11点钟映射到1点钟这种情况，补码到二进制的映射是唯一的。反过来也是，所以是双射1。
为什么要这么设计？即为什么是“取反加一”法则？
答案就是补码的范围（上表)是：$[-4,3]$ ,因此一共以后8个数，所以是对8取模，因此这个编码为了能方便运算，就要将原来的负数映射到 原码(不带符号的)那组的与其绝对值之和为8的数字上去。举个例子：在上面这种表格中，-2的补码的原码表示就是6，而6+2=8。
所以，计算机执行运算一定是对二进制直接运算，所以将负数对应的补码映射到这个负数加上2的字长次幂的原码上，就能直接进行模运算了,而得到的余数，如果未溢出，就会反过来被映射到正确的结果所对应的补码上面去。
例子：$2-3=2+（-3）=010+101=111=-1$
刚刚的例子刚好诠释了这样一组公式：
$[x]_补+[y]_补=[x+y]_补$
$[x]_补+[-y]_补=[x-y]_补$
同时给定一个十进制带符号数，如何生成其补码呢？
$[x]_补= \space (x \ge 0 )\space ? \space \space ‘0’+[x]_原 \space: \space \space ‘1 ‘+[\space\vert x \vert\space]_原$
如何快速求补码？
$eg.$ 给定一个带符号数原码100010，如何求其补码？
如果按定义:先看符号位是否为负数，如果是，然后再看数值位，取反加1即可，所以过程为：
100010 $\rightarrow$ 111101 $\rightarrow$111101+000001 $\rightarrow$ 111110
这样看，一共四步，分析符号，取反，加1，得到结果。
如果细心观察，你会发现，除去符号位，原码和反码的相同最大字串一定是：原码的最后一个1开始，包含1的往后的所有元素构成的串。即00010和11110就是倒数第二位开始一样，前面刚好相反。
为什么会这样？
仔细一想就能推断到：因为负数，所以第一步先求反，也就说明了前面那部分两个串确实相反。那后来为什么一样了呢？我们不妨假设原码的最后一个1出现在倒数第$i$处，那么原码的第倒数$i-1$开始到最后一定都是0（注意，也可以一个0都没有，因为最后一个1也是原码最后一位）。然后这串数就可以写作一个正则表达式（Regular Expression）：1(0)*,对其取反得到：0(1)*,再加1呢？得到：1(0)*,因为最后一位的0导致了前面的依次进位，一直到那个1为止。
和lowbit()的联系
我们都知道，在树状数组这个数据结构中，有个函数叫lowbit(); ，它的实现很简单：
int lowbit(int x)
{
return x&(-x);
}
观察之前给出的补码表，因为C/C++的数值类型是基于补码运算的，所以对于一个数x和-x来说，他们的反码加起来就是1(0)*,0的个数就是x的位数。如果其中一个数是$x_补$=s+1(0)* 那么根据补码定义$(-x)_补$=s_反+1(0)* ，此时将两个式子取与运算，得到$x_补 \& (-x)_补=$(0)*+1(0)* ，故最后的1(0)*得以提出，我们就得到了最后一位1的信息。
浮点数
小数的二进制表示
小数的定点数表示方式
IEEE 754
-
参见«深入理解计算机系统》（原书第三版）的第2章 2.2.2节 ，[美] Randal E. Bryant, David R. O’Hallaron 著。 ↩
