如何在C中实现算术右移

Question

信号处理中的许多无损算法需要评估形式为 ⌊a / 2^{b 的表达式} ⌋，其中 a、b 有符号（a 可能为负数，b非负）整数，⌊·⌋是floor函数。这通常会导致以下实现。

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

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

为了确保在所有平台上的正确行为，可以用多个 if-else 条件替换这个简单的函数，从而导致程序性能不佳。（必须处理整数溢出并考虑 numerator 为 INT_MIN 的情况。）

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

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

更新：

经过一番思考，我意识到我在上述问题中提出了错误的暗示。如果平台不使用二进制补码，则使用算术移位计算负数的 floor 函数没有意义。目标是以可移植的方式实现表达式⌊a/2^b⌋。

Answer 1

在运行时的早期，您可以检查您的假设是否合理

int check_sanity()
{
    if (~0ll != ~0ll>>8)
    {
        return 0; // not sane
    }
    return 1; // sane
}

Answer 2

#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 部分。

如果value >= 0那么不管>>是逻辑还是算术，我们都可以使用它。
如果 value < 0 那么 ~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

如何在C中实现算术右移

How to implement arithmetic right shift in C

c

bit-manipulation

bit-shift

integer-arithmetic

signed-integer