CSAPP 2.3 整数的运算

发表于 分类于 ， 本文字数： 2.3k 阅读时长 ≈ 8 分钟

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)