Representation and Computation – Integer

Representation

The Representation of Integer

Unsigned Integer

这是我们最常见的整数表示法，在进制转换中经常使用该等式作为中介

由于是无符号数，我们并不需要考虑负整数的问题，该表示方式建立了一个二进制位模式和十进制非负整数之间的一个简单的双射：

因而，我们说无符号数编码具有唯一性

Signed Integer

Tow’s Complement Method

大部分的机器采用补码编码, 补码的含义为：对于非负整数x，我们使用$2^{w} - x$来计算-x的w位表示

补码编码在无符号数编码的基础上，将二进制位模式的最高位作为符号位，权重为$-2^{w-1}$

也可以把补码编码看成：将无符号数编码的求和式最后一项 取相反数从而得到。

注意到，除了最高位拥有一个非常大的负权重之外，二进制位模式中的其他位的权重均为 正权重！

进而我们可以表示的$最小负数 = UMin_w \dot{=} [10\cdots0] = (1)\times (-2^{w-1})$，$最大正数 = UMax_w \dot{=} [01\cdots111] = \sum_{i=0}^{w-2}{(1)\times2^i}$

注意这个表示范围，因为$2^{n} - \sum_{i=0}^{n-1}{2^i} = 1 \implies |TMin| = |TMax| + 1$

准确地说，补码编码是将整数划分为负数和非负数。

同理，补码编码也具有唯一性

此外，我们还发现$UMax_w = 2TMax_w + 1$

证明：思路是让等式两边的值相等。

Q.E.D

Ones’ Complement

反码编码与补码编码的区别在于，反码编码最高位的权重比补码编码的最高位权重 小1

反码表示的含义为：使用[111...1] - 1来表示-x的反码表示

Sign-Magnitude

原码编码与补码编码虽然都是由最高位来决定符号，但原码编码的最高位仅仅用于表示正负。

而且，我们注意到后面的$\sum_{i=0}^{w-1}{x_i2^i}$部分相等，但由于对负数的表示方法不同。

原码编码的 正整数个数 = 负整数个数，并且，我们还发现表示0的位模式有两个： +0 和 -0

多出来的一个0是由补码编码中的最小的负整数 的位模式所得来的。

$2^w = \sum_{i=0}^{w-1}{x_i2^i} + 1$

Coding Conversion

T2U

补码编码和无符号数编码的区别在于位模式的最高位的权重。

因此，需要分情况考虑x的补码编码表示下的位模式的最高位：

1. 最高位 = 0：即x在补码编码下为非负整数，则可以直接转化为 无符号数编码的x

   因为无符号数编码的非负整数的范围 > 补码编码的非负整数的范围，所以当前的非负数必定可以被装下

2. 最高位 = 1：即x的补码编码下为负数，则在补码编码的表示下，最高位权重为$-2^{w-1}$，在无符号数的编码表示下，最高位的权重为$2^{w-1}$。

   因此，$\Delta weight = 2^{w-1} - (-2^{w-1} = 2 * 2^{w-1} = 2^w)$

综上，我们得出结论：$B2U_w(T2B_w(x)) = \textcolor{red}{T2U_w(x) = x + x_{w-1} * 2^{w}}$

该结论表明，当有符号数(即用补码编码)被映射到无符号数（即用无符号正数编码）时，负数会被转化为大的正数，而非负数保持不变。

U2T

Unsigned Integer和Two's Complement的区别就在于位模式的最高位，而除了最高的其他w-1位所表示的权重是一样的

因此，我们仍然需要从位模式的最高位 的取值情况 来考虑：

1. $x_{w-1} = 0 \implies u \le TMax_w$：在这种情况下，无符号数编码和补码编码所表示的含义就是一样的了。

2. $x_{w-1} = 1 \implies u \gt TMax_w$：对于位模式的最高位为1的情况。

我们可以得出结论：$\textcolor{red}{U2T_w(u) = u -u_{w-1} \times 2^{w}}$

与有符号数和无符号数转换相关的结论：

$UMax_w = 2TMax_w+ 1$

综上，Q.E.D

Extend Bit Mode

当在不同字长的证整数之间进行转换，同时又想保持数值不变时。

显然，我们只可能从较小的数据类型 -> 较大的数据类型

Methods

Zero Extension

Sign Extension

在需要将补码数字转化为一个更大的数据类型且保持数值不变时，可使用符号拓展。

也就是说：我们可以将较小的补码数字表示 拓展到较大的补码数字表示并且保持数值不变

由于$x_0,\cdots,x_{w-2},x_{w-1}$的部分在补码编码下的拓展前后的前后的权重 相等。

故接下来我们只需要证明，我们为$\vec{x}'$拓展的位的权重的累加 = 0。

但为了证明的简单，我们使用归纳法：仅证明符号拓展了1位的补码编码的数值 不会发生改变，进而得出对补码编码符号拓展任意多位，数值也不会改变

分类讨论$x_{w-1}$的取值

1. $x_{w-1} = 0$：显然成立
2. $x_{w-1} \ne 0$：

Q.E.D

蓝色部分：先考虑从$\vec{x}$和$\vec{x}'$的$x_{w-1}$，当位数拓展1位后，拓展前后的第w-1位的含义就不同了

红色部分：这部分是多出来的，可以直接相加即可。第w位的值为$x_{w-1}$，权重为$-2^{w}$

另一种观点是：$2^w - 2^{w-1} = 2^{w-1}$

即加上一个权为-2^w的位 = 将一个权为-2^{w-1}的位 转换为 权为2^{w-1}

PROOF

1. 如果权重前的系数=0，则显然成立
2. 如果权重前的系数≠0，则 $((2^{w-1}) - (-2^{w-1})) + (-2^w) = 0$

Truncate Integer

截断发生在较大的数据类型 -> 较小的数据类型

Methods

Truncate Unsigned Integer

对于无符号数编码 ：$i \in N, weight(x_i) = 2^i$

分别计算等式左侧和等式右侧

$B2U_w(\vec{x}) = \sum_{i=0}^w x_i 2^i$

$B2U_k(\vec{x}') = \sum_{i=0}^{k}{x_i2^i}$

所有被截去的位的重数都是$2^i, i \ge k$ 因此这些权在 取模操作 下都变为0

也就是说：取模操作$\mod 2^k$可以使得$weight(x_i) = 0, i \ge k$

Q.E.D

Truncate Two’s Complement Integer

$0 \le x \mod 2^k \le 2^k - 1$ 等效于将最高有效位$x_{k-1}$的权重 从$2^{k-1}$转换到$-2^{k-1}$

注：在对最高位k进行$\mod 2^k$操作之前，如果$x_k = 1$则我们当然可以 加权$2^{k-1}$，但是，在进行 取模操作后，即使$x_k = 1$，则在取模运算后，我们加权+0

• 如果$x_k = 0$，那么权重转换的等效性 显然成立。
• 如果$x_k = 1$，则在取模运算后，相当于 最高位是废的，本应当加权$2^{k-1}$实际却只加权$+0$。这等价于我们损失了$2^{k-1}$数量的权（即实际加权为$-2^{k-1}$）

Q.E.D

Computation

Unsigned Addition

如果$sum = x+y \lt 2^w$，则$sum_{w+1} = 0$该位被丢弃不会影响数值

如果$sum = x + y \ge 2^w$，则$sum_{w+1} = 1$该位被丢弃会影响数值，丢弃该位最高位=数值减少$2^w$

Overflow Detection

Unsigned for Non

注：上面的-号并不是减号，而是表示求逆元

根据模数加法（阿贝尔群 Abelian Group）：对于$_w^ux \implies \exists -_w^ux, -_w^ux + _w^ux = 0$

1. 当x = 0时，加法逆元即为0
2. 当x > 0时，考虑$2^w - x$，有$0 \lt 2^w - x \lt 2^w$且$(x + \textcolor{hotpink}{(2^w - x)}) \mod 2^w = 2^w \mod 2^w = 0$。故$2^w-x$是$_w^u+$下的加法逆元

Tow’s Complement Addition

上述式子告诉我们，补码加法和无符号加法之间有完全相同的位级表示。

所以，对于$+_w^t$运算：可以先将参数转化为无符号数，执行无符号加法，然后再将结果转化为补码：

Overflow Detection for Two’s Complement Addition

Two’s Complement for Non

$TMin_w + TMin_w = -2^{w-1} + (-2^{w-1}) = -2^w \implies \text{Negative Overflow}$

$\therefore TMin_w + _w^tTMin_w = -2^w \textcolor{red}{\underbrace{+ 2^w}_{\text{Negative Overflow}}}= 0$

$\because\forall x \gt TMin_w, -x + x = 0$

Q.E.D

Unsigned Multiplication

Two’s Multiplication

对于$-2^{w-1} \le x,y \le 2^{w-1} -1$内的整数x和y可以被表示为w位的补码数字。

但$-2^{w-1} \cdot （2^{w-1} - 1) = -2^{w-1} \cdot -2^{w-1} = -2^{2w-2} \implies -2^{2w-2} \le x \cdot _w^ty \le -2^{2w-2}$