如何不使用bigint比较两组long long乘积的大小？

问题背景 #

需要判断四个long long乘积的大小关系，但存在以下限制：

• 禁止使用bigint或__int128
• 转换为long double会因精度丢失导致错误结果
  已知四个long long的乘积为256位，但99.99%的场景下差异出现在最后128位（多数集中在最后64位），需要在保证完全精确的前提下，优化平均运行速度。此前的高位低位拆分思路被指出本质等同于实现bigint，效率不足。

优化思路 #

• 优先快速判断低阶差异：利用绝大多数差异出现在最后64位的特性，先计算两个乘积的低64位（借助unsigned long long的溢出特性自然取模2^64），若低64位能区分大小，直接返回结果，这一步覆盖99.99%的场景。
• 低阶相等时再处理高阶：仅当低64位完全相等时，再计算乘积的高阶部分（即去掉低64位后的剩余值），通过拆分乘法的方式计算256位乘积的高阶部分，避免完整计算大整数。

代码实现 #

#include <cstdint>
#include <cstdlib>

bool is_product_greater(long long a, long long b, long long c, long long d,
                        long long e, long long f, long long g, long long h) {
    // 计算左右乘积的符号位
    int sign_left = ((a < 0) ^ (b < 0) ^ (c < 0) ^ (d < 0)) ? -1 : 1;
    int sign_right = ((e < 0) ^ (f < 0) ^ (g < 0) ^ (h < 0)) ? -1 : 1;
    
    // 符号不同直接判断
    if (sign_left != sign_right) {
        return sign_left > sign_right;
    }
    
    // 转为无符号整数处理绝对值乘积比较
    uint64_t ua = llabs(static_cast<int64_t>(a));
    uint64_t ub = llabs(static_cast<int64_t>(b));
    uint64_t uc = llabs(static_cast<int64_t>(c));
    uint64_t ud = llabs(static_cast<int64_t>(d));
    uint64_t ue = llabs(static_cast<int64_t>(e));
    uint64_t uf = llabs(static_cast<int64_t>(f));
    uint64_t ug = llabs(static_cast<int64_t>(g));
    uint64_t uh = llabs(static_cast<int64_t>(h));
    
    // 第一步：计算低64位乘积，利用unsigned溢出自然取模2^64
    auto mul_low64 = [](uint64_t x, uint64_t y) -> uint64_t {
        return x * y;
    };
    
    uint64_t low_left = mul_low64(mul_low64(ua, ub), mul_low64(uc, ud));
    uint64_t low_right = mul_low64(mul_low64(ue, uf), mul_low64(ug, uh));
    
    // 根据符号判断低64位的比较结果
    if (sign_left == 1) {
        if (low_left != low_right) {
            return low_left > low_right;
        }
    } else {
        // 负数乘积，低64位越大，整体值越小
        if (low_left != low_right) {
            return low_left < low_right;
        }
    }
    
    // 第二步：低64位相等，计算乘积的高阶部分
    // 计算两个64位整数相乘的高64位
    auto mul_high64 = [](uint64_t x, uint64_t y) -> uint64_t {
        uint32_t xh = static_cast<uint32_t>(x >> 32);
        uint32_t xl = static_cast<uint32_t>(x);
        uint32_t yh = static_cast<uint32_t>(y >> 32);
        uint32_t yl = static_cast<uint32_t>(y);
        
        uint64_t xl_yl = static_cast<uint64_t>(xl) * yl;
        uint64_t xl_yh = static_cast<uint64_t>(xl) * yh;
        uint64_t xh_yl = static_cast<uint64_t>(xh) * yl;
        uint64_t xh_yh = static_cast<uint64_t>(xh) * yh;
        
        uint64_t carry = (xl_yl >> 32) + (xl_yh & 0xFFFFFFFFULL) + (xh_yl & 0xFFFFFFFFULL);
        return xh_yh + (xl_yh >> 32) + (xh_yl >> 32) + (carry >> 32);
    };
    
    // 计算左边ab*cd的高阶部分
    uint64_t ab_low = ua * ub;
    uint64_t ab_high = mul_high64(ua, ub);
    uint64_t cd_low = uc * ud;
    uint64_t cd_high = mul_high64(uc, ud);
    
    uint64_t mid_term_low = mul_low64(ab_high, cd_low) + mul_low64(ab_low, cd_high);
    uint64_t mid_term_high = mul_high64(ab_high, cd_low) + mul_high64(ab_low, cd_high);
    // 处理mid_term_low的进位
    if (mid_term_low < mul_low64(ab_high, cd_low)) {
        mid_term_high++;
    }
    
    uint64_t left_high = mul_low64(ab_high, cd_high) + mid_term_high;
    
    // 计算右边ef*gh的高阶部分
    uint64_t ef_low = ue * uf;
    uint64_t ef_high = mul_high64(ue, uf);
    uint64_t gh_low = ug * uh;
    uint64_t gh_high = mul_high64(ug, uh);
    
    uint64_t right_mid_low = mul_low64(ef_high, gh_low) + mul_low64(ef_low, gh_high);
    uint64_t right_mid_high = mul_high64(ef_high, gh_low) + mul_high64(ef_low, gh_high);
    if (right_mid_low < mul_low64(ef_high, gh_low)) {
        right_mid_high++;
    }
    
    uint64_t right_high = mul_low64(ef_high, gh_high) + right_mid_high;
    
    // 根据符号返回高阶比较结果
    if (sign_left == 1) {
        return left_high > right_high;
    } else {
        return left_high < right_high;
    }
}

方案优势 #

• 平均速度极快：99.99%的场景只需计算低64位即可得出结果，无需进入复杂的高阶计算。
• 完全精确：所有计算基于整数运算，无浮点转换的精度损失，也未使用bigint或__int128。
• 符号处理完善：先通过异或判断乘积符号，符号不同直接返回，避免无符号计算的干扰。

内容的提问来源于stack exchange，提问作者sibillalazzerini