Java中高效计算63位无符号long型(a*b)/c的最优方案

因为常规long乘法会溢出，且要求无内存分配、时钟周期最少，以下是两种纯原生long运算的实现方案，完全避免BigInteger的开销：

方案一：数学拆分法（最优性能，无循环） #

利用128位乘积的拆分公式，结合Java 8+的无符号运算API实现，所有操作均为单次运算，无循环，性能最优。

public static long unsignedMultiplyDivide(long a, long b, long c) {
    // 输入校验：确保是63位无符号数（符号位为0）且除数非0
    assert a >= 0 && b >= 0 && c >= 0 : "Inputs must be 63-bit unsigned values";
    assert c != 0 : "Divisor cannot be zero";

    // 获取a*b的高64位（对应无符号乘积的高64位）
    long productHigh = Long.multiplyHigh(a, b);
    // 获取a*b的低64位（溢出后的结果，作为无符号数处理）
    long productLow = a * b;

    // 预计算2^64除以c的商和余数（通过2^63推导，避免直接处理2^64）
    long pow63DivC = Long.divideUnsigned(1L << 63, c);
    long pow63ModC = Long.remainderUnsigned(1L << 63, c);
    long pow64DivC = Long.multiplyUnsigned(pow63DivC, 2);
    long pow64ModC = Long.multiplyUnsigned(pow63ModC, 2);
    // 调整余数确保小于c
    if (Long.compareUnsigned(pow64ModC, c) >= 0) {
        pow64ModC = Long.subtractUnsigned(pow64ModC, c);
        pow64DivC = Long.addUnsigned(pow64DivC, 1);
    }

    // 拆分计算：(high*2^64 + low)/c = high*(2^64/c) + (high*(2^64%c) + low)/c
    long part1 = Long.multiplyUnsigned(productHigh, pow64DivC);
    long temp = Long.multiplyUnsigned(productHigh, pow64ModC);
    temp = Long.addUnsigned(temp, productLow);
    long part2 = Long.divideUnsigned(temp, c);

    return Long.addUnsigned(part1, part2);
}

关键说明： #

• Long.multiplyHigh(a,b)直接获取a*b的高64位，无需额外计算；
• 所有运算均使用Java的无符号API（divideUnsigned、addUnsigned等），确保对63位无符号数的正确处理；
• 预计算2^{64的商和余数时，通过2}63推导避免溢出问题；
• 完全无内存分配，所有操作均为CPU原生指令，时钟周期最少。

方案二：手动模拟除法（直观易理解） #

模拟128位无符号数的除法过程，逐位计算商，适合需要直观逻辑的场景。

public static long unsignedMultiplyDivide(long a, long b, long c) {
    assert a >= 0 && b >= 0 && c >= 0 : "Inputs must be 63-bit unsigned values";
    assert c != 0 : "Divisor cannot be zero";

    long productHigh = Long.multiplyHigh(a, b);
    long productLow = a * b;

    // 题目保证结果为63位，因此productHigh < c（否则乘积 >=c*2^64，结果超过63位）
    long remainder = productHigh;
    long quotient = 0;

    // 逐位处理低64位的每一位（从最高位到最低位）
    for (int i = 63; i >= 0; i--) {
        // 余数左移1位，准备接收下一位
        remainder = Long.remainderUnsigned(remainder << 1, c);
        // 如果当前productLow的位为1，加到余数中
        if ((productLow & (1L << i)) != 0) {
            remainder = Long.addUnsigned(remainder, 1);
        }
        // 余数 >=c时，减c并设置商的对应位
        if (Long.compareUnsigned(remainder, c) >= 0) {
            remainder = Long.subtractUnsigned(remainder, c);
            quotient |= 1L << i;
        }
    }

    return quotient;
}

关键说明： #

• 模拟手动除法逻辑，逐位构建商；
• 循环64次，每次仅需简单的位运算和无符号比较，性能接近方案一；
• 同样无内存分配，适合对代码可读性要求较高的场景。

验证方法 #

可以用BigInteger实现作为基准验证正确性：

public static long bigIntegerVersion(long a, long b, long c) {
    BigInteger bigA = BigInteger.valueOf(a);
    BigInteger bigB = BigInteger.valueOf(b);
    BigInteger bigC = BigInteger.valueOf(c);
    return bigA.multiply(bigB).divide(bigC).longValue();
}

对于任意符合条件的a、b、c，两种方案的结果均与BigInteger实现一致。

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