如何扩展代码实现128位整数除以64位整数？

现有代码仅能实现128位整数（由high和low两个uint64_t拼接而成）除以32位整数，无法处理64位整数除数。已知_umul128()或__uint128_t这类指令，但需要一个可移植的版本。当前代码仅在除数小于uint32_t时生效，不清楚原因。

原代码如下：

uint64_t udiv32(uint64_t high, uint64_t low, uint32_t divisor, uint32_t* rem)
{
    uint64_t q0, r0;
    uint64_t q1, r1;
    uint64_t temp;

    const uint32_t a_lo = low & 0xFFFFFFFF;
    const uint32_t a_hi = low >> 32;

    r0 = high % divisor;

    temp = ((r0 << 32) | a_hi);
    q1 = temp / divisor;
    r1 = temp % divisor;

    temp = ((r1 << 32) | a_lo);
    q0 = temp / divisor;
    r0 = temp % divisor;

    *rem = r0;
    return ((q1 << 32) | q0);
}

原代码限制的原因分析 #

原代码只能处理32位除数，核心是它的分段逻辑：把128位被除数拆分为high（高64位）+low（低64位），再将low拆成两个32位片段处理。因为除数是32位，中间生成的64位temp值除以32位除数时，商最多是32位（2^64 / 2^32 = 2^32），所以最后拼接q1和q0得到64位商是合理的。但如果换成64位除数，这种分段逻辑就失效了：128位被除数除以64位除数，商最多是64位，原代码的分段计算方式无法覆盖所有情况，且中间步骤的64位值除以64位除数可能出现的溢出问题也没处理。

可移植的128位除以64位实现 #

基于长除法原理，用标准C的uint64_t操作实现完全可移植的版本，不依赖任何编译器扩展或平台指令：

// 计算 (high << 64 | low) / divisor，返回64位商，余数存入*rem
uint64_t udiv64(uint64_t high, uint64_t low, uint64_t divisor, uint64_t* rem)
{
    uint64_t quotient = 0;
    uint64_t remainder = high;

    // 除数为0的错误处理，可根据需求调整（比如加断言）
    if (divisor == 0) {
        *rem = 0;
        return 0;
    }

    // 从最高位到最低位逐位执行长除法
    for (int i = 0; i < 64; i++) {
        // 余数左移1位，并入被除数当前位（从high到low的第63-i位）
        remainder = (remainder << 1) | ((low >> (63 - i)) & 1);
        
        // 若余数大于等于除数，则减去除数，商对应位置1
        if (remainder >= divisor) {
            remainder -= divisor;
            quotient |= (1ULL << (63 - i));
        }
    }

    *rem = remainder;
    return quotient;
}

代码说明 #

• 长除法逻辑：模拟手动计算除法的过程，逐位处理128位被除数，每次判断余数是否够除除数，够除则更新余数和商。
• 可移植性：仅使用C99标准的uint64_t类型和位操作，能在所有支持C99及以上的编译器上运行。
• 边界处理：自动支持被除数小于除数、等于除数等边界情况；除数为0的情况可根据业务需求补充更严格的错误处理（如assert(divisor != 0)）。

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