大数的乘法,如何捕获溢出

发布时间：2020-12-14 04:56:42 所属栏目：大数据来源：网络整理

导读：我正在寻找一个高效的(可选标准，优雅和容易实现)解决方案来乘以相对大的数字，并将结果存储到一个或几个整数：假设我有两个64位整数这样声明： uint64_t a = xxx,b = yyy; 当我做a * b，如何检测操作是否导致溢出，在这种情况下存储进位的地方？请注意，

我正在寻找一个高效的(可选标准，优雅和容易实现)解决方案来乘以相对大的数字，并将结果存储到一个或几个整数：

假设我有两个64位整数这样声明：

uint64_t a = xxx,b = yyy;

当我做a * b，如何检测操作是否导致溢出，在这种情况下存储进位的地方？

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

谢谢

解决方法

检测：

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

编辑：固定除以0(谢谢马克！)

计算进位相当牵连。一种方法是将两个操作数拆分为半字，然后将long multiplication应用于半字：

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;
}

要看到没有一个部分和本身可以溢出，我们认为最坏的情况：

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

令B = 1<<我们有

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

我相信这将工作 – 至少它处理Sjlver的测试用例。除此之外，它是未经测试的(甚至可能不编译，因为我现在没有一个C编译器)。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!