c - 如何以可移植的方式在 C 中执行算术右移？

Question

我们正在编写一个模拟器，我们需要符号传播右移。仿真系统使用 2 的补码。

我读到 C 中有符号整数的 >> 运算符是实现定义的。所以我不能相信它会在所有平台上产生正确的位模式这一事实。

这意味着我需要使用位操作来重现算术右移，并且我希望尽可能避免不必要的分支。

编辑:

回应评论:

"The missing bit is that OP needs to define what result is "correct" when the sign bit is set in x with x >> y"

我基本上想重现 SAR x86 指令的行为。负数用 2 的补码表示。右移基本上也意味着负数除以 2。

这意味着对于以 1 开头的位模式。因此对于 1xxxxxxx，右移应该得到 11xxxxxx。对于以 0 开头的位模式，因此 0xxxxxxx 右移应产生 00xxxxxx。所以 MSB 是“粘性的”。未定义超过字长的移位。

Answer 1

int s = -((unsigned) x >> 31);
int sar = (s^x) >> n ^ s;

这需要 5 个位运算。

解释

如前所述，算术右移 x >> n 对应于除法 x/2**n。如果系统只支持逻辑右移，则可以先将负数转换为正数，然后再将其符号复制回去 sgn(x) * (abs(x)/2**n)。这相当于在右移前后乘以+/-1 sgn(x) * ((sgn(x)*x)/2**n)。

将一个整数与 +/-1 相乘可以用条件无分支否定 s^(s+x) 或 (x^s)-s 来模拟。当 s 为 0 时，没有任何反应，x 保持不变，因此与 1 相乘。当 s 为 -1，我们得到-x，所以与-1相乘。

代码段的第一行 -((unsigned) x >> 31) 提取符号位。此处，unsigned 转换确保 compilation into a logical right shift (组装中的 SHR)。因此，立即数结果为0或1，取反后s为0或-1随心所欲。

通过移位前后的两个无分支否定，我们得到了 ((s^s+x) >> n) + s ^ s。这将执行除法并将结果四舍五入为零(例如 -5>>1 = -2)。但是，算术右移(汇编中的 SAR)会降低结果(即 -5>>1 = -3)。要实现这一行为，必须放弃 +s 操作。

演示在这里:https://godbolt.org/和 https://onlinegdb.com/Hymres0y8 .

PS:我到了这里，因为gnuplot只有逻辑移位。