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

Question

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

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

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

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

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

¹ с учетом,например, 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

This должен быть портативным, но я также не уверен, действительно ли он педантичен.Если это не так, вы можете #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
}