如何高效计算2¹²⁸ % 非零uint64_t类型的n？

更优通用方案 #

利用模运算的基本性质：(2^{128} = (2^{64})2)，因此 (2^{128} \mod n = [(2^{64} \mod n)^2] \mod n)。基于这个性质，我们可以避免依赖平台特定的窄化除法指令，同时提升计算效率：

• 计算(2^{64} \mod n)：由于(2^{64} = \text{UINT64_MAX} + 1)，可通过(UINT64_MAX % n) + 1得到结果，若该值等于n则取0（等价于模n后的余数）。
• 计算平方后的模n结果：将第一步得到的余数平方后再对n取模，优先利用编译器对128位整数的支持（如GCC/Clang的__int128），或采用通用128位模运算实现，避免调用低效的除法指令。

代码实现 #

#include <stdint.h>
#include <stdbool.h>

// 判断n是否是2的幂
static bool is_power_of_two(uint64_t n) {
    return (n & (n - 1)) == 0;
}

uint64_t mod_pow2_128(uint64_t n) {
    // 特殊情况快速处理：n=1或n是2的幂时，余数直接为0
    if (n == 1 || is_power_of_two(n)) {
        return 0;
    }

    // 计算2^64 mod n
    uint64_t r64 = (UINT64_MAX % n) + 1;
    if (r64 == n) {
        r64 = 0;
    }

    // 计算(r64 * r64) mod n
    #if defined(__GNUC__) || defined(__clang__)
        // 利用__int128直接完成128位乘法取模，效率最优
        return ((__int128)r64 * r64) % n;
    #elif defined(_MSC_VER)
        // MSVC下用_umul128计算128位乘积，再通过_udiv128取模
        uint64_t high, low;
        low = _umul128(r64, r64, &high);
        uint64_t remainder;
        _udiv128(high, low, n, &remainder);
        return remainder;
    #else
        // 通用128位模运算实现，不依赖平台内置函数
        uint64_t remainder = high % n;
        remainder = (remainder << 32) % n;
        remainder = (remainder << 32) % n;
        remainder = (remainder + (low >> 32)) % n;
        remainder = (remainder << 32) % n;
        remainder = (remainder + (low & 0xFFFFFFFF)) % n;
        return remainder;
    #endif
}

方案优势 #

• 效率更高：乘法指令执行速度远快于除法，利用__int128的实现仅需一次乘模操作，比原方法的两次除法调用高效得多。
• 兼容性更强：无需依赖ARM等平台不支持的窄化除法指令（如_udiv128），通用实现可适配多数编译器和架构。
• 特殊场景优化：针对n为2的幂或1的情况直接返回结果，进一步提升计算速度。

相关问题：如何在C语言中计算2⁶⁴/n？

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