【CSAPP】整数运算

无符号加法

考虑两个非负整数x和y，满足$0\le x,y<2^w$，每个数都能表示为一个w位的无符号数。如果要计算x+y，其结果的可能取值范围是$0\le x+y\le 2^{w+1}-2$，表示该值可能需要w+1位。如果x+y的结果又要和别的数做加法，那可能需要更多的位表示运算结果。这种字长膨胀意味着，要想完整地表示运算的结果，我们不能对整型长度做任何限制。

但实际情况是，在C语言中，整型变量占固定大小的字节和位，当整数运算结果超出了整型变量的表示范围时，计算机运算的结果是截断后的值，与预期值有偏差。

我们定义操作${+}_w^u$是w位的无符号加法。
原理：无符号数加法。
对满足$0\le x,y<2^w$的$x$和$y$，有：
$$\begin{array}{r}x{+}_w^{u}y=\{\begin{array}{ll}x+y,& 0\le x+y\le 2^w-1\\ x+y-2^w,& 2^w\le x+y\le 2^{w+1}-2\end{array}\end{array}$$

说一个算术运算溢出，是指完整的整数结果不能被有限的整型长度所表示，产生了高有效位的丢失。

执行C程序时，系统不会因运算发生溢出而自己报错，因此程序员必须关注该情况。

原理：检测无符号加法中的溢出。
对满足$0\le x,y\le 2^w-1$的x和y，存在$s\dot{=}x{+}_w^{u}y$，当且仅当$s<x$，$s<y$时，运算发生了溢出。

1. 证明：当$s<x$，$s<y$时，运算发生了溢出。
   因为$x\ge 0$，因此$x+y\ge y$，因此$s\ge y$，所以当$s<y$时，发生运算错误（即溢出）。
   因为$y\ge 0$，因此$x+y\ge x$，因此$s\ge x$，所以当$s<x$时，发生运算错误（即溢出）。
2. 证明：当运算发生溢出时，$s<x$，$s<y$。
   运算发生溢出时，$s=x+y-2^w$，因为$y<2^w$，因此$y-2^w<0$，因此$s<x$。
   运算发生溢出时，$s=y+x-2^w$，因为$x<2^w$，因此$x-2^w<0$，因此$s<y$。

对任何一个数$x$而言，存在$-x$使得$-x+x=0$，则称$-x$是$x$的加法逆元，$x$也是$-x$的加法逆元。加法逆元即取反。
原理：无符号数取反。
对满足$0\le x\le 2^w-1$的x，其w位的无符号加法逆元${-}_w^u$可表示为：
$$\begin{array}{r}{-}_w^{u}x=\{\begin{array}{ll}x,& x=0\\ 2^w-x,& x>0\end{array}\end{array}$$

练习1

实现一个函数，如果参数x和y相加不会产生溢出，这个函数就返回1。

int uadd_ok(unsigned x, unsigned y)
{unsigned s = x + y;return s >= x;
}

练习2

给出下表中数的无符号加法逆元 ${-}_4^u$ 的位表示。

x		-x
十六进制	十进制	十六进制	十进制
0x0	0	0x0	0
0x5	5	0xB	11
0x8	8	0x8	8
0xD	13	0x3	3
0xF	15	0x1	1

补码加法

对满足$-2^{w-1}\le x,y\le 2^{w-1}-1$的x和y，x + y的取值范围是$-2^w\le x+y\le 2^w-2$。跟无符号加法一样，当运算结果不能用w位表示时，会截断数据，产生运算溢出。

我们使用操作${+}_w^t$表示w位的补码加法。
原理：补码加法。
对满足$-2^{w-1}\le x,y\le 2^{w-1}-1$的$x$和$y$，有：
$$\begin{array}{r}x{+}_w^{t}y=\{\begin{array}{llc}x+y+2^w,& x+y<-2^{w-1}& 负溢出\\ x+y,& -2^{w-1}\le x+y\le 2^{w-1}-1& 正常\\ x+y-2^w,& x+y\ge 2^{w-1}& 正溢出\end{array}\end{array}$$

在bit层面，无符号加法和补码加法的运算规则是一样的，都是逢二进一。
负溢出指运算结果太小了，小于$-2^{w-1}$；正溢出指运算结果太大了，大于$2^{w-1}-1$。溢出产生了符号翻转。

原理：检测补码加法中的溢出。
对满足$-2^{w-1}\le x,y\le 2^{w-1}-1$的x和y，存在$s\dot{=}x+y$。当且仅当$x>0$，$y>0$，$s\le 0$时，算术运算正溢出；当且仅当$x<0$，$y<0$，$s\ge 0$时，算术运算负溢出。

1. 证明：$x>0$，$y>0$，$s\le 0$时，算术运算正溢出。
   预期$s=x+y>0$而$s\le 0$，显然s过大而无法表示，运算产生了错误（正溢出）。
2. 证明：算术运算正溢出，因此$x>0$，$y>0$时$s\le 0$。
   运算正溢出，那么$s=x+y-2^w$，且$2^{w-1}\le x+y\le 2^w-2$，因此$x>0$，$y>0$，且$2^{w-1}-2^w\le s\le 2^w-2-2^w$，即$-2^{w-1}\le s\le -2\le 0$，即$s\le 0$。
3. 证明：$x<0$，$y<0$，$s\ge 0$时，算术运算负溢出。
   预期$s=x+y<0$而$s\ge 0$，显然s过小而无法表示，运算产生了错误（负溢出）。
4. 算术运算负溢出，因此$x<0$，$y<0$时$s\ge 0$。
   运算负溢出，那么$s=x+y+2^w$，且$-2^w\le x+y<-2^{w-1}$，因此$x<0$，$y<0$，且$-2^w+2^w\le s\le -2^{w-1}+2^w$，即$0\le s\le 2^{w-1}$，即$s\ge 0$。

练习1

填写下表

$x$	$y$	$x+y$	$x{+}_5^t$	情况
[10100]-12	[10001]-15	[100101]-27	[00101]5	负溢出
[11000]-8	[11000]-8	[110000]-16	[10000]-16	正常
[10111]-9	[01000]8	[11111]-1	[11111]-1	正常
[00010]2	[00101]5	[00111]7	[00111]7	正常
[01100]12	[00100]4	[10000]16	[10000]-16	正溢出

练习2

实现一个函数tadd_ok，参数x和y补码相加不产生溢出时，返回1。

int tadd_ok(int x, int y)
{int s = x + y;return !((x > 0 && y > 0 && s <= 0) || (x < 0 && y < 0 && s >= 0));
}

练习3

如下实现存在什么问题？

int tadd_ok(int x, int y)
{int sum = x + y;return (sum - x == y) && (sum - y == x);
}

函数会永远返回1。因为并没有检测到越界的进位。

练习4

下面的函数在计算x - y不溢出时，返回1。

int tsub_ok(int x, int y)
{return tadd_ok(x, -y);
}

x和y取什么值时，该函数会产生错误的结果？写一个该函数的正确版本。
当y的取值为INT_MIN时，-y的取值也为INT_MIN。因此在计算机看来，x-y就是x+y。
此时按现实的整数运算来看，如果x >= 0，x-y预期运算溢出，返回0；如果如果x < 0，x-y预期运算不溢出，返回1。
但在计算机看来，如果x >= 0，tadd_ok(x, -y)不溢出，返回1；如果x < 0，tadd_ok(x, -y)溢出，返回0。

我们以为它做的是减法，实际上它做的是加法。

在计算机运算中，INT_MIN的位级表示是[1, 0, …, 0]，-INT_MIN的位级表示也是[1, 0, …, 0]，因为[1, 0, …, 0] + [1, 0, …, 0] = [0, 0, …, 0]。当然，这不符合现实的整数运算规则。

正确的写法如下：

int tsub_ok(int x, int y)
{if (y == INT_MIN) {return !tadd_ok(x, -y);}return tadd_ok(x, -y);
}

补码的非

取非就是求加法逆元。
对满足$TMi{n}_w\le x\le TMa{x}_w$的x，其补码的非${-}_w^{t}x$表示为：
$$\begin{array}{r}{-}_w^{t}x=\{\begin{array}{ll}TMi{n}_w,& x=TMi{n}_w\\ -x,& TMi{n}_w<x\le TMa{x}_w\end{array}\end{array}$$

在C语言中，可以说，对于任意整数值x，因为x + ~x + 1 = 0，所以-x = ~x + 1。

练习

填写下表。

$x$	${-}_4^{t}x$
0x00	0x00
0x55	0xB-5
0x8-8	0x8-8
0xD-3	0x33
0xF-1	0x11

无符号乘法

两个w位的无符号数相乘，其结果可能需要2w个位才能完整表示。但在C语言中，会根据整数位宽做截断处理。

对满足$0\le x,y\le 2^w-1$的x和y，有：
$$\begin{array}{r}x{\ast }_w^{u}y\dot{=}(x\ast y)mod{2}^w\end{array}$$

补码乘法

对满足$-2^{w-1}\le x,y\le 2^{w-1}-1$的x和y，有：
$$\begin{array}{r}x{\ast }_w^{t}y\dot{=}U2T_w((x\ast y)mod{2}^w)\end{array}$$

w位无符号乘法和w位补码乘法的运算结果的低w位是一样的，区别在于解释这些位的方式。

练习1

填写下表，位宽w=3。

模式	$x$	$y$	$x\ast y$	截断的x*y
无符号	[100]4	[101]5	[010100]20	[100]4
补码	[100]-4	[101]-3	[001100]12	[100]-4
无符号	[010]2	[111]7	[001110]14	[110]6
补码	[010]2	[111]-1	[111110]-2	[110]-2
无符号	[110]6	[110]6	[100100]36	[100]4
补码	[110]-2	[110]-2	[000100]4	[100]4

计算二进制w位的无符号乘法时，先做零扩展，扩展到2w位，再两数相乘，取低2w位。
计算二进制w位的补码乘法时，先做符号扩展，扩展到2w位，再两数相乘，取低2w位。

练习2

考虑下面的函数，它判断两个参数是否会产生溢出，不溢出返回1。

int tmul_ok(int x, int y)
{int p = x * y;return !x || p/x == y;
}

当x = 0时，乘法不溢出，函数返回1。和预期相符。
当x不等于0时：

1. $x\ast y=p+t{2}^w$，其中$t\ne 0$当且仅当计算溢出。
   当$t\ne 0$时，$x\ast y>p$或者$x\ast y<p$，计算溢出。
   如果计算溢出，$p<x\ast y$或者$p>x\ast y$，所以$t\ne 0$。
2. $p=x\ast q+r$，其中q是$p/x$的结果，|r| < |x|。
   r是p除以x的余数，因此一定存在|r| < |x|。
3. q = y当且仅当r = t = 0。
   q = y时，$x\ast q=p+t{2}^w$，因此$x\ast q+r=p+t{2}^w+r$，因此$p=p+t{2}^w+r$，因此$0=0+t{2}^w+r$，所以r = t = 0。
   r = t = 0时，$x\ast y=x\ast q+t{2}^w$，因此$y=q+\frac{t{2}^w}{x}$，因此q = y。

计算溢出时，$r\ne 0$，$t\ne 0$，因此$q\ne y$，$p/x\ne y$，函数返回0。反之不溢出，函数返回1。

练习3

对于数据类型int为32位的情况，设计一个tmul_ok函数，使用64位精度的数据类型int64_t，不使用除法。不溢出返回1。

int tmul_ok(int x, int y)
{int64_t p = (int64_t)x * y;return p == (int)p;  // 截断前后的值是不是一样
}

乘以常数

在大多数机器上，整数乘法指令相当慢。因此，编译器使用了一项重要的优化，就是用移位和加减法运算的组合来代替与常数因子的乘法。当然，如果数个移位和加减法指令比一个乘法指令更耗时，那就用乘法指令。

一个整数乘以$2^k$等价于左移k位（$k\ge 0$）。

练习1

LEA指令能够执行如(a << k) + b这样的运算。考虑b = 0或者b = a、k为任意可能的值，一条LEA指令可以计算a的哪些倍数？
当b = 0时，一条LEA指令可以计算a的$2^0,2^1,2^2,2^3,...$倍。
当b = a时，一条LEA指令可以计算a的$2^0+1,2^1+1,2^2+1,2^3+1,...$倍。

练习2

填写下表。

$k$	移位	加法/减法	表达式
6	2	1	$(x<<3)-(x<<1)$
31	1	1	$(x<<5)-x$
-6	2	1	$(x<<1)-(x<<3)$
55	2	2	$(x<<6)-x-(x<<3)$

除以2的幂

在大多数机器上，整数除法比整数乘法还慢。
除以2的幂可以用右移实现，无符号数使用逻辑右移，有符号数使用算术右移。

对于任何实数$\alpha$，定义$\lceil \alpha \rceil$为唯一的整数${\alpha }^{\prime }$，使得${\alpha }^{\prime }-1<\alpha \le {\alpha }^{\prime }$。
对于任何实数$\alpha$，定义$\lfloor \alpha \rfloor$为唯一的整数${\alpha }^{\prime }$，使得${\alpha }^{\prime }\le \alpha <{\alpha }^{\prime }+1$。
对于$x\ge 0,y>0$，$x$除以$y$的结果是$\lfloor x/y\rfloor$；对于$x<0,y>0$或$x>0,y<0$，$x$除以$y$的结果是$\lceil x/y\rceil$。即向零取整。

计算机执行除法运算时，不论结果正负，都是向下取整。
如果要向上取整，需要给被除数加上偏置量（除数-1）。
$$\begin{array}{r}\lceil x/y\rceil =\lfloor (x+y-1)/y\rfloor \end{array}$$

C表达式(x < 0 ? x + (1 << k) - 1 : x) >> k将会计算$x/2^k$。

同乘法不同，我们不能用右移和加减运算的组合表示除以任意常数。（乘法满足分配律，但除法不）。

练习1

写一个函数div16，返回x/16的结果。

int div16(int x)
{int sign = x >> 31;  // 符号位填满intint k = 4;int bias = (1 << k) - 1;return (x + sign & bias) >> k;
}

练习2

下面的代码中，省略了M和N的定义。

int arith(int x, int y)
{return x * M + y / N;
}

编译器优化后：

int arith(int x, int y)
{int t = x;x <<= 5;x -= t;if (y < 0) {y += 7;}y >>= 3;return x + y;
}

M和N的值是多少？
M = 31, N = 8。

关于整数运算的最后思考

计算机执行的“整数”运算实际上是一种模运算，因为整型的有限字长限制了可能的取值范围，运算结果可能溢出。
无符号数与补码数在运算时，拥有相同的位级行为，区别在于编译器解释位的方式。

练习

int x = foo();
int y = bar();
unsigned ux = x;
unsigned uy = y;

对于下面的C表达式，
1）证明对于所有的x和y，结果都为1。
2）给出使他们为0的x和y。

1. $(x>0)||(x-1<0)$
   当x = TMin时，结果为0。
2. (x & 7) != 7 || (x << 29 < 0)
   x的低3位不都是1时，结果是1。
   x的低3位都是1时，结果是1。
3. $(x\ast x)>=0$
   运算可能会溢出，当x = 123456时，x * x的低32位是1000 1100 0111 0101 0001 0000 0000 0000，符号位是1，是负数。
4. $x<0||-x<=0$
   如果x是非负数，-x一定是非正的。
5. $x>0||-x>=0$
   如果x = TMin，-x还是TMin，都是负数。
6. $x+y==uy+yx$
   结果是1。无符号数与补码数有相同的位级行为，且可交换。
7. x * ~y + uy * ux == -x
   结果是1。
   补码表示中，-y = ~ y + 1，因此~ y = -y - 1。
   x * ~y + uy * ux = x * (-y - 1) + uy * ux = -xy - x + uy * ux = -x。