如何在C中实现算术右移

Question

在信号处理许多无损算法需要的形式⌊的表达的评估  一个  / 2 ^b  ⌋,其中一个,b是签名(一个可能为负,b非负)的整数和⌊·⌋是地板函数.这通常会导致以下实施.

int floor_div_pow2(int numerator, int log2_denominator)
{
    return numerator >> log2_denominator;
}

不幸的是,C标准规定>>如果左操作数具有有符号类型和负值,则运算符的结果是实现定义的.

为了确保所有平台上的正确行为,可以用多个if-else条件替换这个简单的函数,从而导致程序性能不佳.(必须有人来治疗的整数溢出和考虑的情况下,当numerator为INT_MIN.)

因此,我想问一下,在C中实现算术右移的最佳实践是什么？理想情况下,我正在寻找与上面的代码片段编译成相同代码¹的构造,同时避免实现定义的行为.

¹考虑例如gcc和x86-64平台

更新:

经过一番思考,我意识到我在上面的问题中做了不正确的暗示.如果平台不使用二进制补码,则使用算术移位计算负数的基函数是没有意义的.我们的目标是实现表达⌊  一个  / 2 ^b  ⌋在便携式方式.

Answer 1

#define USES_ARITHMETIC_SHR(TYPE) ((TYPE)(-1) >> 1 == (TYPE)(-1))

int asr(int value, int amount) /* Better codegen on some older compilers */
{
    return !USES_ARITHMETIC_SHR(int) && value < 0 ? ~(~value >> amount) : value >> amount ;
}

int asr2(int value, int amount) /* Completely portable */
{
    return value < 0 ? ~(~value >> amount) : value >> amount ;
}

此代码决定是否首先使用内置>>运算符。您可能希望信任或不信任预处理器为您提供与目标架构相同的结果，但安全的回退是不信任它。

让我们解释一下value < 0 ? ~(~value >> amount) : value >> amount部分。

1. 如果value >= 0那么无论>>是逻辑还是算术都无关紧要，我们可以使用它。
2. 如果value < 0then~value是按位补码，它将是一个正数并且(~value >> amount)将是可移植的（顶部amount的位数将被清除，其余的按预期右移）。
   ~(~value >> amount)将翻转所有位，包括将最高amount数量的零翻转为 1，这正是您想要的算术右移。

代码假设USES_ARITHMETIC_SHR(int) == true编译-O2为：

asr(int, int): // x86-64 GCC 4.4.7
    mov     eax, edi
    mov     ecx, esi
    sar     eax, cl
    ret
asr(int, int): // x86-64 Clang 3.4.1
    mov     cl, sil
    sar     edi, cl
    mov     eax, edi
    ret
asr(int, int): // ARM GCC 4.5.4
    mov     r0, r0, asr r1
    bx      lr

这应该是便携的，但我也不确定它是否真的是迂腐。如果你不是，你可以#define USES_ARITHMETIC_SHR(TYPE) false或只是省略检查它，只检查value < 0. 但这会导致在某些较旧的编译器上的最佳代码较少。

最新版本的编译器（GCC 8+、Clang 7+）编译这两个版本，asr并编译为与asr2上述相同的高效程序集，因此您可以使用任一版本的代码。下面是旧编译器如何处理asr2，这是一个非常便携的解决方案。

asr2(int, int): // x86-64 GCC 4.4.7
    test    edi, edi
    js      .L8
    mov     eax, edi
    mov     ecx, esi
    sar     eax, cl
    ret
  .L8:
    mov     eax, edi
    mov     ecx, esi
    not     eax
    sar     eax, cl
    not     eax
    ret
asr2(int, int): // x86-64 Clang 3.4.1
    mov     cl, sil
    sar     edi, cl
    mov     eax, edi
    ret
asr2(int, int): // ARM GCC 4.5.4
    cmp     r0, #0
    mvnlt   r0, r0
    mvnlt   r0, r0, asr r1
    movge   r0, r0, asr r1
    bx      lr