CSAPP 2.3 整数的运算 | Blog

ヾ(≧O≦)〃ao~ welcome to my website

0%

CSAPP 2.3 整数的运算

2.3 整数的运算

2.3.1 无符号整数的加法

假设有两个w位的无符号整数x与y,当我们计算它们的和时,会发现如下两种情况。

  1. 0 <= x+y <= 2^w^-1

    这时我们可以直接用一个唯一的w位二进制数来表示x+y的值。

  2. x+y > 2^w^-1

    这种情况称为”溢出“(overflow)。大部分编程语言,包括C语言,仅仅支持固定位数的运算,也就是说两个w位的整数相加,其结果必定是w位的整数,不可能会产生w+1位的整数。二进制的溢出仅仅会溢出一位。

    两个w位的整数相加从算术上看至多会产生w+1位整数。当产生”溢出“时,计算机会抛弃运算结果的最高位,即第w+1位,留下其余w位作为运算结果。

    例如 考虑以下4位无符号整数运算

    x = [1001] y = [1100]

    从算术结果上来看, sum(x, y) = [10101], 但是计算机不支持在溢出时进位,所以运算结果需要砍掉最高位的1。计算机的实际运算结果 x+y = [0101]。

综上所述,w位无符号整数的加法运算结果实际上就是 实际运算结果 mod 2^w^。

在执行C语言过程中,”溢出“并不会报错。

这就需要开发者去留心,去警惕可能会发生的溢出现象。

当然也可以用专门的函数去检测”溢出现象“

1
2
3
4
5
6
/* Determine whether arguments can be added without overflow*/
int uadd_ok(unsigned x, unsigned y){
int sum = x+y;
return sum > x;
}
// 当发生溢出时,函数就会返回0, 不发生溢出时返回1

2.3.2 有符号整数(补码)的加法

对于w位有符号整数的加法,就要更复杂一些了。当两者的和小于-2^w-1^,或者大于2^w-1^-1时,就会发生溢出现象。

但即使更加复杂,有符号整数的加法遵循的原则与无符号整数无异,仍然时去掉溢出的最高位。不同点是有符号整数的加法的剩余位数必须视作补码

  1. x+y < -2^w-1^

    此时会发生”负溢出“(negative overflow)。计算机会自动抛弃运算产生的最高位,留下其余w位作为运算结果

    eg1 当w=4, x = [1000], y = [1011], 从算术结果上来看,sum(x, y) = [10011], 抛弃最高位后,计算机的实际运算结果 x+y = [0011] = (3)10

  2. -2^w-1^ <= x+y <= 2^w-1^-1

    此时计算机不发生溢出现象。计算机得到的实际结果等于算术结果。

    eg2 当w=4, x =1000, y = 0101, 算术结果和计算机的实际运行结果都为sum(x+y) = [1101] = (-3)10

  3. x+y > 2^w-1^-1

    此时会发生”正溢出“(positive overflow)。计算机会自动抛弃运算产生的最高位,留下其余w位作为运算结果

    eg1 当w=4, x = [0101], y = [0101], 从算术结果上来看,sum(x, y) = [1010]..计算机的实际运算结果也是 x+y= [1010] = (-6)10

那我们如何检查和分辨出正溢出和负溢出呢?规律如下

  1. 当 x > 0, y > 0, 且计算机的实际运算结果 x+y 小于零时,就说明发生了正溢出现象。
  2. 当 x < 0, y < 0, 且计算机的实际运算结果 x+y 大于零时, 就说明发生了负溢出现象。

我们可以用以下代码来检验溢出(int 类型有符号整数)。

1
2
3
4
5
6
7
/* Determine whether arguments can be added without overflow*/
int tadd_ok(int x, int y){
int sum = x+y;
int neg_over = x < 0 && y < 0 && sum >= 0;
int pos_over = x >= 0 && y >= 0 && sum < 0;
return !neg_over && !pos_over;
}

2.3.3 补码的非

求有符号正数的相反数

第一种方法:

我们知道了一个有符号整数的二进制表示,求出该整数的相反数的二进制表示只需要下列两步

  1. 将二进制的所有位取反。

  2. 将1.得到的结果的最后一位再加1.

eg1. (5)10 = (0101)2, 将二进制所有位取反后得到(1010)2, 最后一位加1得到 (1011)2, 按照补码的运算, (1011)2 = (5)10

第二种方法:

找出二进制表示中最右边的1,该1的位置左侧取反,右侧不变。

eg2. (5)10 = (0101)2, 最右边的1已经用粗斜体表示,按照规则转化为 (1011)2。按照补码的运算, (1011)2 = (5)10

对于一个w位整数x,x的非(在算术中称为相反数)的规律如下 TMin指x所能表示的最小值。
$$
-x = \begin{cases}
TMin & \text{ if } x= TMin \
-x & \text{ if } x> TMin
\end{cases}
$$

解释以下唯一的例外,以4位二进制为例, TMin = (1000)2, 所有位取反得到(0111)2, 最后一位加1后得到 (1000)2, 正好是本身。这是表达式中唯一的例外。

2.3.4 无符号数乘法

w位无符号整数的范围为 0 ~ 2^w^-1, 两个w位整数相乘,范围为 0 ~(2^w^-1)^2^, 至少需要2w位才能完成表示。但C语言中仍然用w位表示二者乘积,即抛弃前w位,只留下后w的数据, 在公式中结果用$x * _{u}^{w}\textrm{y}$表示。则
$$
x * _{w}^{u}\textrm{y} = (x \cdot y ) mod 2^{w}
$$

2.3.5 有符号数乘法

与无符号数乘法规则基本相同。

唯一的不同点是,最后的结果是用补码表示的。我们用$x * _{t}^{w}\textrm{y}$代表C语言中的乘积值。则
$$
x * _{w}^{t}\textrm{y} = (x \cdot y ) mod 2^{w}
$$

IMG_1097(20201005-104026)

下面用一个程序来检验乘法运算时的溢出

1
2
3
4
5
6
/* Determine whether arguments can be multiplied without overflow */
int tmult_ok(int x, int y){
int p = x*y;
/* Either x is zero, or dividing p by x gives y */
return !x || p/x == y;
}

2.3.6 常数的乘除法

计算机中乘法的运算速度相对于加减法,位运算,移位运算来说时比较慢的。因此,我们可以考虑用较快的位运算,移位等操作来代替缓慢的乘法。

用移位实现“乘以2的幂“

  • 无论有符号数还是无符号数
    • u<< k 可得到 u * 2^k^

如果运算结果溢出,那么遵守和前面乘法一样的规则,去掉溢出的高位,保留原本的位数。

c编译器会通过移位,加法和减法的组合来消除许多整数与常数相乘的情况。

例如 表达式 x*14, 因为 14 = 2^3^ + 2^2^ + 2^1^, 所以编译器将这个乘法运算转变为

(x<<3) + (x<<2) + (x<<1)注意,移位运算与加减法在一个表达式中时一定要加括号!),即将一次乘法运算转变为3个移位运算和两个加法运算。

用移位实现”除以2的幂“

在机器中除法的运算比乘法更慢。

  • 整数“除以2的幂”的商

    • u >> k 得到 小于等于(u / 2^k^ )的最大整数

    • 无符号整数使用逻辑右移,有符号整数使用算术右移。

    • 右移会产生二进制小数,在机器运算最后的结果中被去掉。

具体如图所示(以无符号整数为例子)

image-20201005185835285

从中我们可以看出,在C语言中整数与整数做除法得到的一定还是个整数,而且得到的整数是小于等于(u / 2 ^k^ )的最大整数。

此外,还可以通过特殊的运算得到 大于等于(u/2^k^)的最小整数。具体见CSAPP英文版p141.

1
return x>>4

2.3.8 总结

算术运算基本规则

加法:

  • 无/有符号数的加法:正常加法后再截断,位级的运算相同

乘法:

  • 无/有符号数的乘法: 正常乘法后加截断操作,位级运算相同

使用无符号整数时的常见错误

  • 忽略有符号数隐式转换(casting)到无符号数。

  • 无符号数在运算过程中在数学算术上会产生负数结果,在计算机中转换为正数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    /* WARNING: This is buggy code */
    float sum_elements(float a[], unsigned length){
    int i;
    float result = 0;

    for (i = 0; i<= length-1; i++) // bug句需纠正
    result += a[i];
    return result;
    }

    注意,当length=0时, 第一次判断条件中length-1算术结果为-1,但是无符号整数的运算规则可知,实际产生结果将是一个相当大的正数。

    纠正

    1
    for(i=0; i < length; i++)
  • 不知道一些函数方法默认返回无符号整数,采用有符号整数的算法

    1
    2
    3
    4
    5
    /* Determine whether string s is longer than string t*/
    /* a buggy function */
    int strlonger(char *s, char *t){
    return strlen(s) - strlen(t) > 0; // 待修改代码
    }

    注意strlen函数的返回值是无符号整数。无符号整数的减法得到的仍然是无符号整数!除非s数组与t数组长度相同,否则该函数输出均为1.

    纠正

    1
    return strlen(s) > strlen(t)
坚持原创分享,您的支持将鼓励我继续创作!