Lemire近无除法模技巧中-s%s与2^L%s结果不一致原因问询

核心遗漏要点 #

你忽略了无符号取负运算和位宽强绑定的特性：

• 无符号整数的取负运算本质是2^当前变量位宽 - 原值，-s % s等价于2^L % s的前提是：s本身是L位无符号类型，或者取负操作被限制在L位无符号域执行。

你当前测试用的s是64位无符号整数，执行-s时计算的是2^64 - s，自然和你预期的32位场景的2^32 - s不等价，模运算结果自然有差异。

修正验证代码 #

将取负操作限制在32位无符号域即可得到匹配结果：

#include <iostream>
#include <cstdint>

int main() {
  uint64_t s = 1440000000;
  uint64_t k1 = (1ULL << 32ULL) % s;
  // 取负操作限定在32位无符号域
  uint64_t k2 = static_cast<uint32_t>(-static_cast<uint32_t>(s)) % s;
  std::cout << k1 << std::endl;
  std::cout << k2 << std::endl;
}

运行后两个输出均为1414967296，和等价结论一致。

原计算结果差异的原理 #

你原有代码的两个结果对应不同位宽的计算：

• (1ULL << 32) % s 对应 2^32 mod 1440000000 = 1414967296
• 64位域执行-s % s 对应 2^64 mod 1440000000 = 109551616，和你实际得到的k2结果完全匹配。

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