在两个大整数的乘法期间捕获并计算溢出 [英] Catch and compute overflow during multiplication of two large integers

问题描述

我正在寻找一种有效（可选的标准，优雅且易于实现）的解决方案来乘以相对较大的数字，并将结果存储为一个或多个整数：

I am looking for an efficient (optionally standard, elegant and easy to implement) solution to multiply relatively large numbers, and store the result into one or several integers :

假设我有两个64位整数，如下所示：

Let say I have two 64 bits integers declared like this :

uint64_t a = xxx, b = yyy; 

当我做 a * b 时，如何我可以检测到操作是否导致溢出，并且在这种情况下将进位存储在某处吗？

When I do a * b, how can I detect if the operation results in an overflow and in this case store the carry somewhere?

请注意我不想使用任何大的 - 数字库，因为我对存储数字的方式有限制。

Please note that I don't want to use any large-number library since I have constraints on the way I store the numbers.

推荐答案

1。检测溢出：

x = a * b;
if (a != 0 && x / a != b) {
    // overflow handling
}

编辑：修正除以 0 （谢谢马克！）

Fixed division by 0 (thanks Mark!)

<强> 2。计算进位非常复杂。一种方法是将两个操作数分成半字，然后将 long multiplication 应用于半字：

2. Computing the carry is quite involved. One approach is to split both operands into half-words, then apply long multiplication to the half-words:

uint64_t hi(uint64_t x) {
    return x >> 32;
}

uint64_t lo(uint64_t x) {
    return ((1L << 32) - 1) & x;
}

void multiply(uint64_t a, uint64_t b) {
    // actually uint32_t would do, but the casting is annoying
    uint64_t s0, s1, s2, s3; 

    uint64_t x = lo(a) * lo(b);
    s0 = lo(x);

    x = hi(a) * lo(b) + hi(x);
    s1 = lo(x);
    s2 = hi(x);

    x = s1 + lo(a) * hi(b);
    s1 = lo(x);

    x = s2 + hi(a) * hi(b) + hi(x);
    s2 = lo(x);
    s3 = hi(x);

    uint64_t result = s1 << 32 | s0;
    uint64_t carry = s3 << 32 | s2;
}

要看到没有任何部分金额本身可以溢出，我们认为最差案例：

To see that none of the partial sums themselves can overflow, we consider the worst case:

        x = s2 + hi(a) * hi(b) + hi(x)

设 B = 1<< 32 。然后我们

            x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
              <= B*B - 1
               < B*B

我相信这会起作用 - 至少它会处理Sjlver的测试用例。除此之外，它是未经测试的（甚至可能无法编译，因为我手头没有C ++编译器了。）

I believe this will work - at least it handles Sjlver's test case. Aside from that, it is untested (and might not even compile, as I don't have a C++ compiler at hand anymore).

这篇关于在两个大整数的乘法期间捕获并计算溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！