如何在C语言中无溢出快速计算2^64除以随机整数的商和模

问题描述 #

我想了解如何在无溢出的情况下执行除法与取模运算。目前我通过以下方式实现：先计算2^{63除以随机整数N，再将商翻倍，若(2}63 % N)<<1大于等于N则将商加1，同时调整模值。

当前实现代码：

int64 div, mod, N;
...
div = ((1<<63) / N) << 1;
mod = ((1<<63) % N) << 1;

if (mod >= N){
    div++;
    mod -= N;
}

该流程较为复杂，并非最优方案，请问是否有更高效的实现方式？

优化方案 #

方法1：利用128位整数类型（推荐） #

如果你的编译器支持__int128（如GCC、Clang等主流编译器），可以直接用128位整数承载2^64，一步完成除法和取模运算，代码简洁且效率更高，完全规避分步判断逻辑：

int64_t div, mod, N;
__int128_t num = (__int128_t)1 << 64; // 128位整数存储2^64，无溢出风险
div = (int64_t)(num / N);
mod = (int64_t)(num % N);

现代主流编译器基本都支持__int128，这种方式的可读性和执行效率远优于原实现。

方法2：简化原逻辑的分支优化 #

如果无法使用128位整数，可以合并原逻辑中的判断与计算，减少分支操作（分支可能影响CPU流水线效率）：

int64_t div, mod, N;
int64_t half_div = (1LL << 63) / N;
int64_t half_mod = (1LL << 63) % N;

mod = half_mod * 2;
div = half_div * 2 + (mod >= N);
mod -= (mod >= N) * N;

这里把模值调整的分支操作转化为算术运算，避免了条件跳转，在部分场景下能小幅提升性能，但整体收益不如128位整数方案。

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