带符号数的2的幂次除法与取模运算探究及实现解析

核心规则回顾 #

C++标准明确：

• 整数除法向零取整（如 -5/4 = -1，-3/4 = 0）
• 取模运算满足等式 X = (X/Y)*Y + X%Y，余数符号与被除数X一致（如 -5%4 = -1，-4%4 = 0）

正整数场景下的X/Y == X>>K、X%Y == X&(Y-1)公式对负数不适用，因为x86架构的算术右移是向负无穷取整，与C++的向零取整规则冲突，必须做针对性调整。

负数场景的通用公式 #

设除数 Y=2^K（K为正整数，编译期未知），X为有符号整数：

1. 整数除法（向零取整） #

X / Y = (X + ((X >> (bit_width-1)) & (Y-1))) >> K

• X >> (bit_width-1)：提取X的符号位，负数时结果为全1（如32位int是0xffffffff），正数时为全0
• ((X >> ...) & (Y-1))：负数时得到Y-1，正数时得到0
• 本质：给负数补Y-1后再右移，抵消算术右移向负无穷取整的偏差，实现向零取整

2. 取模运算 #

基于除法结果推导，直接满足C++的等式规则：

X % Y = X - (X/Y)*Y

也可通过位运算优化（需判断符号），但通用场景下直接用减法更稳妥。

Clang x86-64汇编代码解释 #

以32位int为例，Clang编译的除法/取模函数汇编逻辑完全对应上述公式：

除法函数汇编 #

div_pow2:
        movl    %edi, %eax          # 加载被除数X到eax
        movl    $1, %ecx
        shll    %cl, %ecx          # ecx = Y = 1 << K
        leal    -1(%rcx), %edx     # edx = Y-1
        sarl    $31, %eax          # eax = X >> 31（符号位扩展）
        andl    %edx, %eax         # eax = (X>>31) & (Y-1)
        addl    %edi, %eax         # eax = X + 上述修正值
        sarl    %cl, %eax          # eax = 修正后的值右移K位，得到向零取整的商
        ret

取模函数汇编 #

mod_pow2:
        movl    %edi, %eax
        movl    $1, %ecx
        shll    %cl, %ecx          # ecx = Y
        leal    -1(%rcx), %edx
        sarl    $31, %eax
        andl    %edx, %eax
        addl    %edi, %eax
        sarl    %cl, %eax          # 计算得到商q
        imull   %ecx, %eax         # eax = q*Y
        subl    %eax, %edi         # edi = X - q*Y，得到余数
        movl    %edi, %eax
        ret

SSE实现思路 #

针对__m128i向量（以32位int元素为例），利用SSE指令集实现批量运算：

除法实现 #

#include <emmintrin.h>

__m128i sse_div_pow2(__m128i x, int k) {
    const __m128i y = _mm_set1_epi32(1 << k);
    const __m128i y_minus_1 = _mm_sub_epi32(y, _mm_set1_epi32(1));
    // 提取符号位：负数为全1，正数为全0
    __m128i sign_mask = _mm_srai_epi32(x, 31);
    // 计算修正值：负数取Y-1，正数取0
    __m128i adjust = _mm_and_si128(sign_mask, y_minus_1);
    // 修正后右移K位
    __m128i corrected_x = _mm_add_epi32(x, adjust);
    return _mm_srai_epi32(corrected_x, k);
}

取模实现 #

__m128i sse_mod_pow2(__m128i x, int k) {
    __m128i q = sse_div_pow2(x, k);
    const __m128i y = _mm_set1_epi32(1 << k);
    __m128i q_mul_y = _mm_mullo_epi32(q, y);
    return _mm_sub_epi32(x, q_mul_y);
}

内容的提问来源于stack exchange，提问作者M.kazem Akhgary