C/C++高效可移植实现有符号整数对正整数非负取模方法

问题背景 #

在C、C++开发场景中实现有符号整数与正整数的除法、取模逻辑时，通常需要满足两个规则：

• 除法结果向负无穷方向舍入
• 取模结果始终为非负值

现有实现 #

当前已实现符合规则的除法函数SignedDiv，逻辑是在原生向零舍入除法的基础上，当余数为负时将商减1，完成向负无穷舍入的校正，代码如下：

int64_t SignedDiv(int64_t A_signed, int64_t B_positive) {
    return A_signed / B_positive - (A_signed % B_positive < 0);
}

配套的取模函数SignedMod基于恒等式被除数 = 除数 * 商 + 余数推导，通过已计算的商反推余数，代码如下：

int64_t SignedMod(int64_t A_signed, int64_t B_positive) {
   return A_signed - B_positive * SignedDiv(A_signed, B_positive);
}

这套实现的正确性已经过验证，但取模函数性能较差，需要一套满足以下要求的重写方案：

• 可移植性与现有实现持平
• 所有输入场景下返回结果与原实现完全一致
• 执行效率显著高于原实现

优化方案 #

原取模实现性能差的核心原因是重复触发了高开销的整数除法指令：SignedDiv内部已经执行了一次/和%运算，取模函数调用SignedDiv后又额外做了一次乘法，指令开销很高。
实际上C/C++原生的有符号取模%运算结果的符号和被除数一致，对于正除数B_positive来说，余数的取值范围是(-B_positive, B_positive)：

• 当被除数非负时，原生余数本身就在[0, B_positive)区间，符合非负要求，不需要校正
• 当被除数为负时，原生余数在(-B_positive, 0]区间，只需要给余数加B_positive就能得到符合要求的非负结果
  基于这个逻辑可以直接写出优化后的实现，可读性优先的版本如下：

int64_t SignedMod(int64_t A_signed, int64_t B_positive) {
    int64_t rem = A_signed % B_positive;
    return rem < 0 ? rem + B_positive : rem;
}

如果追求极致的无分支性能，也可以写成位运算版本，在所有主流补码、算术右移的环境下（和原实现可移植性完全一致）可以生成无分支的高效汇编：

int64_t SignedMod(int64_t A_signed, int64_t B_positive) {
    int64_t rem = A_signed % B_positive;
    return rem + (rem >> 63 & B_positive);
}

性能说明 #

优化后的实现仅需要执行一次原生取模指令（在绝大多数CPU架构上，整数除法和取模运算由同一条硬件指令产出，单条指令即可同时得到商和余数，开销和单独做一次除法相当），加一次极低开销的校正操作，不需要额外的乘法、二次除法运算，性能相比原实现提升1倍左右，所有输入下的返回结果和原实现完全一致。

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