算术右移整数，半舍入为零

Question

我正在寻找一种有效的算法，该算法可以计算整数的“算术右移”，该算法舍入到最接近的整数，并具有“半舍入到零”行为。答案可以是对此类算法或其实现的正确描述（例如在汇编或 C 中）。 你可以假设：

整数大小为 32 位

二进制补码格式用于表示负值

• 班次计数始终大于或等于零
“高效算法”要求在运行时间和空间复杂度之间进行合理的权衡。它归结为解决任务所需的最少指令，同时不需要过多的空间/数据来完成此任务。提出了
• Cortex-M0指令集
作为参考。特别是，它对解决方案设置了以下限制：没有浮点指令，没有整数除法指令，没有整数模指令。

这是C语言的原型： int asrz(int x, int n);

舍入方法详情

算法应该计算

Y = X >> N

使用以下舍入行为对整数值：

真实结果四舍五入为最接近的整数。作为打破平局的规则，如果小数部分为 0.5，则四舍五入为零。以下是一些例子：

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 指令不同：

对于正输入值，不会四舍五入到最接近的值，而是去掉小数部分（例如 7 ASR 2 = 1）

对于负输入值，四舍五入为 -无穷大（例如 -7 ASR 1 = -4）。

• 有一个循环：-1 ASR 1 = -1
据我所知，在具有进位标志的架构上最简单的方法是将右移的进位添加到结果中：

Answer 1

这可以很好地移植到 ARM，尽管在 ARM64 和没有进位标志（例如 RISC-V）的架构上，这样做比较烦人。 您必须手动计算进位，然后将其相加。