无符号加法

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

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

我们定义操作+wu+^u_w+wu​是w位的无符号加法。
原理：无符号数加法。
对满足0≤x,y<2w0 \\le x,y<2^w0≤x,y<2w的$x$和$y$，有：
x+wuy={x+y,0≤x+y≤2w−1x+y−2w,2w≤x+y≤2w+1−2\\begin{align} x+^u_wy= \\begin{cases} x+y,\\quad &0 \\le x+y \\le 2^w -1 \\\\ x + y-2^w, \\quad &2^w \\le x+y \\le 2^{w+1}-2 \\end{cases} \\end{align} x+wu​y={x+y,x+y−2w,​0≤x+y≤2w−12w≤x+y≤2w+1−2​​​

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

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

原理：检测无符号加法中的溢出。
对满足0≤x,y≤2w−10 \\le x,y \\le 2^w-10≤x,y≤2w−1的x和y，存在s=˙x+wuys\\.=x+^u_wys=˙x+wu​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−2ws=x+y-2^ws=x+y−2w，因为y<2wy<2^wy<2w，因此y−2w<0y-2^w<0y−2w<0，因此$s<x$。
   运算发生溢出时，s=y+x−2ws=y+x-2^ws=y+x−2w，因为x<2wx<2^wx<2w，因此x−2w<0x-2^w<0x−2w<0，因此$s<y$。

对任何一个数$x$而言，存在$-x$使得$-x+x=0$，则称$-x$是$x$的加法逆元，$x$也是$-x$的加法逆元。加法逆元即取反。
原理：无符号数取反。
对满足0≤x≤2w−10 \\le x \\le 2^w-10≤x≤2w−1的x，其w位的无符号加法逆元−wu-^u_w−wu​可表示为：
−wux={x,x=02w−x,x>0\\begin{align} -^u_wx= \\begin{cases} x,\\quad &x=0\\\\ 2^w-x,\\quad &x>0 \\end{cases} \\end{align} −wu​x={x,2w−x,​x=0x>0​​​

练习1

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

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

练习2

给出下表中数的无符号加法逆元 −4u-^u_4−4u​ 的位表示。

补码加法

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

我们使用操作+wt+^t_w+wt​表示w位的补码加法。
原理：补码加法。
对满足−2w−1≤x,y≤2w−1−1-2^{w-1} \\le x,y \\le 2^{w-1}-1−2w−1≤x,y≤2w−1−1的$x$和$y$，有：
x+wty={x+y+2w,x+y<−2w−1负溢出x+y,−2w−1≤x+y≤2w−1−1正常x+y−2w,x+y≥2w−1正溢出\\begin{align} x+^t_wy= \\begin{cases} x+y+2^w, \\quad &x+y < -2^{w-1} \\quad &负溢出\\\\ x+y, \\quad &-2^{w-1} \\le x+y \\le 2^{w-1}-1 \\quad &正常 \\\\ x+y-2^w,\\quad &x+y \\ge 2^{w-1} &正溢出 \\end{cases} \\end{align} x+wt​y=⎩⎨⎧​x+y+2w,x+y,x+y−2w,​x+y<−2w−1−2w−1≤x+y≤2w−1−1x+y≥2w−1​负溢出正常正溢出​​​

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

原理：检测补码加法中的溢出。
对满足−2w−1≤x,y≤2w−1−1-2^{w-1} \\le x,y \\le 2^{w-1}-1−2w−1≤x,y≤2w−1−1的x和y，存在s=˙x+ys\\.=x+ys=˙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−2ws=x+y-2^ws=x+y−2w，且2w−1≤x+y≤2w−22^{w-1}\\le x+y \\le 2^{w}-22w−1≤x+y≤2w−2，因此$x>0$，$y>0$，且2w−1−2w≤s≤2w−2−2w2^{w-1}-2^w \\le s \\le 2^{w}-2-2^w2w−1−2w≤s≤2w−2−2w，即−2w−1≤s≤−2≤0-2^{w-1} \\le s \\le -2 \\le 0−2w−1≤s≤−2≤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+2ws=x+y+2^ws=x+y+2w，且−2w≤x+y<−2w−1-2^{w}\\le x+y < -2^{w-1}−2w≤x+y<−2w−1，因此$x<0$，$y<0$，且−2w+2w≤s≤−2w−1+2w-2^{w}+2^w \\le s \\le -2^{w-1}+2^w−2w+2w≤s≤−2w−1+2w，即0≤s≤2w−10 \\le s \\le 2^{w-1}0≤s≤2w−1，即$s\ge 0$。

练习1

填写下表

练习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);
}

补码的非

取非就是求加法逆元。
对满足TMinw≤x≤TMaxwTMin_w \\le x \\le TMax_wTMinw​≤x≤TMaxw​的x，其补码的非−wtx-^t_wx−wt​x表示为：
−wtx={TMinw,x=TMinw−x,TMinw<x≤TMaxw\\begin{align} -^t_wx= \\begin{cases} TMin_w, \\quad &x=TMin_w \\\\ -x, \\quad &TMin_w < x \\le TMax_w \\end{cases} \\end{align} −wt​x={TMinw​,−x,​x=TMinw​TMinw​<x≤TMaxw​​​​

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

练习

填写下表。

无符号乘法

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

对满足0≤x,y≤2w−10 \\le x,y \\le 2^w-10≤x,y≤2w−1的x和y，有：
x∗wuy=˙(x∗y)mod2w\\begin{align} x *^u_w y\\.=(x * y) mod 2^w \\end{align} x∗wu​y=˙(x∗y)mod2w​​

补码乘法

对满足−2w−1≤x,y≤2w−1−1-2^{w-1} \\le x,y \\le 2^{w-1}-1−2w−1≤x,y≤2w−1−1的x和y，有：
x∗wty=˙U2Tw((x∗y)mod2w)\\begin{align} x *^t_w y\\.=U2T_w((x * y) mod 2^w) \\end{align} x∗wt​y=˙U2Tw​((x∗y)mod2w)​​

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

练习1

填写下表，位宽w=3。

计算二进制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∗y=p+t2wx*y=p+t2^wx∗y=p+t2w，其中$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∗q=p+t2wx*q=p+t2^wx∗q=p+t2w，因此x∗q+r=p+t2w+rx*q+r=p+t2^w+rx∗q+r=p+t2w+r，因此p=p+t2w+rp=p+t2^w+rp=p+t2w+r，因此0=0+t2w+r0=0+t2^w+r0=0+t2w+r，所以r = t = 0。
   r = t = 0时，x∗y=x∗q+t2wx*y=x*q+t2^wx∗y=x∗q+t2w，因此y=q+t2wxy=q+\\frac {t2^w}{x}y=q+xt2w​，因此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;  // 截断前后的值是不是一样
}

乘以常数

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

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

练习1

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

练习2

填写下表。

除以2的幂

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

对于任何实数$\alpha$，定义$\lceil \alpha \rceil$为唯一的整数α′\\alpha'α′，使得α′−1<α≤α′\\alpha'-1 < \\alpha \\le \\alpha'α′−1<α≤α′。
对于任何实数$\alpha$，定义$\lfloor \alpha \rfloor$为唯一的整数α′\\alpha'α′，使得α′≤α<α′+1\\alpha' \\le \\alpha <\\alpha'+1α′≤α<α′+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）。
⌈x/y⌉=⌊(x+y−1)/y⌋\\begin{align} \\lceil x/y \\rceil=\\lfloor (x+y-1)/y \\rfloor \\end{align} ⌈x/y⌉=⌊(x+y−1)/y⌋​​

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

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

练习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。