优化64位取模运算：针对固定运行时模数的高效实现方案

核心思路 #

当除数m固定时，我们可以基于经典的无符号整数除法优化思路（用乘法+移位替代除法），预先计算一组优化参数（魔术数、移位量），将x % m的计算转化为乘法、移位和少量减法，替代原生的除法指令——原生除法指令的延迟远高于乘法，批量计算时能显著提升速度。这种思路和编译器对编译时常量除数的优化逻辑完全一致，只是把参数计算从编译期移到了运行期预处理阶段。

优化原理（无符号64位场景） #

对于无符号64位整数x和固定除数m>1，我们可以找到一个64位整数M（魔术数）和整数s（移位量），使得：

1. x % m = x - ((x * M) >> s) * m
2. 其中s的取值范围是64 ≤ s ≤ 127，M是预先计算的常数

参数计算步骤（预处理阶段） #

给定m，按以下步骤计算M和s：

1. 找到最小的k，使得2^k ≥ m（即k是m的二进制位数）
2. 令s = 64 + k，确保计算时不会出现精度丢失
3. 计算魔术数M = ceil(2^s / m)，这里需要用128位整数避免溢出

代码实现 #

伪代码 #

// 预处理阶段：计算固定m的优化参数
struct ModParams {
    m: uint64,
    magic: uint64,
    shift: uint32
}

function precompute_mod_params(m: uint64) -> ModParams:
    if m == 1:
        return ModParams{m: 1, magic: 0, shift: 0} // 任何数%1都是0
    
    k = 64
    // 找到最小的k，使得2^k >= m
    while (1 << k) < m:
        k += 1
    
    s = 64 + k
    // 用128位整数计算分子，避免溢出
    numerator = 1 << s
    // 计算ceil(2^s / m)
    M = (numerator + m - 1) // m
    
    return ModParams{m: m, magic: M as uint64, shift: s}

// 批量计算阶段：用预计算的参数快速取模
function fast_mod(x: uint64, params: ModParams) -> uint64:
    if params.m == 1:
        return 0
    
    // 计算商的近似值
    q = (x as uint128) * params.magic >> params.shift
    // 计算取模结果
    result = x - q * params.m
    
    // 修正近似误差（偶尔会出现result >= m的情况）
    if result >= params.m:
        result -= params.m
    
    return result

C语言实现 #

#include <stdint.h>
#include <stdio.h>

typedef struct {
    uint64_t m;
    uint64_t magic;
    uint32_t shift;
} ModParams;

ModParams precompute_mod_params(uint64_t m) {
    ModParams params = {0};
    params.m = m;
    
    if (m == 1) {
        return params;
    }
    
    uint32_t k = 64;
    while ((1ULL << k) < m) {
        k++;
    }
    uint32_t s = 64 + k;
    
    // 使用128位整数计算魔术数，避免溢出
    __uint128_t numerator = (__uint128_t)1 << s;
    __uint128_t magic_128 = (numerator + m - 1) / m;
    params.magic = (uint64_t)magic_128;
    params.shift = s;
    
    return params;
}

uint64_t fast_mod(uint64_t x, ModParams params) {
    if (params.m == 1) {
        return 0;
    }
    
    __uint128_t product = (__uint128_t)x * params.magic;
    uint64_t q = (uint64_t)(product >> params.shift);
    uint64_t result = x - q * params.m;
    
    // 修正近似误差
    if (result >= params.m) {
        result -= params.m;
    }
    
    return result;
}

// 测试示例
int main() {
    uint64_t m = 123456789;
    ModParams params = precompute_mod_params(m);
    
    uint64_t test_x[] = {0, 123456789, 987654321, 18446744073709551615ULL};
    for (size_t i = 0; i < sizeof(test_x)/sizeof(test_x[0]); i++) {
        uint64_t x = test_x[i];
        uint64_t fast_result = fast_mod(x, params);
        uint64_t native_result = x % m;
        printf("x = %llu, fast_mod = %llu, native_mod = %llu, match: %s\n",
               (unsigned long long)x,
               (unsigned long long)fast_result,
               (unsigned long long)native_result,
               fast_result == native_result ? "yes" : "no");
    }
    
    return 0;
}

Rust语言实现 #

use std::u64;

#[derive(Debug, Clone, Copy)]
struct ModParams {
    m: u64,
    magic: u64,
    shift: u32,
}

fn precompute_mod_params(m: u64) -> ModParams {
    if m == 1 {
        return ModParams { m: 1, magic: 0, shift: 0 };
    }
    
    let mut k = 64;
    while (1u64 << k) < m {
        k += 1;
    }
    let s = 64 + k;
    
    // 使用128位整数计算魔术数
    let numerator = 1u128 << s;
    let magic_128 = (numerator + m as u128 - 1) / m as u128;
    
    ModParams {
        m,
        magic: magic_128 as u64,
        shift: s,
    }
}

fn fast_mod(x: u64, params: ModParams) -> u64 {
    if params.m == 1 {
        return 0;
    }
    
    let product = (x as u128) * params.magic as u128;
    let q = (product >> params.shift) as u64;
    let mut result = x - q * params.m;
    
    // 修正近似误差
    if result >= params.m {
        result -= params.m;
    }
    
    result
}

fn main() {
    let m = 123456789;
    let params = precompute_mod_params(m);
    
    let test_x = [0, 123456789, 987654321, u64::MAX];
    for &x in &test_x {
        let fast_result = fast_mod(x, params);
        let native_result = x % m;
        println!(
            "x = {}, fast_mod = {}, native_mod = {}, match: {}",
            x,
            fast_result,
            native_result,
            fast_result == native_result
        );
    }
}

注意事项 #

• 上述实现依赖128位整数支持（C的__uint128_t、Rust的u128），现代主流编译器（GCC、Clang、MSVC）均支持该特性。
• 预处理阶段仅需执行一次，之后所有取模计算均可复用参数，批量处理数十亿个x时能大幅降低运算耗时。
• 误差修正步骤是必要的：由于乘法移位的近似性，偶尔会出现result >= m的情况，一次减法即可修正，几乎无性能损耗。

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