8

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

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

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

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

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

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

更新：

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

4

2 回答 2

6 
#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的零翻转为一，这正是您想要的算术右移。

假设代码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
于 2018-12-13T17:02:16.033 回答
2

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

int check_sanity()
{
    if (~0ll != ~0ll>>8)
    {
        return 0; // not sane
    }
    return 1; // sane
}
于 2018-12-12T16:32:41.490 回答