求带中间值向零舍入的32位整数算术右移高效算法

需求说明 #

实现一个高效算法，完成32位补码整数的算术右移，结果需取最接近的整数；当小数部分恰好为0.5时，采用向零舍入规则。要求：

• 无浮点指令、无整数除法/取模指令
• 参考Cortex-M0指令集，以最少指令实现，无需额外空间
• C语言原型：int asrz(int x, int n);

假设条件 #

• 整数为32位有符号类型，负数采用补码表示
• 移位计数n ≥ 0
• "高效算法"定义：时间与空间复杂度平衡，指令数最少，无额外空间开销

舍入规则细节 #

算法计算逻辑等价于数学意义上的Y = X / 2^N，舍入规则如下：

• 结果取与真实值最接近的整数
• 当小数部分恰好为0.5时，向零方向舍入（正数舍为0，负数舍为0）

正数示例 #

0 >> 1 = 0
1 >> 1 = 0 (0.5)
2 >> 1 = 1
3 >> 1 = 1 (1.5)
...
2 >> 2 = 0 (0.5)
3 >> 2 = 1 (0.75)
4 >> 2 = 1
5 >> 2 = 1 (1.25)
6 >> 2 = 1 (1.5)
7 >> 2 = 2 (1.75)
...
12 >> 3 = 1 (1.5)
13 >> 3 = 2 (1.625)

负数示例（结果与正数关于零对称） #

-1 >> 1 =  0 (-0.5)
-2 >> 1 = -1
-3 >> 1 = -1 (-1.5)
...
-2 >> 2 =  0 (-0.5)
-3 >> 2 = -1 (-0.75)
-4 >> 2 = -1
-5 >> 2 = -1 (-1.25)
-6 >> 2 = -1 (-1.5)
-7 >> 2 = -2 (-1.75)
...
-12 >> 3 = -1 (-1.5)
-13 >> 3 = -2 (-1.625)

与标准ASR指令的差异 #

本算法行为和多数硬件ASR指令不同：

• 正数输入：标准ASR直接截断小数（如7 ASR 2 = 1），本算法需按规则四舍五入
• 负数输入：标准ASR向负无穷舍入（如-7 ASR 1 = -4），本算法结果与正数关于零对称
• 特殊循环：标准ASR存在-1 ASR 1 = -1的循环行为，本算法无此问题

算法实现 #

核心思路 #

通过给原数添加符号相关的偏移量，再执行算术右移，实现符合要求的舍入：

1. 当n=0时，直接返回原数（无移位）
2. 当n≥32时，返回0（32位整数除以2^32的绝对值≤0.5，向零舍入为0）
3. 正数偏移量：(1 << (n-1)) - 1，确保小数部分≥0.5时进位，恰好0.5时不进位
4. 负数偏移量：1 << (n-1)，确保小数部分≤-0.5时向零舍入

C语言代码实现 #

int asrz(int x, int n) {
    if (n == 0) {
        return x;
    }
    if (n >= 32) {
        return 0;
    }
    const int shift = n - 1;
    const int offset = x >= 0 ? ((1 << shift) - 1) : (1 << shift);
    return (x + offset) >> n;
}

指令集适配说明 #

所有操作仅使用位运算、加法、条件分支，完全符合Cortex-M0指令集限制：

• 无浮点/除法/取模指令
• 位运算（<<、>>）、加法均为单周期指令
• 条件分支仅需少量指令开销

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