CSAPP3 2.3 整数运算

| 分类 Programming  CSAPP3  | 标签 Programming  《深入理解计算机系统》 

无符号数加法

w 位的两个无符号数相加,可能要用 w+1 个位来表示,此时会出现溢出。

对满足 $0 \leq x, y < 2^w$ 的 $x$ 和 $y$,有:

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

对在范围 $0 \leq x, y \leq UMax_w$ 中的 x 和 y,令 $s = x +_w^u y$,则当且仅当 s < x (或者等价地 s < y) 时,发生了溢出。即因为 x 和 y 都非负,故 $x + y \geq x$,因此如果 s 没有溢出,就能够肯定 $s \geq x$,另一方面,如果 s 确实溢出了,就有 $s = x+y-2^w$,而 $y < 2^w$,此时 $s < x$

练习题 2.27 p98

写出如下原型的函数,当参数 x 和 y 相加不会产生溢出时返回 1.

/* Determine whether arguments can be added without overflow */
int uadd_ok(unsigned x, unsigned y)
{
    unsigned s = x + y;
    return s >= x;
}
*/

无符号数的求反

对满足 $0 \leq x < 2^w$ 的任意 $x$,其 $w$ 位的无符号逆元 $-_w^ux$ 为:

也就对于非零的数,求反即为二进制时的取反 + 1 再截断。

练习题 2.28 p98

假设 w=4,填写下面无符号加法逆元的位表示。

$x$ hex $x$ dec $-_4^ux$ dec $-_4^ux$ hex
0 0 0 0
5(0101) 5 11 B
8(1000) 8 8 8
D(1101) 13 3 3
F(1111) 15 1 1

补码加法

两个补码有符号数相加后,结果太大(正溢出)和太小(负溢出)时都会溢出。

对满足 $-2^{w-1} \leq x, y \leq 2^{w-1} - 1$ 的整数 x,y,有:

补码加法溢出情况

实现上,补码加法和无符号数的加法在位模式上是一样的,用的是相同的机器指令,只是对结果的解析不同。因此,计算时,只需进行二进制加法再进行截断即可。

补码加法的溢出检测:

对满足 $TMin_w \leq x, y \leq TMax_w$ 的 x 和 y,令 $s=x +_w^t y$。当且仅当 $x>0, y>0$,但 $s \leq 0$ 时,发生正溢出。当且仅当 $x<0, y<0$,但 $s \geq 0$ 时发生负溢出。

练习题 2.29 102

w=5 时填写下表:

x | y | x+y | $x+_5^ty$ | 情况 ——–| [10100] | [10001] | [100101] | [00101] | 负溢出,情况 1 [11000] | [11000] | [110000] | [10000] | 负值,正常,情况 2 [10111] |[01000] | [11111] |[11111] |负值,正常,情况 2 [00010] | [00101] | [00111] | [00111] | 正值,正常,情况 3 [01100] | [00100] | [10000] | [10000] | 正溢出,情况 4

练习题 2.30 p101

/* Determine whether arguments can be added without overflow */
int tadd_ok(int x, int y)
{
    int s = x + y;
    if ((x>0 && y>0 && s<=0) || (x<0 && y<0 && s>=0))
        return 0;
    return 1;
}

/*or*/
int tadd_ok(int x, int y)
{
    int s = x + y;
    int neq_over = x<0 && y<0 && s>=0;
    int pos_over = x>0 && y>0 && s<=0;
    return !neg_over && !pos_over;
}

练习题 2.31 101

查找下面的补码相加溢出判断的实现函数的 BUG:

/* Determine whether arguments can be added without overflow */
/* WARRING: This code is buggy */
int tadd_ok(int x, int y)
{
    int sum = x+y;
    return (sum-x == y) && (sum-y ==x);
}

模数加法形成了阿贝尔群(Abelian Group),因此代码中的判断,无论溢出与否,都是成立的,都返回 1;

练习题 2.32 p101

假设要写函数 tsub_ok,如果计算 x-y 不产生溢出,返回 1。

/* Determine whether arguments can be subtracted without overflow */
/* WARNNING: This code is buggy. */
int tsub_ok(int x, int y){
    return tadd_ok(x, -y);
}

x 和 y 取什么值是,会产生错误的结果?

当 $y=TMin=-2^{w-1}$ 时,$-y=y$,此时对于 tadd_ok(x, -y) 来说,当 x 为负时都认为溢出,返回 0,而 x 为非负时,都认为没有溢出返回 1。而情况恰恰相反,tsub_ok(x, TMin),当 x 为 负数时,应认为没有溢出,返回 1,而 x 为非负时,应认为溢出返回 0.

补码的非

因 $TMin_w + TMin_w = -2^{w-1} + (-2^{w-1}) = -2^w$,溢出后的结果为 0,故:

对满足 $TMin_w \leq TMax_w$ 的 x,其补码的非 $-_w^tx$ 为:

练习题 2.33 p102

w=4 时,补全下表中补码的加法逆元。

x(hex) x(dec) -x(dec) -x(hex)
0(0000) 0 0 0
5(0101) 5 -5 B
8(1000) -8 8 8
D(1101) -3 3 3
F(1111) -1 1 1

结合题 2.28,补码和无符号数的逆元(非、取反)产生的位模式是相同的,都是位模式取反+1,即对于任意整数 x,-x 和 ~x+1 的结果都是相同的。

如上面的方法类似,计算补码非的第二种方法是建立在向量分为两部分的基础上。假设 $k$ 是最右边的 1 的位置,因而 $x$ 的位级表示形如 $[x_{w-1}, x_{w-2},\cdots,x_{k+1},1,0,\cdots,0]$(只要 $x \neq 0$ 就能找到这样的 $k$),这个值的非写成二进制就是$[\neg x_{w-1}, \neg x_{w-2},\cdots,\neg x_{k+1},1,0,\cdots,0]$。

无符号数乘法

范围 $0 \leq x, y \leq 2^w -1$ 内的整数 x 和 y,乘积 $x\bullet y$ 的取值范围为 0 到 $(2^w-1)^2$,可能需要 2w 位来表示。但最终结果需要截断,故:

对满足 $0 \leq x, y \leq UMax_w$ 的 x 和 y 有:

补码乘法

补码乘法和无符号数乘法,由于结果存在截断的情况,它们的截断后的结果在位级上都是相同的,因此用的相同的机器指令。因此可能理解为它们在位级操作上是相同的,只是解析不同。

练习题 2.34 p104

填写下面 3 位数字的乘法结果。

模式 x y x.y 截断的 x.y
无符号 4[100] 5[101] 20[10100] 4[100]
补码 -4[100] -3[101] 12[01100] -4[100]
无符号 2[010] 7[111] 14[1110] 6[110]
补码 2[010] -1[111] -2[110] -2[110]
无符号 6[110] 6[110] 36[100100] 4[100]
补码 -2[110] -2[110] 4[100] 4[100]

练习题 2.35 p104

下面是判断补码乘法是否溢出的代码:

/* Determine whether arguments can be multiplied without overflow */

int tmult_ok(int x, int y)
{
    int p = x*y;
    /* Either x is 0, or dividing p by x gives y */
    return !x || p/x == y;
}

见题 2.31,我们不能用减法来检验加法是否溢出,但这里可以用除法为检验乘法是否溢出。

按照下面的思路,用数学推导来证明你的方法是对的。首先,证明 $x=0$ 时显然是正确的。另外,考虑 $w$ 位数字 $x(x \neq 0), y, p, q$,这里 $p$ 是 $x$ 和 $y$ 补码乘法的结果,而 $q$ 是 $p$ 除以 $x$ 的结果。

1、 $x$ 和 $y$ 的乘积可写成:$x \bullet y = p + t2^w$,其中,$t \neq 0$ 当且仅当 $p$ 的计算溢出。

2、而 $p$ 也可以写成这样的形式: $p=x \bullet q + r$,其中 $ r < x $。

3、故 $x \bullet y = p + t2^w = x \bullet q + r + t2^w$,故当且仅当 $r=t=0$ 时有 $q=y$。 待推导

练习题 2.36 p105

对于数据类型 int 为 32 位的情况,设计一个版本的 tmul_ok 函数,使用 64 位的 int64_t, 而不使用除法。

int tmul_ok(int x, int y)
{
    /* Compute product without overflow */
    /* 这一行的强制类型转换至关重要。如果写成 int64_t p = x*y;
    就会用 32 位值来计算乘积(可能溢出),再符号扩展到 64 位*/
    int64_t p = (int64_t) x * y;
    
    /* See if casting to int preserves value */
    return (int)p == p;
}

练习题 2.37 p106

XDR 库代码中存在乘法溢出的漏洞:

int ele_cnt;
size_t ele_size;

void *result = malloc(ele_cnt * ele_size);

当 ele_cnt 为 $2^{20}+1$,ele_size 为 $2^{12}$ 时,相乘结果溢出后值为 $2^12=4096$,导致分配的空间不够,复制时会越界。

当数据类型 int 和 size_t 都是 32 位时,你决定将待分配字节数设置为数据类型 uint64_t,来消除乘法溢出的可能性。你把原来对 malloc 调用替换为:

uint64_t asize = ele_cnt * (uint64_t) ele_size;
void *result = malloc(asize); /* malloc 的参数类型为 size_t */

A. 这段代码对原始的代码有了哪些改进?

B. 你该如何修改代码来消除这个漏洞?

改进:保存了乘积的未截断结果,可进一步进行是否溢出判断。

消除漏洞:

uint64_t required_size = ele_cnt * (uint64_t) ele_size;
size_t request_size = (size_t)required_size;
if (request_size != required_size) {
    /* Overflow must have occurred. Abort Operation */
    return NULL;
}
void *result = malloc(request_size);

乘以常数

移位和加减操作比乘法操作快的多,因此编译器常将乘法优化为移位和加减操作。

乘以 2 的幂

无论无符号数,还是补码,由于位级上的表示和操作相同,当乘以 $2^k$ 时,都是进行左移 $k$ 位操作(可能溢出)。

练习题 2.38 p107

LEA 指令能执行形如 (a<<k)+b 的计算,这里 k 等于 0, 1, 2, 或 3,而 b 等于 0 或某个程序值 。编译器常用该指令执行常数因子乘法。例如可用 (a<<1)+a 来计算 3*a

考虑 b 等于 0 或者 a,k为任意可能的值的情况,用一条 LEA 指令可以计算 a 的哪些倍数?

可计算出 $2^k$ (当 b 为 0)和 $2^k+1$ (当 了为 a)的值。

a 的倍数 LEA 指令
2a (a<<1)+0
3a (a<<1)+a
4a (a<<2)+0
5a (a<<2)+a
8a (a<<3)+0
9a (a<<3)+a

对于常数 K 的表达式 x * K 的生成代码,编译器会将 K 的二进制表示表达为一组 0 和 1 交替的序列:

例如,14 可写成 $[(0\cdots0)(111)(0)]$。考虑一组从位位置 $n$ 到位位置 $m$ 的连续的 1($n \geq m$)(对于 14 来说,有 $n=3,m=1$)。可以用下面两种不同形式中的一种来计算这些位对乘积的影响:

形式 A:(x<<n)+(x<<(n-1))+...+(x<<m)

形式 B:(x<<(n+1))-(x<<m)

这种优化只在需少量移位、加减法时才进行。

练习题 2.39 p107

对于位位置 n 为最高有效位的情况,要怎样修改形式 B 的表达式?

此时:x(<<n+1)) 溢出为 0,故结果为 -(x<<m)

练习题 2.40 p107

基于形式 A 和 B,填写 x*K 的优化表达式。

K 移位 加法/减法 表达式
6 2 1 (x<<2) + (x<<1) 即 4+2
31 1 1 (x<<5)-x 即 32-1
-6 2 1 (x<<1)-(x<<3) 即 2-8
55 2 2 (x<<6)-x(<<3)-x 即 64-8-1

练习题 2.41 p107

对于形式 A 和 B,编译器如何决定使用哪种?

选择操作次数少的形式。

首先当 $m > 0$ 时:当 $n=m$ 时,形式 A 只需 1 个移位,而形式 B 需 2 移位 1 减法,选 A;当 $n=m+1$ 时,A 和 B 都需要 2 移位 1 加减;当 $n>m+1$ 时,A 需要 $n-m+1>2$ 个移位和 $n-m>1$ 个加法,B 还是 2 移位 1 减法。对于 $m=0$ 时,形式 A 和 B 都会少 1 移位,还适用同样的选择原则。

除以 2 的幂

可以用移位来实现,无符号的用逻辑右移,补码的用算术右移。

规定整数除法总是舍入到 0,即舍入到最接近 0 的整数,即当实际值为正数 3.14 时,将向下舍入到 $\lfloor 3.14 \rfloor = 3$,而若实际值为负数 -3.14 时,将向上舍入到 $\lceil -3.14 \rceil=-3$。

无符号数除以 2 的幂,只需逻辑右移

k >>k(二进制) 十进制 $12340/2^k$
0 0011000000110100 12340 12340.0
1 0001100000011010 6170 6170.0
4 0000001100000011 711 771.25
8 0000000000110000 48 48.203125

上面是整数 12340 进行逻辑右移的值,可见无符号数除以 2 的幂,只需进行 $k$ 位的逻辑右移,其效果和除以 $2^k$ 再舍入到 0 是一样的。

补码数除以 2 的幂

补码 x 进行算术右移的结果总是向下舍入的。当 x 为非负数时,和上面的无符号数进行逻辑右移一样,舍入到 0(向下舍入)。但当 x 为负数时,以 -12340 为例:

k >>k(二进制) 十进制 $-12340/2^k$
0 1100111111001100 -12340 -12340.0
1 1110011111100110 -6170 -6170.0
4 1111110011111100 -712 -771.25
8 1111111111001111 -49 -48.203125

可见,当负数时,算术右移的结果总是向下舍入,与规定的舍入到 0 不符。

此时,可利用编置技术,在执行算术右移前,先加上适当的偏置量,再进行算术右移,从而使结果满足舍入到 0 的规定。

k 偏量 -12340+偏量 >>k(二进制) 十进制 $-12340/2^k$
0 0 1100111111001100 1100111111001100 -12340 -12340.0
1 1 1100111111001101 1110011111100110 -6170 -6170.0
4 15 1100111111011011 1111110011111101 -711 -771.25
8 255 1101000011001011 1111111111010000 -48 -48.203125

偏置技术利用了如下属性:对于整数 $x$ 和 $y(y>0)$,$\lceil x/y \rceil = \lfloor (x+y-1)/y \rfloor$。

当 $y=2^k$ 时,$x+y-1=x+2^k-1=x+(1«k)-1$,故补码 $x$ 的算术右移的表达式为 (x<0 ? x+(1<<k)-1 : x) >> k

练习题 2.42 p111

写一个函数 div16,对于整数参数 x 返回 x/16 的值。要求不能使用除法、模运算、乘法、条件语句 (if 和 ?:)、比较运算符、循环等。假设 int 为 32 位,补码,算术右移。

int div16(int x)
{
    /* (x + bias) >> k:
    对于 x 为正数时, bias 为 0
    对于 x 为负数时, bias = (1<<4)-1=15
    */
    int bias = (x>>31) & 0xF;
    return (x+bias) >> 4;
}

练习题 2.43 p111

下面的代码中,省略了常数 M 和 N 的定义:

#define M    /* Mystery number 1 */
#define N    /* Mystery number 2 */
int arith(int x, int y)
{
    int result = 0;
    result = x*M + y/N;
    return result;
}

用某个 M 和 N 的值编译上面代码后,编译器将优化乘除操作。下面是产生的机器码翻译回 C 的结果:

/* Translation of assembly code for arith */
int optarith(int x, int y)
{
    int t = x;
    x <<= 5;  
    x -= t;  /*  x = x*32 -x,使用了形式 B的优化:`(x<<(n+1))-(x<<m)`,
    这里 n=4, m=0, 从而 M = [1111] = 15 */
    if (y < 0) y += 7; /* y + (1<<3)-1 */
    y >>= 3; /* Arithmetic shift,从而 N  2  3 次方,即为 8
    return x+y;
}

M = 15, N=8

关于整数运算的最后思考

整数表示的有限字长限制了运算结果的取值范围,从而可能会溢出。无论是补码表示还是无符号数,它们的加减乘除操作,在位级上都完全一样或非常类似。

C 中的 unsigned 数据类型变量,在运算中会隐式地要求将其它参数先转换成 unsigned 数据类型再计算,从而会导致难以察觉的 BUG。

练习题 2.44 p112

假设有符号值使用补码、32 位、算术右移,无符号逻辑右移。变量的声明和初始化如下:

int x = foo(); /* Arbitrary value */
int y = bar(); /* Arbitrary value */

unsigned ux = x;
unsigned uy = y;

对于下面各 C 表达式, 1、证明对于所有的 x 和 y值,都为真,或者 2、给出使它不为真时的 x 和 y 值。

A. (x>0) || (x-1<0): x 为 0 时为真,为正数时为真,为 TMin = $-2^{31}` 时,$x-1=-2^{31}-1=2^{31}-1=TMax > 0$,此时不成立。

B. (x&7) != 7 || (x<<29 < 0): 左边要求最低 3 位有效位不能同时为 1,右边的要求最低的第 3 位为 1, 故例如当最低有效位为 011 时不成立。

C. (x*x) > =0:当 $x=2^{16}-1$ 时,$x*x = 2^{32} + 1 - 2^{17} = -2^{17} -1$,故不成立。

D. x<0 || -x <=0: 根据定义,

,故都成立。

E. x>0 || -x >=0: x=Tmin 时, -x=Tmin,此时不成立。

F. x+y == uy+ux:由于位级操作相同,只是解析不同,故都成立。

G. x*~y + uy*ux == -x: 因 -y = ~y+1,即 ~y=-y-1,同时,乘法的位级操作也相同,故 uyuy=yx,故 x~+uyux = x(-y-1)-yx = -x,故都成立。

参考


上一篇     下一篇