算术运算中发生溢出

Question

在进行数学运算时，如何获取溢出的部分？

例如，假设使用32位整数：

unsigned int a = 0Xffffffff;
unsigned int b = 0xffffffff;
unsigned int c = a + b;

在这种情况下，c 是 0xfffffffe，但答案应该是 0x1fffffffe。我该如何获取溢出的1？

同样的，对于乘法，我该如何做到相同的效果？我可以将两个大数相乘并仅获取溢出部分吗？

bigint（大整数）库是如何管理这个的？

- mark

---

可能会有关：https://zh.wikipedia.org/wiki/%E4%B9%98%E6%B3%95 - Igor Tandetnik

64位整数的位移操作怎么样？ - Gerhard Stein

由于两个数字的和大于存储值，没有地方可以存储该数字，因此会发生溢出。如果您能够在某个地方检查溢出，那么根本不需要发生溢出。但是，您可以检测到溢出并执行其他操作，例如：if(UINT_MAX - a < b) then handle_it()。 - DCTID

"unsigned long long int" 是标准的 C 类型，必须至少有 64 位。因此，在您的 32 位示例中，可以通过计算 (unsigned long long int) a * b 来得出乘积，之后可以通过移位和掩码来提取低位和高位的 32 位。 - Eric Postpischil

@Dr.-Ing.GerhardStein问题将会出现无符号长整型。那么应该使用什么类型？ - 0___________

Q：如何获取溢出的1？A：遗憾的是，你无法获得。解决方法：a）使用更大的整数类型进行算术运算（并检查高阶位），b）编写内联汇编来检查CPU的进位标志等。请参见：http://www.cplusplus.com/articles/DE18T05o/。大部分讨论同样适用于C。 - FoggyDay

Answer 1

@警告 不可移植@

1. 使用https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

示例：https://godbolt.org/z/NcyNzR

#include <stdio.h> 
int main(void)
{
    unsigned int res;

    if(__builtin_uadd_overflow(0Xffffffff, 0Xffffffff, &res))
    {
        printf("Overflowed\n");
    }
    printf("Result: 0x%x\n", res);
}

2. 使用内联汇编读取进位标志

- 0___________

Answer 2

假设操作数是无符号类型，你可以这样写：

bool cf = a+b<a;

或者

bool cf = a>-1-b;

这些内容不受需要使用的更大类型的存在影响。

乘法更加困难；如果没有更大的类型，就无法访问结果的上半部分。如果您有更大的类型，可以使用它。例如，如果您的操作数是uint32_t，

uint32_t upper = ((uint64_t)a * b) >> 32;
uint32_t lower = a*b;

否则，你只能使用半尺寸的类型并使用长乘法。例如，对于 uint64_t a,b; 的情况。

uint32_t al = a, ah = a>>32;
uint32_t bl = b, bh = b>>32;

然后结果的上半部分是ah*bh加上al*bh、ah*bl和al*bl的进位位。

Bigint库可以通过选择一个最多只有最大整数类型宽度一半的limb类型来避免这种痛苦。

- R.. GitHub STOP HELPING ICE

Answer 3

我如何获取溢出的1？

为了便于移植（不要忘记unsigned int可能只有16位），稍后可以这样做：

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;
    uint32_t c_low = a + b;
    uint32_t c_high;
    if(c_low >= a) {
        c_high = 0;
    } else {
        c_high = 1;
    }

为了以便携的方式提前完成它（无需分支）：

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;
    uint32_t c_low;
    uint32_t c_high;

    c_high = (a&b) >> 31;
    c_low = (a ^ (c_high<<31)) + b;

我该如何对乘法做同样的操作呢？

乘法没有进位，而是有一个“上半部分”。具体来说，如果您将具有N位的无符号整数与具有M位的无符号整数相乘，则结果将具有N+M位；如果两个数字大小相同，则结果将是原来的两倍。

不幸的是，C语言不支持“结果类型比源类型/类型更大”的功能，因此您需要“预提升”源类型，例如：

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;
    uint64_t temp = (uint64_t)a * (uint64_t)b;
    uint32_t c_low = temp;
    uint32_t c_high = temp >> 32;

当然，如果编译器不支持更大的类型，则必须将其拆分为较小的部分，例如：

    uint32_t a = 0Xffffffff;
    uint32_t b = 0xffffffff;

    uint32_t a_low = a & 0xFFFF;
    uint32_t a_high = a >> 16;
    uint32_t b_low = a & 0xFFFF;
    uint32_t b_high = b >> 16;

    uint32_t temp_0 = a_low * b_low;
    uint32_t temp_16a = a_high * b_low;
    uint32_t temp_16b = a_low * b_high;
    uint32_t temp_32 = a_high * b_high;

    uint32_t c_low = temp_0 + (temp16a << 16) + (temp16b << 16);
    uint32_t c_high = (temp16a >> 16) + (temp16b >> 16) + temp_32;

"bigint"库如何处理这个问题？

主要是使用内联汇编语言，因为大多数CPU都支持高效地处理更大的整数，并且/或者可以直接访问进位标志。例如，在80x86中，CPU具有adc/sbb、shld/shrd、mul（带有双宽结果）/div（带有双宽分子）以及可能的扩展（adcx和adox）。

在32位80x86汇编语言中，加法可能如下所示： "

    xor edx,0
    add eax,ebx      ;c_low = a + b
    adc edx,0        ;c_high = carry

...乘法可能看起来像这样:

    mul ebx          ;edx:eax = a * b

- Brendan