如何在C中实现算术右移 [英] How to implement arithmetic right shift in C

问题描述

信号处理中的许多无损算法都需要评估⌊ a  /  2 ^b 形式的表达式 ⌋，其中 a ， b 是带符号的( a 可能为负， b 为非负)整数和the·⌋是发言权功能.通常，这会导致以下实现.

Many lossless algorithms in signal processing require an evaluation of the expression of the form ⌊ a / 2^b ⌋, where a, b are signed (a possibly negative, b non-negative) integers and ⌊·⌋ is the floor function. This usually leads to the following implementation.

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

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

Unfortunately, the C standard states that the result of the >> operator is implementation-defined if the left operand has a signed type and a negative value.

为了确保在所有平台上的正确行为，可以用多个if-else条件替换此简单功能，从而导致较差的程序性能.(必须处理整数的溢出并考虑 numerator 为 INT_MIN 时的情况.)

To ensure the correct behaviour on all platforms, one could replace this simple function with multiple if-else conditions, resulting in poor program performance. (One must to treat an overflow of an integer and consider the case when the numerator is INT_MIN.)

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

Therefore I ask, what is the best practice for implementation of the arithmetic right shift in C? Ideally, I'm looking for the construct that compiles into the same code¹ as the code fragment above while avoiding the implementation-defined behaviour.

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

¹ considering, e.g., gcc and x86-64 platform

更新:

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

After some thought, I realized that I made an incorrect implication in the above question. Computing the floor function for negative numbers using an arithmetic shift doesn't make sense if the platform doesn't use two's complement. The goal is to implement the expression ⌊ a / 2^b ⌋ in a portable way.

推荐答案

#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 ;
}

此代码决定是否先使用内置的>> 运算符.您可能希望信任或不信任预处理器，从而为您提供与目标体系结构相同的结果，但是安全的后备状态是不信任它.

This code decides whether to just use the builtin >> operator or not first. You might want to either trust or not trust the preprocessor giving you the same result as the target architecture, but a safe fallback is to not trust it.

让我们解释值<0?〜(〜值>>数量):值>>金额部分.

1. 如果 value> = 0 ，那么>> 是逻辑还是算术都没关系，我们可以使用它.
2. 如果 value<0 ，然后〜value 是按位补码，它将是一个正数，并且(〜value>>数量)将是可移植的(顶部数量位数将被清除，其余按预期右移).
   〜(~~ value>>数量)将向后翻转所有位，包括将顶部的 amount 零从零翻转为1，这正是您希望算术正确的转移.

1. If value >= 0 then it doesn't matter whether >> is logical or arithmetic, we can use it.
2. If value < 0 then ~value is the bitwise complement which will be a positive number and (~value >> amount) will be portable (the top amount number of bits will be cleared, the rest shifted right as expected).
   ~(~value >> amount) will flip all the bits back, including flipping the top amount number of zeroes to ones which is exactly what you want with arithmetic right shifting.

假设 USES_ARITHMETIC_SHR(int)== true 的代码使用 -O2 编译为:

The code assuming USES_ARITHMETIC_SHR(int) == true compiles with -O2 into:

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 .但这会导致某些较旧的编译器的代码不那么理想.

This should be portable but I'm also unsure if it pedantically really is. If you aren't either, you can #define USES_ARITHMETIC_SHR(TYPE) false or just omit checking it and only check value < 0. But that results in less optimal code on the some older compilers.

最新版本的编译器(GCC 8 +，Clang 7+)将两个版本的 asr 和 asr2 编译为与上述相同的高效程序集，因此您可以使用任何版本的代码.下面是较老的编译器如何使用 asr2 (一种非常可移植的解决方案)进行的操作.

The newest version of the compilers (GCC 8+, Clang 7+) compile both versions, asr and asr2 to the same, efficient assembly as above, so you can use either versions of the code. Below is how older compilers do with asr2, a very portable solution.

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中实现算术右移的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！