如何以可移植的方式在C中执行算术右移? [英] How can I perform arithmetic right shift in C in a portable way?

问题描述

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

We are writing an emulator where we need sign propagating right shift. The emulated system uses 2's complement numbers.

我读到C中有符号整数的>>运算符是实现定义的.因此，我不能依靠它会在所有平台上产生正确的位模式这一事实.

I read that the >> operator on signed integers in C is implementation defined. So I cannot rely on the fact it will result in the correct bit pattern in all platforms.

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

This means I'll need to use bit manipulation to reproduce the arithmetic right shift, and I would want to avoid unnecessary branching if possible.

针对评论:

缺少的一点是，OP需要定义什么结果是正确的" 当x设置为x >> y时，将符号位设置为x"

"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.

I basically want to reproduce the SAR x86 instruction's behavior. There the negative numbers are represented using 2's complement. The right shift should basically mean division by 2 for negative numbers too.

这意味着对于以1开头的位模式，因此对于1xxxxxxx，向右移位应为11xxxxxx.对于以0开头的位模式，因此0xxxxxxx右移应为00xxxxxx.因此，MSB是粘性"的.没有定义超过字长的移位.

This means for bit patterns starting with 1. So for 1xxxxxxx, a right shift with should result 11xxxxxx. For bit patterns starting with 0, so 0xxxxxxx right shift should result in 00xxxxxx. So MSB is "sticky". Shifting by more than word length is not defined.

推荐答案

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

这需要进行5次按位运算.

This requires 5 bitwise operations.

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

As already mentioned, an arithmetic right shift x >> n corresponds to the division x / 2**n. In case the system supports only logical right shift, a negative number can be first converted into a positive number and then its sign is copied back afterwards sgn(x) * (abs(x)/2**n). This is equivalent to multiply with +/-1 before and after the right shift sgn(x) * ((sgn(x)*x)/2**n).

可以使用条件无分支取反s^(s+x)或(x^s)-s模拟将+/- 1整数相乘.当s是0时，什么都不会发生，并且x保持不变，因此与1进行乘法.当s是-1时，我们获得-x，因此与-1进行乘法.

Multiplying an integer with +/-1 can be emulated with the conditional branchless negation s^(s+x) or (x^s)-s. When s is 0, nothing happens and x remains unchanged, so a multiplication with 1. When s is -1, we obtain -x, so a multiplication with -1.

摘要的第一行-((unsigned) x >> 31)提取符号位. 在这里，unsigned转换可确保编译为逻辑右移(汇编中的SHR).因此，立即结果为0或1，并且取反后s为0或-1.

The first line of the snippet, -((unsigned) x >> 31), extracts the sign bit. Here, the unsigned conversion ensures compilation into a logical right shift (SHR in assembly). Therefore, the immediate result is 0 or 1, and after the negation s is 0 or -1 as desired.

在移位前后有两个无分支的求反，我们得出((s^s+x) >> n) + s ^ s.这会执行除法，并将结果舍入为零(例如-5>>1 = -2).但是，算术右移(汇编中的SAR)限制了结果(即-5>>1 = -3).要实现此行为，必须放弃+s操作.

With two branchless negations before and after the shift, we arrive at ((s^s+x) >> n) + s ^ s. This performs a division with rounding the result towards zero (e.g. -5>>1 = -2). However, an arithmetic right shift (SAR in assembly) floors the result (i.e. -5>>1 = -3). To achieve this behaviour, one has to drop the +s operation.

一个演示在这里: PS:我到达这里是因为gnuplot只有逻辑上的偏移.

PS: I arrived here, because gnuplot has only logical shifts.

这篇关于如何以可移植的方式在C中执行算术右移?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！