从算术运算中溢出

Question

进行数学运算时，如何得到溢出的部分？

例如，假设32位整数：

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

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

如何进行乘法运算？我可以将两个大数相乘，只得到溢出部分吗？

bigint库如何管理它？

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. 使用内联汇编读取进位标志

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库可以通过选择最大为最大整数类型宽度一半的肢体类型来避免这种麻烦。

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