整数运算溢出

最近在书上看到有在说数据溢出的问题，受益匪浅。想想自己虽然曾经上过计组等一些类似课程，对这些理论知识都是学过的，但从来在实际写代码中都是默认忽略，没有认真考虑过这些问题。我们在写代码过程中很容易写出下列代码：

//int b, c;
int sum = b + c;
int mul = b * c;

假设int在32位机器上是4个字节长，也就是32位。那么两个int相加可能会产生33位数据，也就是32位的int型变量sum不足以保存这个结果，对于乘法来说更不用提了。而我们实际中确实很“放心”的写出这些表达式，并默认它们是正确的，这可能会带来意想不到的后果，因为C/C++标准里并不会将数据溢出抛出异常，这也意味着你什么提示信息也看不到，程序还是照样往下执行。

1. 无符号数加法溢出

我们就以4位数来做了示例，4位数能够表示的无符号数的范围是0000b ~ 1111b，即[0, 15]。我们在做8 + 8运算时，1000b + 1000b = (1)0000b，数据溢出，实际结果为0。

我们可能更想关注的是如何判断数据产生溢出。假设数a、b是4位二进制表示，a、b的范围是0~15，那么sum = a+b的范围应该是0~30，超过15就需要5位数来编码了，也就是可能会产生溢出。溢出的部分会被直接截断的，所以该如何判断溢出呢。可以这么想，因为a、b都是无符号数，依据它们的范围，如果sum没有溢出，那么就能推导出sum >= a。逆否的思想：如果sum < a，推导出 sum溢出。这对于b是等价的。所以我们就得到，当和小于两个加数时，无符号加法产生溢出。你也许可以写出这样的代码来判断无符号int加法是否溢出：

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

当然你也可以用一个更长位数的类型来保存结果，然后进行比较，这样也是可以的。

2. 补码加法溢出

有符号数在计算机中是以补码形式存储。其实，计算机根本不知道存的是补码还是原码，只知道存的是一串二进制数，具体是补码还是原码，看你代码中的声明，然后编译器根据你的声明去按照补码规则还是原则规则去解释这串二进制数。比如，计算机某个内存单元存的是1111，如果是按原码去解释，就是十进制的15，如果按照补码去解释，就是十进制的-1。而实际上，大多数计算机使用同样的指令来执行无符号或有符号加法。我的理解是，反正存的只是二进制数，那就按照无符号加法规则加吧，把最后的结果按照有符号来解释，而实际也是正确的。举例来说：

x = 0010b
y = 1110b
x + y = (1)0000b

如果是无符号加，x是2，y是14，x + y = 16 mod 16 = 0，结果是正确的。如果是有符号加，x是2，y是-2，x + y = 16 mod 16 = 0也是正确的。

关于无符号数和有符号数还有一点就是，即使使用了强制转换，并不会改变内存中存的二进制数，只是改变解释这串二进制的方法。所以将一个无符号转换成有符号，数值可能会改变，但是二进制数并没有改变。反之亦然。

对于补码加法溢出，有两种情况，正溢出和负溢出。正溢出的条件是x>0 && y>0 && sum<=0；负溢出条件是x<0 && y<0 && sum>=0。所以可能写出这样的代码来判断有符号int加法是否溢出：

bool tadd_ok(int x, int y) {
    int sum = x + y;
    int no = x < 0 && y < 0 && sum >= 0;
    int po = x > 0 && y > 0 && sum <= 0;
    return !(no || po);
}

3. 乘法

不管无符号位还是有符号位，都看成二进制在做乘法，最后的结果在依据不同类型做不同解释。两个w位的数的乘法结果可能会是2w位，所以前w位的数会被直接截断，只保留低w位作为结果。

在判断溢出时，可能的检测代码：

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

书上习题还有个拿更多位的类型来保存结果进行比较：

int tmul_ok(int x, int y) {
    int64_t pll = (int64_t) x*y;
    return pll = (int)pll;
}

书中说到int 64_t pll = (int64_t) x*y这行代码，等号右边的强制转换一定要存在，不然就会用32位值来计算乘积，可能会溢出，然后再扩展到64位。实际我测试了，两种写法都没有问题，不知道是不是现在的C标准改了，还是和我的具体机型有关。那就按照作者所说的方式，保证没有意外。

4. 其它

在写代码过程中，有很多地方还是需要用到当前类型的最大值和最小值的。C和C++各自标准里都有定义这些。C在头文件<limits.h>里定义了很多宏：CHAR_BIT、CHAR_MIN、CHAR_MAX、INT_MIN、INT_MAX等等。C++在头文件<limits>里定义了如std::numeric_limits<int>::min()等。