如何以便携的方式在C语言中执行算术右移？

Question

我们正在编写一个模拟器，需要进行右移符号扩展。被模拟的系统使用二进制补码表示数字。

我了解到，在C语言中，带符号整数的 >>运算符是实现定义的。因此我不能依赖于这个事实，以保证在所有平台上都会得到正确的位模式。

这意味着我需要使用位操作来重现算术右移，而且如果可能的话，我想避免不必要的分支。

编辑：

响应评论：

“OP需要定义当x和y都为正数时结果是什么。”

我基本上想要复制SAR x86指令的行为。在那里，负数使用二进制补码表示。对于负数，右移应该基本上意味着除以2。

这意味着对于以1开头的位模式。例如：1xxxxxxx，右移应该得到11xxxxxx。对于以0开头的位模式，例如：0xxxxxxx，右移应该得到00xxxxxx。所以最高有效位是“粘性的”。位移超过字长没有定义。

- Calmarius

---

你希望它做什么？ - Eugene Sh.

不要提负数的表示也是实现定义（虽然只有三种可能性，但还是...）。 - Eugene Sh.

更新后：检查MSB，进行无符号移位，将移入的位设置为MSB值。问题出在哪里？ - Eugene Sh.

@EugeneSh。我认为存在一些聪明的位操作技巧，没有人想到过...到目前为止，我正在进行检查MSB的操作，但是那个额外的分支让我感到困扰... - Calmarius

缺失的部分是OP需要定义当x中的符号位被设置为x >> y时，“正确”的结果是什么。 - chux - Reinstate Monica

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)。

使用有条件的无分支否定s^(s+x)或(x^s)-s可以模拟将整数乘以+/-1。当s为0时，不会发生任何事情，x保持不变，因此乘以1。当s为-1时，我们得到-x，因此乘以-1。

代码段的第一行-((unsigned) x >> 31)提取符号位。 这里，unsigned转换确保编译成逻辑右移（汇编中的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只有逻辑移位。

- Friedrich -- Слава Україні

---

我认为写x > 0比(unsigned) x >> 31更具可移植性，因为它不会硬编码假设int是32位宽度的。另外，比较操作不是分支操作，所以它很可能同样高效。事实上，我曾经看到编译器为x > 0和(unsigned) x >> 31生成相同的代码。 - undefined

@user16217248 非常有趣且易读的建议。我本来想说必须是 x<0 才能得到符号位。然而，在某些系统上，x>0 似乎也适用于 sar。但是，当 >> 用零填充时可能会失败（例如，在 C 中 -5>>1 得到 -3，但在 gnuplot v5.4 中得到 9223372036854775805）。因此，x<0 似乎更加稳健（可移植）。 - undefined

哎呀，我是说 x < 0。 - undefined

Answer 2

这里是针对gcc和clang的单指令解决方案，在-O1及以上优化级别下：

x < 0 ? ~(~x >> y) : x >> y

我用clang 8.01和gcc 8.1测试了这个代码，它们都将代码简化为单个 sar 指令。演示在这里。

该代码将问题分解为两个子问题的右移，每个子问题只涉及非负值。编译器将 ~(~x >> y) 子表达式优化为算术右移。然后编译器看到分支的 "then" 和 "else" 部分是相同的代码，并优化掉了分支。

- Arch D. Robison

Answer 3

如果您可以拥有特定于平台的代码，那么您可以测试现有的>>运算符（对于有符号整数可能会做您想要的事情，但很可能会扩展符号）。这是大多数平台上最简单和最有效的解决方案，因此如果可移植性是一个问题，我只会提供另一种解决方案作为后备。 （我不完全确定有没有好的方法用预处理器进行测试，所以测试需要进入构建解决方案。）

如果您想手动执行它，可以通过条件按位OR掩码高位，或在许多情况下：

#define asr(x, shift) ((x) / (1 << (shift)) // do not use as is, see below

使用除法解决问题的问题在于所需的最大除数无法用与x相同的已签名类型表示，因此您需要适当地为x的类型和必要的移位进行类型转换（例如首先转换为较大的类型，然后返回，因为结果将适合）。

这种解决方案是由二进制数移位等价于乘以和除以2的幂（在算术意义上）的事实引起的；这适用于模拟算术右移的除法，以及左移1以获得2的幂除数。

但是，在二进制补码机器上，它与符号扩展的右移不完全相等，特别是如果负的x的除法结果为零：真正的符号扩展移位应该在二进制补码机上给出-1（所有位都是1），这将成为一的互补。类似地，负结果可能会比负x少一个，这再次归因于二进制补码和一的互补之间的差异。我认为，除法给出了正确的算术结果，但它与符号扩展结果不匹配，因此可能不适用于仿真器。

- Arkku

Answer 4

为了做到可移植性并避免有符号整数右移的实现定义行为，所有移位操作都要使用unsigned类型进行。下面是对@harold答案的变异。它不会按位宽移位（这是未定义的行为），也不依赖于2的补码。没有分支。如果在一台罕见的不使用2的补码的机器上，可能会创建陷阱值。

#if INT_MAX == 0x7FFF && UINT_MAX == 0xFFFF
  #define W 16
#elif INT_MAX == 0x7FFFFFFF && UINT_MAX == 0xFFFFFFFF
  #define W 32
#else
  // Following often works
  #define W (sizeof (unsigned)*CHAR_BIT)
#endif

int TwosComplementArithmeticRightShift(int x, int shift) {
  unsigned ux = (unsigned) x;
  unsigned sign_bit = ux >> (W-1);
  y = (ux >> shift) | (((0-sign_bit) << 1) << (W-1-shift));
return y;
}

或者作为一行代码

  y = (((unsigned) x) >> shift) | (((0-(((unsigned) x) >> (W-1))) << 1) << (W-1-shift));

- chux - Reinstate Monica

Answer 5

这是一个简单的技巧，适用于所有有效的移位值：

// shift x right y bits (0..31) with sign replication */
uint32_t sar32(uint32_t x, uint32_t y) {
    uint32_t bottom = x >> y;
    uint32_t top = -((x & (1u << 31)) >> y);
    return top | bottom;
}

你可能希望定义移位计数大于或等于字长的行为：

// shift x right y bits with sign replication, intel behavior */
uint32_t sar32(uint32_t x, uint32_t y) {
    uint32_t bottom = x >> (y &= 31);
    uint32_t top = -((x & (1u << 31)) >> y);
    return top | bottom;
}

- chqrlie

Answer 6

将整数类型强制转换为更大的类型将会进行符号扩展。这样，我们可以通过将其转换为更大的类型、执行移位操作、然后截断和转换回来的方式，强制新的位成为符号扩展位而不是实现定义的位。

_Static_assert(sizeof(long)>sizeof(int), "sizeof(long) must be > sizeof(int)");
int SHR(int N, unsigned char I) {
    return (int)((long)N>>I);
}

这是一种相对简单和直观的方法，不需要太多的位运算，但前提是有更大的整数类型可用。

- user16217248

Answer 7

一种可能的方法是首先执行无符号右移，然后根据最高有效位的值对移位后的值进行符号扩展。利用当两个位 a 和 b 相加时，和位为 a ^ b，进位位为 a & b 的事实，我们可以用两种方式构建符号扩展。结果表明，使用基于和位的方法更有效。

下面的代码显示了算术右移的仿真作为函数 arithmetic_right_shift()，以及一个测试框架；T 是您希望操作的整数类型。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define T int
#define EXTEND_USING_CARRY_BIT  (1)
#define EXTEND_USING_SUM_BIT    (2)

#define SIGN_EXTEND_METHOD EXTEND_USING_SUM_BIT

T arithmetic_right_shift (T a, int s)
{
    unsigned T mask_msb = (unsigned T)1 << (sizeof(T) * CHAR_BIT - 1);
    unsigned T ua = a;
    ua = ua >> s;
    mask_msb = mask_msb >> s;
#if (SIGN_EXTEND_METHOD == EXTEND_USING_SUM_BIT) 
    return (T)((ua ^ mask_msb) - mask_msb);
#else // SIGN_EXTEND_METHOD
    return (T)(ua - 2 * (ua & mask_msb));
#endif // SIGN_EXTEND_METHOD
}

int sar_ref (int a, int s)
{
    int res;
    __asm mov eax, dword ptr [a];
    __asm mov ecx, s;
    __asm sar eax, cl;
    __asm mov dword ptr [res], eax;
    return res;
}

int main (void) 
{
    unsigned int x;
    int a, s, res, ref;

    s = 0;
    do {
        x = 0;
        do {
            a = (int)x;
            res = arithmetic_right_shift (a, s);
            ref = sar_ref (a, s);
            if (ref != res) {
                printf ("!!!! a=%08x s=%d  res=%08x  ref=%08x\n", 
                        a, s, res, ref);
                return EXIT_FAILURE;
            }
            x++;
        } while (x);
        s++;
    } while (s < 32);
    return EXIT_SUCCESS;
}

- njuffa

---

这个问题需要一种便携的方式——使用汇编语言可以说是最不便携的方式了！ - undefined

@Andrew 你在 arithmetic_right_shift() 函数中看到任何汇编代码吗？那是所要求的可移植代码。汇编语言仅在用于测试目的的参考函数中使用。 - undefined

Answer 8

我认为使用>>没有什么大问题，但如果你想要进行算术右移，那么你可以将数字除以2的x次方，其中x是你想要进行的右移量，因为将一个数字除以二等同于进行一次右移。

假设你想要进行a >> x。那么也可以通过执行a / (int)pow(2,x)来实现。其中pow(2,x)是数学上的幂运算，你也可以理解为2的x次方。

- Rakholiya Jenish

---

“pow”实际上是浮点数，对于这样一个简单的任务来说代价很高。它甚至可能不会像左移一样被编译器优化为常量 x。 - too honest for this site

对于有符号二进制补码数的右移相当于将其除以2的幂次方并向负无穷舍入。使用浮点单元进行此操作需要设置舍入模式为“向下舍入”。而且，这只适用于浮点尾数具有足够精度以精确表示值的情况。例如，IEEE FP64（通常实现的“double”类型）不适用于移位int64_t，因为FP64仅具有53位精度。 - Arch D. Robison

Answer 9

这个函数将会在任何机器定义'int'的情况下都能够工作，它通过移动绝对值（即没有符号）然后再加上符号来实现：

int shift(int value, int count)
{
  return ((value > 0) - (value < 0)) * (abs(value) >> count);
}

- JL. Sanchez

---

这在处理负值时无法正常工作。shift(-5,1) 的结果是 -2，而算术移位应该返回 -3。请参见此处 https://godbolt.org/z/u5jdTj。 - Friedrich -- Слава Україні