Как реализовать арифметическое смещение вправо в C

Question

Многие алгоритмы без потерь в обработке сигналов требуют оценки выражения в форме a / 2 ^b, где a, b - целые числа со знаком (возможно, отрицательные, b неотрицательные), а ⌊·⌋ - функция этажа. Это обычно приводит к следующей реализации.

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

К сожалению, стандарт C гласит, что результат >> Оператор определяется реализацией, если левый операнд имеет тип со знаком и отрицательное значение.

Чтобы обеспечить правильное поведение на всех платформах, можно заменить эту простую функцию несколькими условиями if-else, что приведет к снижению производительности программы. (Необходимо обработать переполнение целого числа и рассмотреть случай, когда numerator является INT_MIN.)

Поэтому я спрашиваю, какова лучшая практика для реализации арифметического сдвига вправо в C? В идеале я ищу конструкцию, которая компилируется в тот же код ^1, что и фрагмент кода выше, избегая поведения, определенного реализацией.

^{1 с} учетом, например, платформы gcc и x86-64

ОБНОВИТЬ:

Подумав, я понял, что неправильно сформулировал этот вопрос. Вычисление функции этажа для отрицательных чисел с использованием арифметического сдвига не имеет смысла, если платформа не использует дополнение до двух. Цель состоит в том, чтобы реализовать выражение " a / 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 < 0 затем ~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

Answer 2

Когда -нибудь на раннем этапе выполнения вы могли проверить разумность вашего предположения

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