计算机算法中的数字表示法——原码、反码、补码

1.前言

昨天有粉丝让我讲解下定点数和浮点数，本来这部分是打算在FPGA入门系列的最后面来讲的。作者想开的系列真的很多，比如开发FPGA需要学会相关软件Matlab、Vivado、ModelSim等等的使用，每个软件做一个系列；FPGA入门教程做一个系列；基础数字信号处理做一个系列；通信相关的系列；IP核使用详解系列；FPGA数字积木系列（自己设计的一些参数化IP）。但是这些无疑都会花大量的时间去构思和整理资料，会出的比较慢，请读者耐心等待。

这篇文章就先介绍定点数和浮点数的概念，因为要真正讲清楚还得从原码、补码和反码开始讲起。要仔细研究的建议去多看看相关书籍，讲清楚原理之后再讲Matlab里面计算的浮点数怎么转换为定点数到FPGA里面进行使用，以及FPGA里面计算的定点数，怎么在Matlab里面又转换为浮点数。

这里需要重点强调的是，原理虽然很枯燥，但是真的很重要，是绝对不能忽视的，如果原理弄的一知半解，就开始去做处理，后期该踩得坑一个也少不了。

2.研究数字表示法的意义

在计算机算法中，有两个基本设计准则是非常重要的:分别是数字表示法和代数运算的实现。例如:定点数或浮点数就是常用且可行的数字表示法。一些基本的运算，像加法器和乘法器，更为繁琐的运算，诸如求平方根和应用CORDIC算法计算角函数的有效实现，都要以可行的数字表示法为基础实现。
FPGA由于其物理位级编程结构的特点，提供了大量实现数字信号处理算法所需要的计算机算法。这恰好与带有定点多级累加器内核的可编程数字信号处理器(programmable digital signal processors,PDSP)相反。在FPGA设计中仔细地选择位宽就能够从本质上做到节约。

3.数字表示法

在工程的早期阶段，必须仔细考虑，确定是使用定点数还是浮点数更适合于解决问题。一般可以认为:定点数的实现具有更高的速度和更低廉的成本；而浮点数则具有更高的动态范围且不需要换算，这对较为复杂的算法可能更适合。下图给出了传统和非传统定点数和浮点数的数字表示法的一个概观。两套系统都由许多各自的标准所覆盖，当然，如果需要的话也可以以一种专有形式实现。

3.1 无符号整数

设 $X$ 是 一个 $N$ 位无符号二进制数, 则其范围是 $\left[0,2^N-1\right]$, 表达式如下:
$$X=\sum _{n=0}^{N-1}{x}_n{2}^n$$

其中 $x_n$ 是 $X$ 的第 $n$ 位二进制数字(也就是 $x_n\in [0,1]$ )。数字 $x_0$ 称作最低有效位(Least Significant Bit, LSB), 具有相当于个位的权重。数字 $x_{N-1}$ 就是最高有效位(Most Significant Bit, MSB), 具有相当于 $2^{N-1}$ 的权重。

3.2 有符号数值

在有符号数字表示法中, 数字和符号是单独表示的。第一位代表符号, 余下的 $N-1$ 位代表数字, 表达式如下:
$$X=\{\begin{array}{ll}{\sum }_{n=0}^{N-1}{x}_n{2}^n& X\ge 0\\ -{\sum }_{n=0}^{N-1}{x}_n{2}^n& X<0\end{array}$$

表达式的范围是 $\left[-2^{N-1},2^{N-1}\right]$, 有符号数字表示法的优点就是简化了溢出的问题, 但缺点就是加法需要根据哪一个操作数更大来进行区分运算。

3.3 二进制补码(Two’s Complement, 2C)

有符号整数的 $N$ 位二进制补码表达式如下:
$$X=\{\begin{array}{ll}{\sum }_{\infty -0}^{N-1}{x}_n{2}^n& X\ge 0\\ 2^k-{\sum }_{n=0}^{1-1}{x}_n{2}^n& X<0\end{array}$$
其范围是$\left[-2^{N-1},2^{N-1}-1\right]$。目前数字信号处理领域，最常用的就是用二进制补码来表示有符号数。这是由于它可以累加多个有符号数，且最终结果也在N位范围内，即可以忽略一切算术上的溢出。

例如，我们计算两个3位数的差（3-2=?）：
$$\begin{array}{rrr}{3}_{10}& \leftrightarrow & 011_{2C}\\ -2_{10}& \leftrightarrow & 110_{2C}\\ 1_{10}& \leftrightarrow & 1.001_{2C}\end{array}$$

溢出可以忽略。所有的计算都是取模 $2^N$ 。这样就有可能出现不能够正确表示中间值的情形,但只要最终值有效, 结果就是正确的。例如计算 3 位的数字 $2+2-3$, 会得到一个中间值 $010+010=100_{2C}$, 也就是 $-4_{10}$, 但是结果 $100-011=100+101=001_{2C}$, 是正确的。

二进制补码还可以用来实现模 $2^N$ 的算法, 而且不需要在算法中作任何改动。

3.4 二进制反码(也称作 1 的补码, One’s Complement, 1C)

$N$ 位二进制反码数字表示法可以表示的整数范围是 $\left[-2^{N-1}-1,2^{N-1}-1\right]$ 。在二进制反码中,正整数和负整数除了符号位之外具有相同的表示方法。那么“0”就有正的和负的，两个表达式。二进制反码中有符号数的标准表达式如下:
$$X=\{\begin{array}{ll}{\sum }_{n=0}^{N-1}{x}_n{2}^n& X\ge 0\\ 2^N-1-{\sum }_{n=0}^{N-1}{x}_n{2}^n& X<0\end{array}$$

请看下面的简单示例:
$$\begin{array}{rrrrrr}{3}_{10}& \leftrightarrow & & 0& 1& 1_{1C}\\ -2_{10}& \leftrightarrow & & 1& 0& 1_{1C}\\ 1_{10}& \leftrightarrow & 1.& 0& 0& 0_{1C}\\ 进位& & \to & \to & \to & 1_{1C}\\ 1_{10}& \leftrightarrow & & 0& 0& 1_{1C}\end{array}$$
在二进制反码中需要， “进位问绕(carry wrap-around)” 加法。在最高有效位与最低有效位相加得到正确结果时, 就会出现进位。

尽管如此, 这种数字表示法还走能够有效地实现模 $2^N-1$ 运算, 而且不需要校正。因此二进制反码在实现特定的 DSP 算法(例如: 整数计算不 $2^N-1$ 的 Mersenne 变换)时, 还是有其特殊价值的。

3.5 减 1 表示法(Diminished one System, D1)

减1表示法是一种有偏移的数学表示法。正整数与二.进制补码相比减少了 1。 $N$ 位 D1数值范围是 $\left[-2^{N-1},2^{N-1}\right]($ 不含 0$)$ 。D1 数字表示法的编码规则定义如下:
$$X=\{\begin{array}{ll}{\sum }_{n=0}^{A-1}{x}_n{2}^n-1& X\ge 0\\ 2^N-{\sum }_{n=0}^{N-1}{x}_n{2}^n& X<0\\ 2^N& X=0\end{array}$$

从下面两个 D1 数相加可以看到, 对于 D1 而言还必须计算补码和颠倒进位的加法。
$$\begin{array}{rrrrrr}{3}_{10}& \leftrightarrow & & 0& 1& 0_{D1}\\ -2_{10}& \leftrightarrow & & 1& 1& 0_{D1}\\ 1_{10}& \leftrightarrow & 1.& 0& 0& 0_{D1}\\ 进位& & \to & \boxed{.\; -1}& \to & 0_{D1}\\ 1_{10}& \leftrightarrow & & 0& 0& 0_{D1}\end{array}$$
D1 数不需要在算法上作任何改动就能够有效地实现模 $2^N+1$ 运算。比如可以利用这一结论在 $2^N+1$ 计算环中实现费尔出 NTT(Fermat Network Transfer Table, Fermat 网络传输表)。

3.6 原码、反码、补码总结

上面说了这么多，又是公式又是例子的估计很多人都开始晕了，现在直接总结口诀如下：

对于有符号数而言：

1.二进制的最高位是符号位：0表示正数，1表示负数（口诀0——>0,1——>-）。

2.正数的原码、反码、补码都是一样的（三码合一）。

3.负数的反码 = 它的原码符号位不变，其他位取反（0——>1,1——>0）。

4.负数的补码 = 它的反码 + 1，负数的反码 = 负数的补码 - 1。

5.0的反码、补码都是0。

6.在计算机运算的时候，都是以补码的方式来运算的。

7.当我们看运算结果的时候，要看它的原码。

关注微信公众号获取更多资讯：​​​​![在这里插入图片描述](https://img-