计算机数值表示
计算机数值表示
符号定义
| Symbol | Type | Meaning | Defineition |
|---|---|---|---|
| \(B2T_w\) | 函数 | Binary to two's complement | \(\vec{x} = [x_{w-1},x_{w-2},\cdots,x_0];\;B2T_w(\vec{x})=-x_{w-1}2^{w-1}+\sum\limits_{i=0}^{w-2}x_i2^i\) |
| \(B2U_w\) | 函数 | Binary to unsigned | \(\vec{x} = [x_{w-1},x_{w-2},\cdots,x_0];\;B2U_w(\vec{x})=\sum\limits_{i=0}^{w-1}x_i2^i\) |
| \(U2B_w\) | 函数 | Unsigned to binary | \(B2U_w\)的反函数 |
| \(U2T_w\) | 函数 | Unsigned to two's complement | \[0\leq u\leq UMax_w;U2T_w(u)=B2T_w(U2B_w(u))=\begin{cases}u, u\leq TMax_w \\ u-2^w, u>TMax_w\end{cases}\] |
| \(T2B_w\) | 函数 | Two's complement to binary | \(B2T_w\)的反函数 |
| \(T2U_w\) | 函数 | Two's complement to unsigned | \[TMin_w \leq x \leq TMax_w; T2U_{w}(x) = B2U_{w}(T2B_{w}(x))= \begin{cases} x+2^w, x<0\\x, x\geq 0 \end{cases}\] |
| \(TMin_w\) | 常数 | Minimum two's-complement value | \(-2^{w-1}\) |
| \(TMax_w\) | 常数 | Maximum two's-complement value | \(2^{w-1}-1\) |
| \(UMax_w\) | 常数 | Maximum unsigned value | \(2^w-1\) |
| \(+_w^t\) | 操作符 | Two's-complement addition | Let us define the operation \(+_w^t\) for arguments \(x\) and \(y\), where \(-2^{w-1} \leq x, y \leq 2^{w-1}-1\), as the result of truncating the integer sum \(x + y\) to be \(w\) bits long and then viewing the result as a two’s-complement number. |
| \(+_w^u\) | 操作符 | Unsigned addition | Let us define the operation \(+_w^u\) for arguments \(x\) and \(y\), where \(0 \leq x, y < 2^w\), as the result of truncating the integer sum \(x + y\) to be \(w\) bits long and then viewing the result as an unsigned number |
| \(*_w^t\) | 操作符 | Two's-complement multiplication | \(x\)与\(y\)相乘，然后截断\(w\)比特，将剩余的比特按照补码解析。等效于\(x \; *_w^t \; y=U2T_w((x ·y)\; mod \; 2^w)\) |
| \(*_w^u\) | 操作符 | Unsigned multiplication | \(x\)与\(y\)相乘，然后截断\(w\)比特，将剩余的比特按照无符号数解析。等效于\(x \; *_w^u \; y=(x ·y)\; mod \; 2^w\) |
| \(-_w^t\) | 操作符 | Two's-complement negation | 补码数的逆元运算符，满足\(-_w^tx+_w^tx=0\) |
| \(-_w^u\) | 操作符 | Unsigned negation | 无符号数的逆元运算符，满足\(-_w^ux+_w^ux=0\) |
PS:w表示数据的位宽，\(\vec{x}\)表示二进制bits序列
数值截断
无符号数截断
\(\vec{x}=[x_{w-1},x_{w-2},\cdots,x_0]\)，为\(w\)比特的二进制矢量；\(\vec{x}^\prime = [x_{k-1},x_{k-2},\cdots,x_0]\)，表示被截断之后的\(k\)比特二进制矢量，其中\(w\geq k\)。定义\(x=B2U_w(\vec{x});x^\prime=B2U_k(\vec{x}^\prime)\)，则可以得\(x^\prime = x\;mod\;2^k\)。记\(x^\prime=C_k^ux\)
证明如下：
\[
\begin{align*}
B2U_w([x_{w-1},x_{w-2},\cdots,x_0])\;mod\; 2^k &=\left[\sum_{i=0}^{w-1}x_i2^i\right]\; mod \; 2^k \\
&=\left[\sum_{i=0}^{k-1}x_i2^i\right]\; mod \; 2^k \\
&= \sum_{i=0}^{k-1}x_i2^i \\
&=B2U_k([x_{k-1},x_{k-2},\cdots,x_0])
\end{align*}
\]
因此可以得到：
\[
\begin{align*}
x^\prime = C_k^ux=x\; mod\; 2^k
\end{align*}
\]
截断补码
\(\vec{x}=[x_{w-1},x_{w-2},\cdots,x_0]\)，为\(w\)比特的二进制矢量；\(\vec{x}^\prime = [x_{k-1},x_{k-2},\cdots,x_0]\)，表示被截断之后的\(k\)比特二进制矢量，其中\(w\geq k\)。定义\(x=B2T_w(\vec{x});x^\prime=B2T_k(\vec{x}^\prime)\)，则可以得\(x^\prime = U2T_k(x\;mod\;2^k)\)。记\(x^\prime=C_k^tx\)
证明如下：
\[
\begin{align*}
U2T_k(x\;mod\;2^k)
&= U2T_k(B2T_w([x_{w-1},x_{w-2},\cdots,x_0])\;mod\;2^k) \\
&=U2T_k\left(\left[-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i\right]\; mod \; 2^k\right) \\
&=U2T_k\left(\left[\sum_{i=0}^{k-1}x_i2^i\right]\; mod \; 2^k\right) \\
&= U2T_k\left(\sum_{i=0}^{k-1}x_i2^i \right)\\
&= U2T_k\left(B2U_k([x_{k-1},x_{k-2},\cdots,x_0])\right)\\
&= B2T_k(U2B_k(B2U_k[x_{k-1},x_{k-2},\cdots,x_0]))\\
&= B2T_k([x_{k-1},x_{k-2},\cdots,x_0])\\
&= x^\prime
\end{align*}
\]
因此可以得到：
\[
\begin{align*}
x^\prime = C_k^tx=U2T_k(x\; mod \; 2^k)
\end{align*}
\]
整数运算
无符号加
Let us define the operation \(+_w^u\) for arguments x and y, where \(0 \leq x, y < 2^w\), as the result of truncating the integer sum \(x + y\) to be \(w\) bits long and then viewing the result as an unsigned number。
上述定义等效如下数学等式：其中\(C_w^u\)为一个运算符，将无符号数截断为\(w\)比特。
\[
\begin{align*}
x\;+_w^u\;y = C_w^u(x+y)=(x+y) \; mod \; 2^w
\end{align*}
\]
从而可以推导出无符号加法具有下面的性质：
\[
\begin{equation*}
x\;+_w^u\;y =
\begin{cases}
x+y,&x+y<2^w &Normal\\
x+y-2^w, &2^w\leq x+y< 2^{w+1} & Overflow
\end{cases}
\end{equation*}
\]
无符号加法本质上是模\(2^w\)加法。
溢出检测：
\(0\leq x,y< UMax_w\)，记\(s=x \; +_w^u \; y\)，当且仅当\(s<x\)(或者等效的\(s<y\))时，计算是溢出的（充要条件）
无符号减（无符号加的逆）
对于任意的\(x(0\leq x<2^w)\)，其\(w\)比特的逆元\(-_w^ux\)定义如下：
\[
\begin{equation*}
-_w^ux =
\begin{cases}
x,&x=0\\
2^w-x,&x>0
\end{cases}
\end{equation*}
\]
补码加
Let us define the operation \(+_w^t\) for arguments \(x\) and \(y\), where \(-2^{w-1} \leq x, y \leq 2^{w-1}-1\), as the result of truncating the integer sum \(x + y\) to be \(w\) bits long and then viewing the result as a two’s-complement number.
上述定义等效如下数学等式：其中\(C_w^t\)为一个运算符，将补码截断为\(w\)比特。
\[
\begin{align*}
x \; +_w^t \; y=C_w^t(x+y)=U2T_w((x+y)\; mod \; 2^w)
\end{align*}
\]
对于\(-2^{w-1} \leq x, y \leq 2^{w-1}-1\)，\(+_w^t\)具有如下的性质：
\[
\begin{equation*}
x \; +_w^t \; y=
\begin{cases}
x+y-2^w, & 2^{w-1}-1 < x+y & Positive \; overflow \\
x+y, & -2^{w-1} \leq x+y \leq 2^{w-1}-1 &Normal \\
x+y+2^w, & x+y<-2^{w-1} & Negative \; overflow
\end{cases}
\end{equation*}
\]
除此之外，由于补码加法与无符号的加法有相同的比特级的表示(依据补码加法的定义)，因此：
\[
\begin{equation*}
x \; +_w^t \; y=U2T_w(T2U_w(x) \; +_w^u \; T2U_w(y))
\end{equation*}
\]
由于\(T2U_w(x)=x_{w-1}2^w+x\)，所以：
\[
\begin{align*}
x \; +_w^t \; y &= U2T_w[(x_{w-1}2^w+x+y_{w-1}2^w+y) \; mod \; 2^w]\\
&=U2T_w[(x+y) \; mod \; 2^w]
\end{align*}
\]
溢出检测:
\(TMin_w\leq x,y \leq TMax_w\)，记\(s=x \; +_w^t \; y\)，当且仅当\(x>0\)，\(y>0\)，但是\(s\leq 0\)时，计算是上溢的（充要条件）。当且仅当\(x<0\)，\(y<0\)，但是\(s\geq 0\)时，计算是下溢的（充要条件）。
补码减（补码加的逆）
对于每一个\(x(TMin_w\leq x \leq Tmax_w)\)，都存在一个\(+_w^t\)运算的逆，其表示为\(-_w^tx\)，其定义如下：
\[
\begin{equation*}
-_w^tx =
\begin{cases}
TMin_x, &x=TMin_w\\
-x, & x>TMin_w
\end{cases}
\end{equation*}
\]
无符号加与补码加的比特级等效性
定义\(\vec{x}\)和\(\vec{y}\)是长度为\(w\)的向量；定义整数\(x\)和\(y\)表示该向量以补码解释的整数值（\(x=B2T_w(\vec{x})\)，\(y=B2T_w(\vec{y})\)）；定义非负整数\(x^\prime\)和\(y^\prime\)表示该向量以无符号数解释的整数值（\(x ^ \prime = B2U_w(\vec{x})\)，\(y^\prime=B2U_w(\vec{y})\)）。则具有以下性质：
\[
\begin{equation*}
T2B_w(x\; +_w^t \; y)=U2B_w(x^\prime \; +_w^u \; y^\prime)
\end{equation*}
\]
示例如下：
| \(Mode\) | \(x\) | \(y\) | \(x + y\) | \(Truncated\;\;x + y\) |
|---|---|---|---|---|
| Unsigned | 5 [101] | 3 [011] | 8 [1000] | 0 [000] |
| Two's complement | −3 [101] | 3 [011] | 0 [0000] | 0 [000] |
| Unsigned | 4 [100] | 7 [111] | 11 [1011] | 3 [011] |
| Two's complement | −4 [100] | −1 [111] | -5 [1011] | 3 [011] |
| Unsigned | 3 [011] | 3 [011] | 6 [0110] | 6 [110] |
| Two's complement | 3 [011] | 3 [011] | 6 [0110] | -2 [110] |
证明如下：
证明1：
\[
\begin{align*}
\because x^\prime=x+x_{w-1}2^w \;\;\;\; y^\prime=y+y_{w-1}2^w \\
\end{align*}
\]
\[ \begin{align*} \therefore (x^\prime+y^\prime)\;mod \; 2^w &=[(x+x_{w-1}2^w)+(y+y_{w-1}2^w)]\; mod \; 2^w \\ &=[x+y+(x_{w-1}+y_{w-1})2^w]\; mod \; 2^w\\ &=(x+y)\; mod \; 2^w \end{align*} \]
\[ \begin{align*} \because x \; +_w^t \; y=U2T_w((x+y)\; mod \; 2^w) \end{align*} \]
\[ \begin{align*} \therefore T2U_w(x \; +_w^t \; y)=T2U_w(U2T_w((x+y)\; mod\; 2^w))=(x+y)\;mod\; 2^w \end{align*} \]
综合上述推导可以得到：
\[
\begin{align*}
T2U_w(x \; +_w^t \; y)=(x+y)\;mod \; 2^w=(x^\prime+y^\prime)\;mod \; 2^w=x^\prime \; +_w^u \; y^\prime
\end{align*}
\]
对等式两边同时运用\(U2B_w\)算子，可以得到：
\[
\begin{align*}
U2B_w(T2U_w(x \; +_w^t \; y))=T2B_w(x \; +_w^t \; y)=U2B_w(x^\prime \; +_w^u \; y^\prime)
\end{align*}
\]
证明2：
\[ \begin{align*} \because x=x^\prime-x_{w-1}2^w \;\;\;\; y=y^\prime-y_{w-1}2^w\\ \end{align*} \]
\[ \begin{align*} \therefore x \; +_w^t \; y=C_w^t(x+y)&=U2T_w((x+y)\; mod \; 2^w) \\ &=U2T_w(((x^\prime-x_{w-1}2^w)+(y^\prime-y_{w-1}2^w)) \; mod \; 2^w) \\ &=U2T_w((x^\prime+y^\prime-(x_{w-1}+y_{w-1})2^w) \; mod \; 2^w)\\ &=U2T_w((x^\prime+y^\prime) \; mod \; 2^w) \\ &=U2T_w(x^\prime\;+_w^u\;y^\prime) \end{align*} \]
对等式两边同时运用\(T2B_w\)算子，可以得到：
\[
\begin{align*}
T2B_w(x \; +_w^t \; y)=T2B_w(U2T_w(x^\prime\;+_w^u\;y^\prime))=U2B_w(x^\prime\;+_w^u\;y^\prime)
\end{align*}
\]
无符号乘法
对于\(0\leq x,y \leq UMax_w\)，其无符号乘法定义如下：
\[
\begin{equation*}
x \; *_w^u \; y=C_w^u(x·y)=(x ·y)\; mod \; 2^w
\end{equation*}
\]
补码乘法
对于\(TMin_w \leq x,y \leq TMax_w\)，其补码乘法定义如下：
\[
\begin{equation*}
x \; *_w^t \; y=C_w^t(x·y)=U2T_w((x ·y)\; mod \; 2^w)
\end{equation*}
\]
无符号乘法与补码乘法的比特级等效性
定义\(\vec{x}\)和\(\vec{y}\)是长度为\(w\)的向量；定义整数\(x\)和\(y\)表示该向量以补码解释的整数值（\(x=B2T_w(\vec{x})\)，\(y=B2T_w(\vec{y})\)）；定义非负整数\(x^\prime\)和\(y^\prime\)表示该向量以无符号数解释的整数值（\(x ^ \prime = B2U_w(\vec{x})\)，\(y^\prime=B2U_w(\vec{y})\)）。则具有以下性质：
\[
\begin{equation*}
T2B_w(x\; *_w^t \; y)=U2B_w(x^\prime \; *_w^u \; y^\prime)
\end{equation*}
\]
示例如下：
| \(Mode\) | \(x\) | \(y\) | \(x · y\) | \(Truncated\;\;x · y\) |
|---|---|---|---|---|
| Unsigned | 5 [101] | 3 [011] | 15 [001111] | 7 [111] |
| Two's complement | −3 [101] | 3 [011] | −9 [110111] | −1 [111] |
| Unsigned | 4 [100] | 7 [111] | 28 [011100] | 4 [100] |
| Two's complement | −4 [100] | −1 [111] | 4 [000100] | −4 [100] |
| Unsigned | 3 [011] | 3 [011] | 9 [001001] | 1 [001] |
| Two's complement | 3 [011] | 3 [011] | 9 [001001] | 1 [001] |
证明如下：
\[
\begin{align*}
&\because x^\prime=x+x_{w-1}2^w \;\;\;\; y^\prime=y+y_{w-1}2^w &\\
\end{align*}
\]
\[ \begin{align*} \therefore (x^\prime·y^\prime)\;mod \; 2^w &=[(x+x_{w-1}2^w)·(y+y_{w-1}2^w)]\; mod \; 2^w \\ &=[x·y+(x_{w-1}y+y_{w-1}x)2^w+x_{w-1}y_{w-1}w^{2w}]\; mod \; 2^w\\ &=(x·y)\; mod \; 2^w \end{align*} \]
\[ \begin{align*} \because x \; *_w^t \; y=U2T_w((x ·y)\; mod \; 2^w) \end{align*} \]
\[ \begin{align*} \therefore T2U_w(x \; *_w^t \; y)=T2U_w(U2T_w((x·y)\; mod\; 2^w))=(x·y)\;mod\; 2^w \end{align*} \]
综合上述推导可以得到：
\[
\begin{align*}
T2U_w(x \; *_w^t \; y)=(x·y)\;mod \; 2^w=(x^\prime ·y^\prime)\;mod \; 2^w=x^\prime \; *_w^u \; y^\prime
\end{align*}
\]
对等式两边同时运用\(U2B_w\)算子，可以得到：
\[
\begin{align*}
U2B_w(T2U_w(x \; *_w^t \; y))=T2B_w(x \; *_w^t \; y)=U2B_w(x^\prime \; *_w^u \; y^\prime)
\end{align*}
\]