- 文章
- 整数溢出
2012年6月9日（最后更新：2014年6月9日）
整数溢出
评分：3.8/5 (448 票)
溢出是一种现象，即对两个数字的操作超过了数据类型可以拥有的最大值（或低于最小值）。通常认为整数类型非常大，人们没有考虑到两个数字的和可能大于该范围。但在科学和数学计算中，这可能会发生。例如，发动机转向软件中未处理的算术溢出是阿丽亚娜 5 火箭首次飞行坠毁的主要原因。该软件一直被认为是无错误的，因为它已在之前的多次飞行中使用过；但那些飞行使用的是较小的火箭，产生的加速度小于阿丽亚娜 5 火箭。本文将介绍如何解决这个问题。
在本文中，我们只处理整数类型（而不处理像 float 和 double 这样的类型）
为了理解如何解决这个问题，我们将首先了解数字是如何存储的。
如果数据类型的大小为 n 字节，则它可以存储 28n 个不同的值。这被称为数据类型的范围。
如果无符号数据类型的大小为 n 字节，则范围为 0 到 28n-1
如果带符号数据类型的大小为 n 字节，则范围为 -28n-1 到 28n-1-1
因此，short（通常为 2 字节）的范围为 -32768 到 32767，而 unsigned short 的范围为 0 到 65535
考虑一个值为 250 的 short 变量。
它在计算机中以如下方式存储（以二进制格式）
00000000 11111010
一个数的补码是该数的位翻转后的数。它用 ~ 表示
例如，~250 是 11111111 00000101
负数使用 2 的补码系统存储。根据该系统，-n=~n+1
-250 存储为 11111111 00000110
http://stackoverflow.com/questions/1049722/what-is-2s-complement
10000000 00000000 (-32768) 没有正数对应项。它的负数是它本身（尝试 -n=~n+1）
如果数据类型是 unsigned，11100010 01110101 将被读取为 57973，而如果数据类型是 signed，则将被读取为 -7563。如果将 65536（范围）添加到 -7563，您将得到 57973。
溢出
考虑一个数据类型 var_t，大小为 1 字节（范围为 256）
signed var_t a,b;
unsigned var_t c,d;
如果 c 为 200(11001000)，d 为 100(01100100)，则 c+d 为 300(00000001 00101100)，这大于最大值 255(11111111)。 00000001 00101100 大于一个字节，因此高位字节将被拒绝，c+d 将被读取为 44。所以，200+100=44！这很荒谬！（注意 44=300-256）。这是一个无符号溢出的例子，其中该值无法存储在可用的字节数中。在这种溢出中，结果会模范围（这里是 256）。
如果 a 为 100(01100100)，b 为 50(00110010)，则 a+b 为 150(10010110)，这大于最大值 127。相反，a+b 将被读取为 -106（注意 -106=150-256）。这是一个有符号溢出的例子，其中结果会模范围（这里是 256）。
除法和取模永远不会产生溢出。
加法溢出
只有在被加的数字的符号相同时才会发生溢出（无符号数始终是这种情况）
可以通过查看其符号与操作数的符号相反来轻松检测有符号溢出。
让我们分析一下无符号整数加法中的溢出。
考虑一个数据类型的两个变量 a 和 b，大小为 n，范围为 R。
设 + 是实际的数学加法，a$b 是计算机进行的加法。
如果 a+b<=R-1, a$b=a+b
由于 a 和 b 是无符号的，a$b 大于或等于 a 和 b。
如果 a+b>=R a$b=a+b-R
由于 R 大于 a 和 b，a-R 和 b-R 为负数
所以，a+b-R<a 和 a+b-R<b
因此，a$b 小于 a 和 b。
这种差异可用于检测无符号加法溢出。 a-b 可以被视为 a+(-b)，因此可以以相同的方式处理减法。
乘法溢出：有两种方法可以检测溢出
1. 如果 a*b>max，则 a>max/b（如果 unsigned，max 为 R-1，如果 signed，max 为 R/2-1）。
2. 假设存在一个大小为 n 且范围为 R 的数据类型，称为 var_t，以及一个大小为 2n 的数据类型，称为 var2_t。
假设有两个 var_t 变量 a 和 b。 var2_t 的范围将是 R*R，它总是大于 a 和 b 的乘积。因此，如果 var2_t(a)*var2_t(b)>R，则发生了溢出。
截断：当从较长的变量分配给较短的变量时，会发生这种情况。例如，
如果将 int 替换为 unsigned short，也会显示类似的行为。
类型转换： 考虑
每当在相同类型的无符号变量和有符号变量之间执行操作时，操作数都会转换为无符号类型。
每当在 long 类型和 short 类型之间执行操作时，操作数都会转换为 long 类型。
上面的代码返回 1，因为 a 和 b 被转换为 unsigned int，然后进行比较。
如果我们使用 __int64（一个 64 位类型）而不是 unsigned int，并使用 18446744073709551610 而不是 4294967290，结果将会相同。
类型提升： 每当对类型短于 int 的两个变量执行操作时，这两个变量的类型都会转换为 int。 例如。
在本文中，我们只处理整数类型（而不处理像 float 和 double 这样的类型）
为了理解如何解决这个问题，我们将首先了解数字是如何存储的。
关于整数
如果数据类型的大小为 n 字节，则它可以存储 28n 个不同的值。这被称为数据类型的范围。
如果无符号数据类型的大小为 n 字节，则范围为 0 到 28n-1
如果带符号数据类型的大小为 n 字节，则范围为 -28n-1 到 28n-1-1
因此，short（通常为 2 字节）的范围为 -32768 到 32767，而 unsigned short 的范围为 0 到 65535
考虑一个值为 250 的 short 变量。
它在计算机中以如下方式存储（以二进制格式）
00000000 11111010
一个数的补码是该数的位翻转后的数。它用 ~ 表示
例如，~250 是 11111111 00000101
负数使用 2 的补码系统存储。根据该系统，-n=~n+1
-250 存储为 11111111 00000110
http://stackoverflow.com/questions/1049722/what-is-2s-complement
10000000 00000000 (-32768) 没有正数对应项。它的负数是它本身（尝试 -n=~n+1）
如果数据类型是 unsigned，11100010 01110101 将被读取为 57973，而如果数据类型是 signed，则将被读取为 -7563。如果将 65536（范围）添加到 -7563，您将得到 57973。
溢出
考虑一个数据类型 var_t，大小为 1 字节（范围为 256）
signed var_t a,b;
unsigned var_t c,d;
如果 c 为 200(11001000)，d 为 100(01100100)，则 c+d 为 300(00000001 00101100)，这大于最大值 255(11111111)。 00000001 00101100 大于一个字节，因此高位字节将被拒绝，c+d 将被读取为 44。所以，200+100=44！这很荒谬！（注意 44=300-256）。这是一个无符号溢出的例子，其中该值无法存储在可用的字节数中。在这种溢出中，结果会模范围（这里是 256）。
如果 a 为 100(01100100)，b 为 50(00110010)，则 a+b 为 150(10010110)，这大于最大值 127。相反，a+b 将被读取为 -106（注意 -106=150-256）。这是一个有符号溢出的例子，其中结果会模范围（这里是 256）。
检测溢出
除法和取模永远不会产生溢出。
加法溢出
只有在被加的数字的符号相同时才会发生溢出（无符号数始终是这种情况）
可以通过查看其符号与操作数的符号相反来轻松检测有符号溢出。
让我们分析一下无符号整数加法中的溢出。
考虑一个数据类型的两个变量 a 和 b，大小为 n，范围为 R。
设 + 是实际的数学加法，a$b 是计算机进行的加法。
如果 a+b<=R-1, a$b=a+b
由于 a 和 b 是无符号的，a$b 大于或等于 a 和 b。
如果 a+b>=R a$b=a+b-R
由于 R 大于 a 和 b，a-R 和 b-R 为负数
所以，a+b-R<a 和 a+b-R<b
因此，a$b 小于 a 和 b。
这种差异可用于检测无符号加法溢出。 a-b 可以被视为 a+(-b)，因此可以以相同的方式处理减法。
乘法溢出：有两种方法可以检测溢出
1. 如果 a*b>max，则 a>max/b（如果 unsigned，max 为 R-1，如果 signed，max 为 R/2-1）。
2. 假设存在一个大小为 n 且范围为 R 的数据类型，称为 var_t，以及一个大小为 2n 的数据类型，称为 var2_t。
假设有两个 var_t 变量 a 和 b。 var2_t 的范围将是 R*R，它总是大于 a 和 b 的乘积。因此，如果 var2_t(a)*var2_t(b)>R，则发生了溢出。
截断：当从较长的变量分配给较短的变量时，会发生这种情况。例如，
short a;long b=70000;a=b; 只复制低位，并且值的含义被转换。short a;int b=57973;a=b; 也会显示此行为，变为 -7563。如果将 int 替换为 unsigned short，也会显示类似的行为。
类型转换： 考虑
unsigned int a=4294967290;int b=-6; return (a==b); 这返回 1。每当在相同类型的无符号变量和有符号变量之间执行操作时，操作数都会转换为无符号类型。
每当在 long 类型和 short 类型之间执行操作时，操作数都会转换为 long 类型。
上面的代码返回 1，因为 a 和 b 被转换为 unsigned int，然后进行比较。
如果我们使用 __int64（一个 64 位类型）而不是 unsigned int，并使用 18446744073709551610 而不是 4294967290，结果将会相同。
类型提升： 每当对类型短于 int 的两个变量执行操作时，这两个变量的类型都会转换为 int。 例如。
short a=32000,b=32000;cout<<a+b<<endl; 将显示 64000，这大于 short 的最大值。 原因是 a 和 b 被转换为 int，a+b 将返回一个 int，它可以具有 64000 的值。