信息的表示和处理

信息存储

虚拟地址空间只是一个展现给机器级程序的概念性映像。实际是将动态随机访问存储器（DRAM），闪存，磁盘存储器，特殊硬件和操作系统结合起来，为程序提供一个看上去统一的字节数组。

C语言中一个指针的值（无论它指向一个整数、一个结构或某个其他程序对象）都是某个存储块的第一个字节的虚拟地址。

C编译器还把每个指针和类型信息绑定起来，这样就可以根据指针的类型，生成不同的机器级代码来访问存储在指针所指向位置处的值。

对一个字长为$w$位的机器而言，虚拟地址的范围为$0$~$2^{w}-1$，程序最多访问$2^w$个字节。（64位机器sizeof(char *) //8）

在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。

位级运算的一个常见用法就是实现掩码运算，这里掩码是一个位模式，表示从一个字中选出的位的集合。

整数表示

用位来编码整数有两种形式：一种只能表示非负数，而另一种能够表示负数、零和整数。

下图的数学术语，用于精确定义和描述计算机如何编码和操作整数：

C和C++都支持有符号（默认）和无符号数。Java只支持有符号数。

无符号数的编码

假设有一个整数数据类型有 $w$ 位。

可以使用位向量 $\vec{x}$，表示整个向量；或者使用 $[x_ {w-1},x_ {w-2}, …, x_ 0]$ 表示向量中的每一位。

把 $\vec{x}$ 看做一个二进制表示的数，就获得了 $\vec{x}$ 的无符号表示。在这个编码中， 每个位 $x_ i$ 都取值 $0$ 或 $1$ 。

无符号数编码的定义

$B2U_ w(\vec{x})$ 函数是用于将 $\vec{x}$ 表示的二进制无符号数转换为十进制无符号数。

对向量 $\vec{x}=[x_ {w-1}, x_ {w-2}, …, x_ 0]$: $$ B2U_w(\vec{x}) \equiv \sum_{i=0}^{w-1}x_i2^i \tag{1} $$

$$UMax_ w \equiv \sum_ {i=0}^{w-1}2^i=2^w-1$$

$$UMax_ 4=B2U_ 4([1111])=2^4-1=15$$

无符号数编码的唯一性： 函数$B2U_w$是一个双射。

补码编码

最常见的有符号数的计算机表示方式就是补码（two’s-complement）。

补码会将字的最高有效位解释为负权（negative weight）。

补码编码的定义

对向量 $\vec{x}=[x_ {w-1}, x_ {w-2}, …, x_ 0]$ :

$$ B2T_ w(\vec{x})=-x_ {w-1}2^{w-1} + \sum_ {i=0}^{w-2}x_ i2^i \tag{2} $$

最高有效位 $x_ {w-1}$ 也称为符号位，它的权重为 $-2^{w-1}$ ，是无符号表示中权重的负数。符号位被设置为 $1$ 时，表示值为负，而当设置为 $0$ 时，值为非负。

$$ \begin{align} B2T_ 4([0001]) &= -0 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 = 1 \\ B2T_ 4([0101]) &= -0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 5 \\ B2T_ 4([1011]) &= -1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = -5 \\ B2T_ 4([1111]) &= -1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 1 * 2^0 = -7 \end{align} $$

补码编码的唯一性： 函数$B2T_w$是一个双射。

下图是针对不同字长，几个重要数字的位模式和数值。 补码的范围是不对称的： $|TMin|=|TMax|+1$，$TMin$ 没有与之对应的整数。之所以有这样的不对称性，是因为一半的位模式（符号位设置为1的数）表示负数，而另一半（符号位为0的数）表示非负数。

因为 $0$ 是非负数，也就意味着能表示的正数比负数少一个。

最大的无符号数刚好比补码的最大值的两倍大 $1$ ：$UMax_w=2TMax_w+1$。 补码表示中所有表示负数的位模式在无符号数中都变成了正数。

术语补码来源于这样一个情况，对于非负数 $x$ ，我们用$2^w-x$来计算 $-x$ 的 $w$ 位表示。

无符号和补码的转换

C语言允许在各种不同的数字数据类型之间做强制类型转换，但是强制类型转换的结果保持位值不变，只是改变了解释这些位的方式。

#include <stdio.h>
int main(){
    short int v=-12345;
    unsigned short uv=(unsigned short)v;
    printf("v=%d,uv=%u\n",v,uv);//v=-12345,uv=53191
    return 0;
}

可以发现-12345和53191的二进制位模式相同，因为 $2^{16}-12345=53191$ 。

大多数C语言的实现，处理同样字长的有符号数和无符号数之间相互转换的一般规则是：数值可能会变，但是位模式不变。

$-x$的补码的位模式和$2^w-x$的无符号数的位模式相同。因此计算一个负数补码的位模式，只要计算对应的无符号数的位模式即可。

补码转换为无符号数

对满足 $TMin_w \leq {x} \leq {TMax_w}$ 的 $x$ 有： $$ T2Uw(x)=\begin{cases} x+2^w &, x<0 \\ x &, x\geq{0} \tag{3} \end{cases} $$

推导如下：

1. 由公式（1）和公式（2）可以得出 $$ \begin{align} B2U_ w(\vec{x}) - B2T_ w(\vec{x}) &= \sum_ {i=0}^{w-1}x_ {i}2^i - (-x_ {w-1}2^{w-1} + \sum_ {i=0}^{w-2}x_ {i}2^{i}) \\ &= x_ {w-1}2^{w-1} + x_ {w-1}2^{w-1} \\ &= x_ {w-1}2^w \\ B2U_ w(\vec{x}) &= x_{w-1}2^w + B2T_ w(\vec{x}) \end{align} $$

2. 令 $\vec{x} = T2B_ w(x)$ 则有 $$ \begin{align} B2U_ w(\vec{x}) &= B2U_ w(T2B_ w(x)) \\ &= T2U_ w(x) \\ &= x_ {w-1}2^w + B2T_ w(T2B_ w(x)) \\ &= x_ {w-1}2^w + x \end{align} $$

3. 得出结论如下 $$ T2U_ w(x) = x_ {w-1}2^w + x \tag{4} $$

4. 当 $x \geq 0$ 时， $x_ {w-1} = 0$ ，则 $T2U_ w(x) = x$ ；当 $x < 0$ 时，$x_ {w-1} = 1$， 则 $T2U_ w(x) = 2^w + x$， 符合公式 $(3)$ 。

无符号数转换为补码

对满足 $0\leq{u}\leq {UMax_ w}$ 的 $u$ 有： $$ U2T_ w(u)=\begin{cases} u &, u\leq{TMax_w} \\ u-2^w &, u>TMax_w \tag{5} \end{cases} $$

推导如下：

1. 由公式（1）和公式（2）可以得出 $$ \begin{align} B2U_ w(\vec{u}) - B2T_ w(\vec{u}) &= \sum_ {i=0}^{w-1}u_ {i}2^i - (-u_ {w-1}2^{w-1} + \sum_ {i=0}^{w-2}u_ {i}2^{i}) \\ &= u_ {w-1}2^{w-1} + u_ {w-1}2^{w-1} \\ &= u_ {w-1}2^w \\ B2T_ w(\vec{u}) &= B2U_ w(\vec{u}) - u_{w-1}2^w \end{align} $$

2. 令 $\vec{u} = U2B_ w(u)$ 则有 $$ \begin{align} B2T_ w(\vec{u}) &= B2T_ w(U2B_ w(u)) \\ &= U2T_ w(u) \\ &= B2U_ w(U2B_ w(u)) - u_ {w-1}2^w \\ &= u - u_ {w-1}2^w \end{align} $$

3. 得出结论如下 $$ U2T_ w(u) = u - u_ {w-1}2^w \tag{6} $$

4. 当 $u > TMax_ w$ 时， $u_ {w-1} = 1$ ，则 $U2T_ w(u) = u - 2^w$ ；当 $u \leq TMax_ w$ 时，$u_ {w-1} = 0$， 则 $U2T_ w(u) = u$， 符合公式 $(4)$ 。

映射区间如图所示：

扩展数

无符号数的零扩展

将无符号数转换为更大的数据类型，只需要在位表示的开头添加 $0$， 称为零扩展。

数学描述如下：

定义宽度为 $w$ 的位向量 $\vec{u}=[u_ {w-1}, u_ {w-2}, …, u_ 0]$ 和宽度为 $w’$ 的位向量 $\vec{u’}=[0, …, 0, u_ {w-1}, u_ {w-2}, …, u_ {0}]$，其中 $w’>w$ ，则 $B2U_ w(\vec{u})=B2U_ w(\vec{u’})$。

补码的符号扩展

将补码数字转换为更大的数据类型，需要执行符号扩展，即在位表示中添加最高有效位的值。

数学描述如下：

定义宽度为 $w$ 的位向量 $\vec{x} = [x_ {w-1}, x_ {w-2}, …, x_ 0]$ 和宽度为 $w’$ 的位向量 $\vec{x’}=[\underbrace{x_ {w-1}, …, x_ {w-1}}, x_ {w-1}, x_ {w-2}, …, x_ 0]$，其中 $w’>w$ ，则$B2T_ w(\vec{x}) = B2T_ {w’}(\vec{x’})$。

推导：

1. 令 $w’ = w + k$，则待证明公式如下：

$$B2T_ {w+k}([\underbrace{x_ {w-1}, …, x_ {w-1}}_ {k}, x_ {w-1}, x_ {w-2}, …, x_ 0]) = B2T_ w([x_ {w-1},x_ {w-2}, …, x_ 0])$$

2. 当 $k$ 取任意值时，证明如下： $$ \begin{align} B2T_ {w+k}([\underbrace{x_ {w-1}, …, x_ {w-1}}_ {k}, x_ {w-1}, x_ {w-2}, …, x_ 0]) &= -x_ {w-1}2^{w+k-1} + \sum_ {i=0}^{w+k-2}x_ {i}2^{i}\\ &= -x_ {w-1}2^{w+k-1} + \sum_ {i=w-1}^{w+k-2}x_ {i}2^{i} + \sum_ {i=0}^{w-2}x_ {i}2^{i} \\ &= -x_ {w-1}2^{w+k-1} + x_ {w-1}\sum_ {i=w-1}^{w+k-2}2^{i} + \sum_ {i=0}^{w-2}x_ {i}2^{i} \\ &= -x_ {w-1}(2^{w+k-1} - \sum_ {i=w-1}^{w+k-2}2^{i}) + \sum_ {i=0}^{w-2}x_ {i}2^{i} \\ &= -x_ {w-1}(2^{w+k-1} - 2^{w+k+1} + 2^{w-1}) + \sum_ {i=0}^{w-2}x_ {i}2^{i} \\ &= -x_ {w-1}2^{w-1} + \sum_ {i=0}^{w-2}x_ {i}2^{i} \\ &= B2T_ {w}([x_ {w-1}, x_ {w-2}, …, x_0)]) \end{align} $$

3. 上式的证明过程中使用等比数列的求和公式，如下：$S_ n = a_ {1} \frac{1 - q^n}{1 - q}$ 。

4. 补码符号扩展的关键属性是 $2^{w} - 2^{w-1} = 2^{w-1}$。因此加上一个权值为 $-2^{w}$ 的位，和将一个权值为 $-2^{w-1}$ 的位转换为一个权值为 $2^{w-1}$ 的位，这两项运算的综合效果就会保持原始的数值。

截断数

将一个 $w$ 位的数 $\vec{x} = [x_ {w-1}, x_ {w-2}, …, x_ {0}]$ 截断为一个 $k$ 位数字时，会丢弃高 $w - k$ 位，得到一个位向量 $\vec{x’} = [x_ {k-1}, x_ {k-2}, …, x_ 0]$。

截断一个数字可能会改变其值，这是溢出的一种形式。

截断无符号数

令 $\vec{x}$ 等于位向量 $[x_ {w-1}, x_ {w-2}, …, x_ {0}]$，而 $\vec{x’}$ 是将其截断为 $k$ 位的结果：$\vec{x’} = [x_ {k-1}, x_ {k-2}, …, x_ {0}]$。

令$x=B2U_w(\vec{x})$，$x’=B2U_k(\vec{x’})$，则$x’=x \mod 2^{k}$。

所有被截去的位其权重形式都为 $2^{i}$ ，其中 $i \geq k$ 。 因此，每一个权重在取模操作下结果都为 $0$ 。

推导： $$ \begin {aligned} B2U_w([x_{w-1},x_{w-2},…,x_{0}]) \mod 2^{k} &= [\sum_{i=0}^{w-1}x_{i}2^{i}] \mod 2^{k}\\ &= ([\sum_{i=k}^{w-1}x_{i}2^{i}] \mod 2^{k} + [\sum_{i=0}^{k-1}x_{i}2^{i}] \mod 2^{k}) \mod 2^{k}\\ &=(0+[\sum_{i=0}^{k-1}x_{i}2^{i}] \mod 2^{k}) \mod 2^{k}\\ &=[\sum_{i=0}^{k-1}x_{i}2^{i}] \mod 2^{k}\\ &=B2U_k([x_{k-1},x_{k-2},…,x_{0}]) \end {aligned} $$

对于任何 $i \geq {k}$， $2^{i} \mod 2^{k} = 0$。

截断补码数值

补码截断也具有相似的属性，只不过要将截断后的最高位转换为符号位。

令 $\vec{x}$ 等于位向量 $[x_ {w-1}, x_ {w-2}, …, x_ {0}]$，而 $\vec{x’}$ 是将其截断为 $k$ 位的结果：$\vec{x’} = [x_ {k-1}, x_ {k-2}, …, x_ {0}]$。

令 $x=B2U_w(\vec{x})$，$x’ = B2T_ k(\vec{x’})$，则 $x’ = U2T_ k(x \mod 2^k)$ 。

计算补码截断时，先将补码的位模式转为无符号数，再使用无符号数截断方式，最后再转换会补码。

$$ B2T_ k[x_ {k-1}, x_ {k-2}, …, x_ {0}] = U2T_ k(B2U_ w([x_ {w-1}, x_ {w-2}, …, x_ {0}]) \mod 2^k) $$

整数运算

无符号数加法

两个非负整数 $x$ 和 $y$，满足 $0 \leq x$，$y < 2^w$。

每个数都可以表示为 $w$ 位的无符号数字，则其和的可能范围为 $0 \leq x + y \leq 2^{w+1} -2$，表示这个和可能需要 $w+1$ 位。

运算$+_ {w}^{u}$ ：对于参数 $0 \leq x, y < 2^w$，该操作是把整数和 $x + y$ 截断为 $w$ 的结果，再把这个结果看做是一个无符号数。

数学描述如下：

对满足 $0 \leq x, y < 2^{w}$ 的 $x$ 和 $y$ 有： $$ x +_{w}^{u} y= \begin {cases} x+y &, x+y < 2^{w} \\ x+y-2^{w} &, 2^{w} \leq x+y < 2^{w+1} \end {cases} $$

1. 如果 $x+y<2^{w}$ 的和的 $w+1$ 位的位表示中的最高位为 $0$，因此丢弃它不会改变这个数的值。
2. 如果 $2^{w} \leq x+y <2^{w+1}$ 的和的$w+1$位表示中的最高位会等与 $1$，因此丢弃它就相当于从和中减去了 $2^{w}$。

检测无符号数加法中的溢出

对于 $0 \leq x, y \leq UMax_w$ 中的 $x$ 和 $y$，令 $s \equiv x +_ {w}^{u} y$，则对计算$s$，当且仅当 $s < x$时，发生了溢出。

推导如下：

1. 由于是无符号加法，所以 $s = x + y \geq x$。如果 $s$ 没有溢出，则可以肯定 $s \geq x$。
2. 如果 $s$ 确实溢出，则有 $s = x + y - 2^w$。又因为 $y < 2^w$，因此 $s = x + (y - 2^w) < x$。

无符号数求反

阿贝尔群

模数加法形成了一种数学结构，称为阿贝尔群。

它有一个单位元 $0$，并且每个元素有一个加法逆元。

考虑 $w$ 位的无符号数的集合，执行加法运算 $+_ w^u$。

对于每个值 $x$，必然有某个值 $-_ {w}^{u}x$ 满足 $-_ {w}^{u}x +_ {w}^{u} x=0$。

无符号数求反

对于满足 $0 \leq x < 2^w$ 的任意 $x$，其 $w$ 位的无符号逆元 $-_ {w}^{u}x$ 由下式给出： $$ -_{w}^{u}x=\begin {cases} x &, x=0\ 2^w-x &, x>0 \end {cases} $$

补码加法

对满足条件 $-2^{w-1} \leq x, y \leq 2^{w-1} - 1$ 的整数值 $x$ 和 $y$，其和的值范围为 $-2^{w} \leq x + y \leq 2^{w} - 2$ 。需要 $w+1$ 位，才能准确表示。

运算$x+_ {w}^{t} y$： 整数和 $x + y$ 被截断为 $w$ 位的结果，并将这个结果看作补码数。

数学描述如下：

对满足 $-2^{w-1}\leq x,y\leq 2^{w-1}-1$ 的整数 $x$ 和 $y$，有： $$ x+_{w}^{t} y=\begin {cases} x+y-2^{w} &, 2^{w-1}\leq x+y 正溢出\\ x+y &, -2^{w-1}\leq x+y <2^{w-1} 正常 \\ x+y+2^w &, x+y<-2^{w-1} 负溢出 （加上2^w才是抵消掉被截断的最高位） \end {cases} $$ 该公式左侧的和 $x + y$ 的取值范围为 $-2^{w} \leq x + y \leq 2^{w} - 2$；右侧的是该和截断为 $w$ 位补码的结果。

推导

1. 补码加法与无符号数加法有相同的位级表示，则运算 $+_ {w}^t$ 的计算方式为：将其参数转换为无符号数，执行无符号数加法，再将结果转换为补码。公式描述如下： $$ x +_ {w}^{t} y \equiv U2T_ {w}(T2U_ {w}(x) + T2U_ {w}(y)) $$
2. 由公式 $(4)$ 可以得出， $$ \begin{align} T2U_ {w}(x) &= x_ {w-1}2^{w} + x \\ T2U_ {w}(y) &= y_ {w-1}2^{w} + y \end{align} $$
3. 由于 $+_ {w}^u$ 是模 $2^w$ 的加法，以及模数加法的属性，可以得出： $$ \begin{align} x +_ {w}^{t} y &= U2T_ {w}(T2U_ {w}(x) + T2U_ {w}(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} $$
4. 定义 $z \equiv x + y$，$z’ \equiv z \mod 2^w$ ，$z’’ \equiv U2T_ {w}(z’)$ ，结果分析如下：
   1. 当 $-2^w \leq z < -2^{w-1}$， 有 $z’ = z + 2^w$，且 $0 \leq z’ < -2^{w-1} + 2^{w} = 2^{w-1}$ ，可得出 $ z’’ = x + y + 2^w$。此时 $z$ 最高位为 $1$，次高位为 $0$，截断最高位相当于减去 $2^w$，负溢出。
   2. 当 $-2^{w-1} \leq z <0$，有 $z’ = z + 2^w$，且 $-2^{w-1} + 2^{w} = 2^{w-1} \leq z’ < 2^w$，由公式 $(5)$ 可得出 $z’’ = x + y$ 。
   3. 当 $0 \leq z < 2^{w-1}$，有 $z’ = z$，且 $0 \leq z’ < 2^{w-1}$，可得出 $z’’ = z$。
   4. 当 $2^{w-1} \leq z < 2^w$ 有 $z’ = z$，且 $2^{w-1} \leq z’ < 2^{w}$，由公式 $(5)$ 可得出 $z’’ = z’ - 2^{w} = x + y - 2^{w}$。

补码数将 $w+1$位 截断为 $w$ 位。先将二进制位模式转换为无符号数然后取模运算再转换为补码。

补码的非

对 $TMin_ w \leq x \leq TMax_ w$ 的 $x$，其补码的非 $-_ {w}^{t}x$ 由下式给出： $$ -_{w}^{t}x=\begin {cases} TMin_w &, x=TMin_w\\ -x &, x>TMin_w \end {cases} $$

$TMin_w+TMin_w=-2^{w-1}+(-2^{w-1})=-2^{w}$，这将导致负溢出，因此$TMin_w+_{w}^{t}TMin_w=-2^{w}+2^{w}=0$。

无符号数乘法

范围在$0\leq x,y\leq 2^{w}-1$内的整数$x$和$y$可以被表示为$w$位的无符号数，但是它们的乘积$x*y$的取值范围为$0$到$2^{2w}-2^{w+1}+1$之间。 这可能需要$2w$来表示。不过，C语言中的无符号乘法被定义为产生$w$位的值，就是$2w$位的整数乘积的低$w$位来表示的值。我们将这个值表示为$x *_{w}^{u} y$。

对满足$o \leq x,y \leq UMax_w$的 $x$ 和 $y$ 有： $$ x * _ {w}^{u} y = (x * y) \mod 2^{w} $$

补码乘法

范围在$-2^{w-1}\leq x,y \leq 2^{w-1}-1$内的整数$x$和$y$可以被表示为$w$位的补码数字，但是它们的乘积$x * y$ 的取值范围为 $-2^{w-1} * (2^{w-1}-1) = -2^{2w-2} + 2^{w-1}$ 到 $(-2^{w-1}) * (-2^{w-1}) = 2^{2w-2}$ 之间。要想用补码来表示这个乘积，可能需要 $2w$ 位。

然而C语言中的有符号乘法是通过将$2w$位的乘积截断为$w$来实现的。我们将这个数值表示为$x * _{w}^{t} y$。将一个补码数截断为 $w$ 位相当于先计算该值模 $2^w$，再把无符号数转换为补码。

数学描述如下：

对满足 $TMin_ w \leq x,y \leq TMax_ w$ 的 $x$ 和 $y$ 有： $$x * _ {w}^{t} y = U2Tw[(x * y) \mod 2^{w}]$$

乘以2的幂

设$x$为位模式$[x_{w-1},x_{w-2},…,x_0]$表示的无符号整数。那么，对于任何$k\geq 0$，我们都认为$[x_{w-1},x_{w-2},…,x_0,\underbrace{0,…,0}_{k}]$给出了$x2^{k}$的$w+k$位的无符号表示，这里右边增加了$k$个0。

推导： $$ \begin{align} B2U_ {w+k}([x_ {w-1}, x_ {w-2}, …, x_ {0}, \underbrace{0, …, 0}_ {k}]) &= \sum_{i=0}^{w-1}x^i2^{i+k}\\ &= [\sum_{i=0}^{w-1}x_i2^i]*2^{k}\\ &= x2^{k} \end{align} $$ C变量 $x$ 和 $k$ 有无符号数值 $x$ 和 $k$，且 $0 \leq k < w$，则C表达式x<<k产生数值$x * _ w^u2^k$。

除2的幂

在大多数机器上，整数除法要比整数乘法更慢–需要30个或更多的时钟周期。

除以2的幂也可以用移位来实现，只不过用的是右移，而不是左移。

无符号和补码数分别使用逻辑移位和算术移位来达到目的。

对于任何实数 $a$，都有 $\lfloor a \rfloor \leq a < \lfloor a \rfloor + 1$ 和 $\lceil a \rceil - 1 < a \leq \lceil a \rceil$。

整数除法总是舍入到零。 对于 $x \geq 0$ 和 $y > 0$，结果会是 $\lfloor \frac{x}{y} \rfloor$，而对于 $x < 0$ 和 $y > 0$，结果会是 $\lceil \frac{x}{y} \rceil$。

无符号数除法

对无符号数运算使用移位是非常简单的，部分原因是由于无符号数的右移一定是逻辑右移。

C变量 $x$ 和 $k$ 有无符号数值 $x$ 和 $k$， 且 $0 \leq k < w$，则C表达式 $x » k$ 产生数值 $\lfloor \frac{x}{2^k} \rfloor$。

推导如下：

1. 设 $x$ 为位模式 $[x_ {w-1}, x_ {w-2}, …, x_ {0}]$ 表示的无符号整数，而 $k$ 的取值范围为 $0 \leq k < w$ 。

2. 设 $x’$ 为 $w - k$ 位位表示 $[x_ {w-1}, x_ {w-2}, …, x_ {k}]$ 的无符号数，而 $x’’$ 为 $k$ 位位表示 $[x_ {k-1}, …, x_ {0}]$ 的无符号数。 $$ \begin{align} x &= \sum_ {i=0}^{w-1}x_ {i}2^{i} \\ x’ &= \sum_ {i=k}^{w-1}x_ {i}2^{i-k} \\ 2^{k}x’ &= 2^{k}\sum_ {i=k}^{w-1}x_ {i}2^{i-k}\\ &= \sum_ {i=k}^{w-1}x_ {i}2^{i} \\ x’’ &= \sum_ {i=0}^{k}x_ {i}2^{i} \\ x &= 2^{k}x’ + x’' \end{align} $$

3. 由于 $0 \leq x’’ < 2^k$，因此 $$ \begin{align} \frac{x}{2^k} &= x’ + \frac{x’’}{2^k} \\ \lfloor \frac{x’’}{2^k} \rfloor &= 0 \\ \lfloor \frac{x}{2^k} \rfloor &= x' \end{align} $$

对位向量 $[x_ {w-1}, x_ {w-2}, …, x_ {0}]$ 逻辑右移 $k$ 位得到位向量 $[0, …, 0, x_ {w-1}, x_ {w-2}, …, x_ k]$ 。这个位向量有数值$x’$，我们可以看到该值可以通过计算x>>k得到。

补码除法

为了保证负数仍然为负，移位执行的是算术右移。

C变量 $x$ 和 $k$ 分别由补码值 $x$ 和无符号数值 $k$，且 $0 \leq k < w$，则当执行算术移位时，C表达式 x>>k 产生数值 $\lfloor x/2^{k} \rfloor$。

推导：

1. 当 $x \geq 0$ 时，变量 $x$ 的最高有效位为 $0$，移位效果和逻辑右移是一样的。因此，对于非负数来说，算术右移 $k$ 位与除以 $2^k$ 是一样的。
2. 除以2的幂的补码除法，向下舍入:
   1. 设$x$为位模式$[x_{w-1},x_{w-2},…,x_{0}]$表示的补码整数，而$k$的取值范围为$0\leq k<w$。设$x’$为$w-k$位$[x_{w-1},x_{w-2},…,x_{k}]$表示的补码数，而$x’’$为低$k$位$[x_{k-1},…,x_{0}]$表示的无符号数。通过与对无符号数类似的分析，我们有$x=2^{k}x’+x’’$，而$0\leq x’’<2^{k}$，得到$x’=\lfloor x/2^{k} \rfloor$
   2. 进一步，可以观察到，算术右移位向量$$[\underbrace{x_{w-1},…,x_{w-1}}{k},x{w-1},x_{w-2},…,x_k]$$。它刚好就是将$[x_{w-1},x_{w-2},…,x_k]$从$w-k$位符号扩展到$w$。因此这个移位后的位向量就是$\lfloor x/2^k \rfloor$的补码的表示。
   3. 如下所示例子：
3. 我们可以通过在移位之前“偏置”这个值，来修正负数向下设置的问题。
4. 除以2的幂的补码除法*，向上舍入
   1. C变量$x$和$k$分别有补码值$x$和无符号数值$k$，且$0\leq k < w$，则当执行算术移位时，C表达式(x+(1<<k)-1)>>k产生数值$\lfloor x/2^k \rfloor$。
   2. 如下图所示：
   3. 我们可以看到低$k$位左边的位可能会加1，也可能不会加1。对于不需要舍入的情况，加上偏量只影响那些被移掉的位。对于需要舍入的情况，加上偏量导致较高的位加1，所以结果会向零舍入。
   4. 偏置技术利用如下属性： 对于整数$x$和$y(y>0)$，$\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor$
   5. 推导：
      1. 查看$\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor$，假设$x=qy+r$，其中$0 \leq r < y$，得到$(x+y-1)/y=q+(r+y-1)/y$，因此$\lfloor (x+y-1)/y \rfloor=q+\lfloor (r+y-1)/y \rfloor$。当$r=0$时，后面一项等于0，而当$r>0$时，等于1。也就是说，通过给$x$增加一个偏量$y-1$，然后在将除法向下舍入，当$y$整除$x$时，我们得到$q$，否则得到$q+1$。

浮点数

• 浮点表示对形如$V=x*2^y$的有理数进行编码。

• 十进制表示法，十进制表示法使用如下形式的表示：$$d_{m}d_{m-1}…d_{1}d_{0}.d_{-1}d_{-2}…d_-{n}$$，其中每个十进制数字$d_{i}$的取值范围是$0~9$。这个表达描述的数值$d$定义如下： $$ d=\sum_{i=-n}^{m}10^i*d_{i} $$

• 数字权的定义与十进制小数点符号“.”相关，这意味着小数点左边的数字的权时10的正幂，得到整数值，而小数点右边的数字的权是10的负幂，得到小数值。

• 考虑一个形如$b_{m}b_{m-1}…b{1}b_{0}.b_{-1}b_{-2}…b_{-n-1}b_{-n}$的表示法，其中每个二进制数字，或者称为位，$b_{i}$的取值范围是0和1。这种表示方法表示的数b定义如下： $$ b=\sum_{i=-n}^{m}2^i*b_{i} $$

• 符号“.”现在变为了二进制的点，点左边的位的权是2的正幂，点右边的权是2的负幂。

• $101.11_2$表示数字$$12^2+12^0+12^{-1}+12^{-2}=5\frac{3}{4}$$

• IEEE浮点标准用$$V=(-1)^{s}M2^{E}$$的形式来表示一个数：

  • 符号 $s$决定这数是负数还是整数，而对于数值0的符号位解释作为特殊情况处理。
  • 尾数 $M$是一个二进制小数，它的范围是$1$$2-\epsilon$，或者$0$$1-\epsilon$。
  • 阶数 $E$的作用是对浮点数加权，这个权重是2的$E$次幂。

• 将浮点数的位划分位三个字段，分别对这些值进行编码：

  • 一个单独的符号位$s$直接编码符号$s$。
  • $k$位的阶码字段$exp=e_{k-1}…e_{1}e_{0}$编码阶码$E$。
  • $n$位小数字段$frac=f_{n-1}…f_{1}f_{0}$编码尾数$M$，但是编码出来的值也依赖与阶码字段的值是否等于0

• 在单精度浮点格式（C语言中的float）中，$s$，$exp$和$frac$字段分别为1位，8位和23位，得到一个32位的表示。在双精度浮点格式（C语言中的double）中，$s,exp$和$frac$字段分别为1位，11位和52位，得到一个64位的表示。如下图所示：{% asset_img 2-32.png %}

• 给定位表示，根据$exp$的值，被编码的值可以分为三种不同的情况。如下图所示：{% asset_img 2-33.png %}

• 规格化的值：

  • 这是最普遍的情况。当$exp$的位模式既不全为0，也不全为1时，都属于这类情况。
  • 在这种情况下，阶码字段被解释为以偏置形式表示的有符号整数。也就是说，阶码的值是$E=e-Bias$，其中$e$是无符号数，其位表示为$e_{k-1}…e_{1}e_{0}$，而$Bias$是一个等于$2^{k-1}-1$的偏置值。由此产生指数的取值范围，对于单精度是$-126$$+127$，而对于双精度是$-1022$$+1023$。
  • 小数字段$frac$被解释为描述小数值$f$，其中$0\leq f<1$，其二进制表示为$0.f_{n-1}…f_{1}f_{0}$，也就是二进制小数点在最高有效位的左边。尾数定义位$M=1+f$。这种方式也叫做隐含的以1开头的表示，因为我们可以把$M$看成一个二进制表达式为$1.f_{n-1}f_{n-2}…f_{0}$的数字。既然我们总是能够调整阶码$E$，使得尾数$M$在范围$1\leq M <2$之中，那么这种表示方式是一种轻松获得一个额外精度位的技巧。

• 非规格化的值：

  • 当阶码域为全0时，所表示的数就是非规格化形式。在这种情况下，阶码值是$E=1-Bias$，而尾数的值是$M=f$，也就是小数字段的值，不包含隐含的开头的1。
  • 非规格化数有两个用途。
    • 首先它们提供了一种表示数值0的方法，因为使用规格化数，我们必须总是使$M\geq 1$，因此我们不能表示0。实际上，$+0.0$的浮点表示的为模式为全0：符号位是0，阶码字段和小数域也全为0，这就得到$M=f=0$。当符号位为1，而其他域全为0时，我们得到值$-0.0$。根据IEEE的浮点格式，值$+0.0$和$-0.0$除了符号位不同外，其他位均相同。
    • 非规格化数的另外一个功能就是表示那些非常接近于0.0的数。它们提供了一种属性，称为逐渐溢出，其中，可能的数值分布均匀地接近于0.0。

• 特殊值：

  • 最后一类数值是指阶码全为1的时候出现的。当小数域全为0时，得到的值表示无穷，当$s=0$时得到$+\infty$，或者当$s=1$时是$-\infty$。当小数域为非零时，结果值表示“NaN”。一些运算的结果不能是实数或无穷，就会返回这样的NaN值（$\sqrt{-1}$）。

• 下图给出了$k=4$的阶码位和$n=3$的小数位，偏置量是$2^{4-1}-1=7$。{% asset_img 2-35.png %}

• 因为表示方法限制了浮点数的范围和精度，所以浮点运算只能近似地表示实数运算。

• 对于值$x$，我们一般想用一种系统的方法，能够找到“最接近的”匹配值$x’$，它可以用期望的浮点形式表示出来。这就是舍入运算的任务。一个关键问题是在两个可能值的中间确定舍入方向。

• 如图所示显示了4中舍入方式：{% asset_img 2-37.png %}向偶数舍入，也被称为向最接近的值舍入，是默认的方式，试图找到一个最接近的匹配值。

• 为什么选用向偶数的舍入方式，是因为其他舍入方式在舍入一组数据时，得到的一组数的平均数会比这些数的实际值或大或小。

• 在我们不想舍入到整数时，也可以使用向偶数舍入。我们只是简单地考虑最低有效位是奇数还是偶数。

• 相似的，向偶数舍入法能够运用到二进制小数上。我们将最低有效位的值0认为是偶数，值1认为是奇数。一般来说，只有对形如$XX…X.YY…Y100…$的二进制位模式的数，这种舍入方式才有效，其中$X$和$Y$表示认为位值，最右边的$Y$是要被舍入的位值。只有这种位模式表示在两个可能的结果正中间的值。这是因为在$0$和$2^{-n}$之间的数值是$2^{-(n+1)}$。