编译器在编译时如何检测数字溢出？

Question

编译器将源代码处理为字符串，因此在C++中，例如当它鼓励像 unsigned char x = 150; 这样的语句时，它知道从类型限制中 unsigned char 必须在 0 和 255 的范围内。

我的问题是，当数字 150 保持为字符串时，编译器使用什么算法来比较数字序列 - 在这种情况下是 150 - 与类型限制？

我为类型“int”的十进制、八进制、十六进制和小端二进制制作了一个简单的算法，但我不认为编译器会像这样做来检测数字溢出。

我编写的算法是用C++编写的：

typedef signed char int8;
typedef signed int  int32;

#define DEC  0
#define HEX  1
#define OCT  2
#define BIN  3

bool isOverflow(const char* value, int32 base)
{
    // left-most digit for maximum and minimum number
    static const char* max_numbers[4][2] =
    {
        //                 INT_MAX                           INT_MIN
        {                       "2147483647",                       "2147483648" }, // decimal
        {                         "7fffffff",                         "80000000" }, // hexadecimal
        {                      "17777777777",                      "20000000000" }, // octal
        { "01111111111111111111111111111111", "10000000000000000000000000000000" }  // binary
    };

    // size of strings in max_numbers array
    static const int32 number_sizes[] = { 10, 8, 11, 32 };

    // input string size
    int32 str_len = strlen(value);

    // is sign mark exist in input string
    int32 signExist = ((base == DEC || base == OCT) && *value == '-');

    // first non zero digit in input number
    int32 non_zero_index = signExist;

    // locate first non zero index
    while(non_zero_index < str_len && value[non_zero_index] == 0) non_zero_index++;

    // if non_zero_index equal length then all digits are zero
    if (non_zero_index == str_len) return false;

    // get number of digits that actually represent the number
    int32 diff = str_len - non_zero_index;

    // if difference less than 10 digits then no overflow will happened
    if (diff < number_sizes[base]) return false;
    // if difference greater than 10 digits then overflow will happened
    if (diff > number_sizes[base]) return true;

    // left digit in input and search strings
    int8 left1 = 0, left2 = 0;

    // if digits equal to 10 then loop over digits from left to right and compare
    for (int32 i = 0; non_zero_index < str_len; non_zero_index++, i++)
    {
        // get input digit
        left1 = value[non_zero_index];
        // get match digit
        left2 = max_numbers[signExist][i];

        // if digits not equal then if left1 is greater overflow will occurred, false otherwise
        if (left1 != left2) return left1 > left2;
    }

    // overflow won't happened
    return false;
}

这个算法可以优化以适用于所有整数类型，但对于浮点数，我必须制作一个新的算法以适用于IEEE浮点表示。

我认为编译器使用比我的更有效的算法来检测溢出，你不觉得吗？

- Muhammad

---

将数字以字符串形式进行比较并不是大多数计算机的有效方法；它们更喜欢数字不以文本形式出现。通常，大多数应用程序将数字文本转换为内部数字，然后处理这些内部数字。处理器喜欢内部格式的数字，并且在以这种方式处理它们方面非常擅长。 - Thomas Matthews

词法分析器已经检测到一个数字，因此它知道它的类型是根据后缀来确定的，现在它将存储文字形式并将其转换为数字形式，我的问题是它将以什么类型的存储方式保存数字？它如何检测转换后的数字是否与文字形式匹配？ - Muhammad

Answer 1

编译器处理这种情况非常简单：它们将数字转换为相应的整数或浮点数。虽然编译器也可以将字符串转换为其他表示形式，但并没有规定必须这样做。

现在来考虑一下您最初的问题；如果您只是将数字视为数字并构建处理它们的例程呢？比如说，一个算法可以将 6 + 5 计算出来并得到两位数字字符串11？将此扩展到其他操作，您就可以直接计算 32769 是否大于 32768。

- Charlie Martin

---

在 C++ 中，如果没有后缀，数字就是 int。因此，如果我执行 INT_MAX + INT_MAX，编译器将使用什么存储来存储结果，然后将其截断到目标类型的限制？ - Muhammad

更大了。但是你不需要做那个求和来知道 INT_MAX+INT_MAX > 'INT_MAX`。有很多选择，一些决策可能取决于底层硬件；例如，是否有一种方法可以检测溢出？如果你坚持的话，你可以使用某种 BigNum 实现，以空间和性能为代价，保证没有实际溢出的可能性。此外，在 C++ 中，甚至不能保证编译器会检测溢出--编译器处理它的一种方式是将责任留给你。 - Charlie Martin

Answer 2

编译器将字符串表示转换为整数，然后在第二步中与类型的上限和下限进行比较似乎是最简单的。

我无法想象为什么比较字符串会更好。

对于浮点数，由于精度和舍入问题，这个问题更加困难。

- mattst88

Answer 3

我不确定大多数编译器使用哪些特定算法来完成这个任务，但以下是几个可行的选项：

1. 编译器可以尝试使用现有库（例如，在C++中，使用stringstream）将字符串转换为适当类型的数字。然后可以使用此数字检查错误。

2. 编译器可以将字符串转换为非常高精度的数字格式（例如，128位整数），然后在从数字文字向基本类型进行赋值时检查该值是否可以在没有强制转换的情况下适合该范围。

- templatetypedef

---

1. 实际上并没有太多已知的速度较慢的选项... :)

- sehe

Answer 4

由于编译器必须将其转换为整数/数字类型，因此它们可以让它们的atoi、atol、atof函数在目标容量超过限制时引发错误。

没有必要事先操作字符串，并在单独的步骤中进行转换。

最有可能的是，编译器将直接在其（高度优化的）解析器语义动作中转换为整数类型。

- sehe

Answer 5

在大多数编译器理论中，程序文本（翻译单元）会被转换成标记和值。例如，文本“150”将被转换为一个带有值150的常量整数标记。当然，在预处理器运行之后才会进行这个过程。

然后编译器开始语法和语义检查的过程。因此，赋值语句会被评估其语法（正确的拼写和格式），然后再检查其语义。

编译器可以抱怨超出范围的值（例如对于unsigned char来说是-150），或者应用一些转换。对于-150的情况，它将被转换为8位值（最高有效位表示负数，现在变成了值128）。我不是语言律师，所以我不确定编译器在这方面有多少自由度，也不知道是否需要警告。

总之，编译器在评估语句和检查语义时有一些自由。所有文本都被转换为令牌和值的内部表示形式（更紧凑的数据结构）。在编译过程的语义阶段，将检查常量整数文字是否在赋值语句范围内。语义是根据语言标准或公司政策决定的。有些语义被转化为编译器选项并留给程序员。

- Thomas Matthews