如何实现算术右移从逻辑移位

Question

我需要在逻辑移位、and、or、xor和普通整数算术运算中实现32位算术右移。

我在什么地方读到下面的应该是工作的:

(x>>N)|(((1<<N)-1)<<(32-N))

x是要移位的整数，N是要移位的位数。

这适用于负数(msb为1)，但不适用于正数(msb为0)。

有谁知道一个总是产生正确结果的有效算法吗?

Answer 1

你可以使用

(x >> N) | (-(x < 0) << (32 - N))

如果x为负，则-(x < 0)返回-1，其位模式为所有1s，假设2为补码。-1 << (32 - N)将生成一个值，其中前N位全部为1，其余部分为0。如果x是非负的，那么后面的部分将始终为零，结果将与逻辑移位相同。也可以修改为

(x >> N) | ~(((x < 0) << (32 - N)) - 1)

请注意，对于N <= 0或N>= 32不起作用(因为移动超过type的宽度会调用UB)，所以如果需要，您应该专门处理这些情况

如果您不允许使用比较，那么您可以将x < 0更改为(unsigned)x >> 31，并得到以下等效方法

(x >> N) | (-((unsigned)x >> 31) << (32 - N))
(x >> N) | ((~0*(unsigned)x >> 31) << (32 - N))
(x >> N) | ~((((unsigned)x >> 31) << (32 - N)) - 1)

Answer 2

LSR 1:

+---+---+---+---
|   |   |   | ...
+---+---+---+---
            
            
           
+---+---+---+---
| 0 |   |   | ...
+---+---+---+---

ASR 1:

+---+---+---+---
|   |   |   | ...
+---+---+---+---
  |         
  |         
  |        
+---+---+---+---
|   |   |   | ...
+---+---+---+---

一个ASR由一个LSR +一个OR组成。

---

你想复制bit31 N次。有效的解决方案可能是

的有效实现

( bit31 ? 0xFFFFFFFF : 0x00000000 ) << ( 32 - N ) )

我想到了

LSL(SUB(LSR(NOT(X), 31), 1), SUB(32, N))

整件事

OR(LSL(SUB(LSR(NOT(X), 31), 1), SUB(32, N)), LSR(X, N))

这似乎不是很有效。