这篇文章是csapp第二章第二节的阅读笔记。
既然知道了信息是如何存储的，那么接下来看看，整数是如何存储的。整数包括两种：有符号整数和无符号整数，分别对应可为负和不可为负。
这里会涉及到如下的一些符号（其中下标的w表示数据的位数）：
| Symbol | Type | Meaning |
|---|---|---|
| $B2T_w$ | 函数 | 二进制到补码 |
| $B2U_w$ | 函数 | 二进制到无符号 |
| $U2B_w$ | 函数 | 无符号到二进制 |
| $U2T_w$ | 函数 | 无符号到补码 |
| $T2B_w$ | 函数 | 补码到二进制 |
| $T2U_w$ | 函数 | 补码到无符号 |
| $TMin_w$ | 常量 | 补码最小值 |
| $TMax_w$ | 常量 | 补码最大值 |
| $UMax_w$ | 常量 | 无符号最大值 |
1. 整型数据类型
首先来看看C语言中几种整型在不同位数的机器下所能表示的范围。
| C data type | Min in 32 | Max in 32 | Min in 64 | Max in 64 |
|---|---|---|---|---|
[signed] char |
$-2^7$ | $2^7-1$ | $-2^7$ | $2^7-1$ |
unsigned char |
0 | $2^8-1$ | 0 | $2^8-1$ |
short |
$-2^{15}$ | $2^{15}-1$ | $-2^{15}$ | $2^{15}-1$ |
unsigned short |
0 | $2^{16}-1$ | 0 | $2^{16}-1$ |
int |
$-2^{31}$ | $2^{31}-1$ | $2^{31}-1$ | $2^{31}-1$ |
unsigned |
0 | $2^{32}-1$ | 0 | $2^{32}-1$ |
long |
$-2^{31}$ | $2^{31}-1$ | $-2^{64}$ | $2^{64}-1$ |
unsigned long |
0 | $2^{32}-1$ | 0 | $2^{64}-1$ |
int32_t |
$-2^{31}$ | $2^{31}-1$ | $-2^{31}$ | $2^{31}-1$ |
uint32_t |
0 | $2^{32}-1$ | 0 | $2^{32}-1$ |
int64_t |
$-2^{63}$ | $2^{63}-1$ | $-2^{63}$ | $2^{63}-1$ |
uint64_t |
0 | $2^{64}-1$ | 0 | $2^{64}-1$ |
2. 无符号数的编码
既然有无符号和有符号两种，那么每种的编码应该是不一样的。首先看看无符号的编码，毕竟这个比较简单。
我们知道，信息的存储就是一个比特序列。如果数据有w位，那么这个数据就可以表示成一个w位的向量$\vec{x}=[x_{w-1},w_{w-2},…,x_0]$，其中每一个$x_i$的取值是0或1。
那么将这个二进制形式的数据转换成无符号类型的十进制数可以：
$$
B2U_w(\vec{x})=\sum_{i=0}^{w-1}x_i2^i
$$
接下来看看w位无符号整数的范围。最小值当然就是0，最大值$UMax_w$对应的二进制数据都是1，那么：
$$
UMax_w=\sum_{i=0}^{w-1}1·2^i=2^w-1
$$
当w=4的时候，$UMax_4=2^4-1=15$。
需要注意的是，函数$B2U_w$是一个双射（bijection）函数。
3. 补码编码
无符号编码不可以表示负数，因为最小值就是0。为了可以表示负数，需要使用补码编码（Two’s-Complement Encodings）。
我们使用符号$B2T_w$来表示将一个二进制编码转换成对应的十进制补码数值。对于一个二进制向量$\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
$$
补码编码将最高位当做标志位，当最高位$x_{w-1}=1$时表示负数；当$x_{w-1}=0$时表示正数。为了统一，这个最高位也加上一个权值$-2^{w-1}$，就可以计算整个向量对应的十进制值了。
接下来看看补码可以表示的范围。当$\vec{x}=[1,0,…,0]$时，表示最小值，即$TMin_w=-2^{w-1}$；当$\vec{x}=[0,1,…,1]$时表示最大值，即$TMax_w=2^{w-1}-1$。
同样，函数$B2T_w$也是一个双射函数。
可知：
- $|TMin_w|=|TMax_w|+1$
- $UMax_w=2TMax_w+1$
4. 有符号与无符号数之间的转换
既然信息的底层存储是一样的，那么不同的解释方法会得到不同的结果。接下来就看看，对于同一个二进制编码来说，使用不同的解释方法（无符号编码和补码编码）得到的结果之间的关系。
无符号编码的取值范围是$[0,UMax_w]$，补码编码的取值范围是$[TMin_w,TMax_w]$。
先看看将补码编码转换成无符号编码。令$T2U_w(x)=B2U_w(T2B_w(x))$，其中$TMin_w\leq x \leq TMax_w$，有：
$$
T2U_w(x)=
\begin{cases}
x+2^w, & \text{x<0}\
x, & \text{x $\geq$ 0}
\end{cases}
$$
比如，$T2U_{16}(-12345)=-12345+2^{16}=53191$，同时可得：$T2U_w(-1)=-1+2^w=UMax_w$。
对于一个$\vec{x}$，我们知道$B2U_w(\vec{x})$和$B2T_w(\vec{x})$，那么：
$$
B2U_w(\vec{x})-B2T_w(\vec{x})=(\sum_{i=0}^{w-1}x_i2^i)-(-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i)=x_{w-1}2^w
$$
也就是说$B2U_w(\vec{x})=B2T_w(\vec{x})+x_{w-1}2^w$，所以：
$$
B2U_w(T2B_w(x))=T2U_w(x)=x+x_{w-1}2^w
$$
这样就可以通过这个公式将一个有符号数转换成无符号数了。
接下来看看从无符号数到有符号数的转换，这个函数记作$U2T_w(u)$。
那么对于$0 \leq u \leq UMax_w$，有：
$$
U2T_w(u)=\left{
\begin{aligned}
u&,&u \leq TMax_w\
u-2^w&,&u > TMax_w
\end{aligned}
\right.
$$
令$\vec{u}=U2B_w(u)$，那么这个编码也就是$U2T_w(u)$的编码，同时有：
$$
B2T_w(u)=B2U_w(u)-u_{w-1}2^w
$$
所以：
$$
U2T_w(u)=B2T(U2B_w(u))=B2U_w(U2B_w(u))-U_{w-1}2^w=u-u_{w-1}2^w
$$
比如，$T2U_{16}(-12345)=65536-12345=53191$。
5. C语言中的有符号数和无符号数
C语言中的数字默认是有符号的，可以通过在数字的末尾加上u或U来指明是无符号的，比如12345U。
C语言中会发生无符号和有符号数之间的转换。要么是显式的：
int tx, ty;
unsigned ux, uy;
tx = (int) ux;
uy = (unsigned) ty;要么是隐式的：
int tx, ty;
unsigned ux, uy;
tx = ux; // Cast to signed
uy = ty; // Cast to unsigned需要注意的是，当有符号和无符号数放在一起运算的时候，C会隐式地将有符号数转换成无符号数。
比如判断-1<0U，-1是有符号数而0U是无符号数，那么-1就会转换成无符号数，$T2U_w(-1)=UMax_w$，导致判断为假。
6. 扩展一个数字的位表示
将一个数扩展成更大的位数表示，同时保留原来的值。对于有符号和无符号，扩展方法不同。
对于无符号数，扩展的最高位直接用0补齐即可。
对于有符号数，需要看原来表示的最高位，用那个最高位来补齐。
需要注意的一点是：当涉及到扩展位数和有符号与无符号之间的转换时，先扩展位数，然后转换类型：
short sx = -12345;
unsigned uy = sx;
printf("uy = %u:\t", uy);
show_bytes((byte_pointer) &uy, sizeof(unsigned));会得到不一样的结果，uy的值变成了4294954951。
7. 减少一个数字的位表示
反过来，减少一个数字的位表示，就会改变所表示的数值了。
对于无符号数，截断后的值$x’=x,mod,2^k$，其中$k$就是截断后的位数。因为：
$$
B2U_w([x_{w-1},x_{w-2},…,x_0]),mod,2^k=[\sum_{i=0}^{w-1}x_i2^i],mod,2^k=[\sum_{i=0}^{k-1}x_i2^i],mod,2^k=\sum_{i=0}^{k-1}x_i2^i=B2U_k([x_{k-1},x_{k-2},…,x_0])
$$
对于有符号数，截断后的值$x’=U2T_k(x,mod,2^k)$。截断后的编码不管是有符号还是无符号都是一样的，所以对于有符号数，截断后的编码还是$[x_{k-1},x_{k-2},…,x_0]$，那么只需要把这个编码转换成对应的有符号数就可以了：
$$
x’=U2T_k(B2U_k([x_{k-1},x_{k-2},…,x_0]))=U2T_k(x,mod,2^k)
$$
8. 关于有符号和无符号数的建议
由于C语言中会有有符号与无符号之间的隐式转换，所以一些情况下会有奇怪的bug出现。比如：
float sum_elements(float a[], unsigned length) {
int i;
float result = 0;
for(i = 0; i <= length-1; i++)
result += a[i];
return result;
}当length=0的时候会出错。这是因为length是无符号的，计算length-1的时候会产生一个巨大的无符号整数，导致判断为真，然后访问非法的地址。
只需要将循环里的判断条件改成i < length即可。
使用无符号数就可能会导致上面类似的问题，那么一个建议就是不使用无符号数。
不过无符号数在一些情况下也是有用的，比如仅仅看作位的集合而不考虑数字的含义的时候：
- 存储的每一位都是标记（flag）；
- 内存地址也是无符号的——系统程序员；
- 数学中的多精度计算，数字是由字的数组表示，也可以使用无符号数。
9. 重要的事儿
- 二进制转无符号数：$B2U_w(\vec{x})=\sum_{i=0}^{w-1}x_i2^i$
- 无符号数的最大值：$UMax_w=2^w-1$
- 二进制转有符号数：$B2T_w(\vec{x})=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$
- 有符号最大值和最小值的关系：$|TMin_w|=|TMax_w|+1$
- 无符号数最大值和有符号数最大值的关系：$UMax_w=2TMax_w+1$
- 有符号数转无符号数：$T2U_w(x)=x+x_{w-1}2^w$
- 无符号数转有符号数：$U2T_w(u)=u-u_{w-1}2^w$
- 同一二进制编码下有符号数和无符号数的关系：$B2U_w(u)-B2T_w(u)=u_{w-1}2^w$
- 截断无符号数：$x’=x,mod,2^k$
- 截断有符号数：$x’=U2T_k(x,mod,2^k)$
