Какой вид целочисленного деления со знаком соответствует битовому сдвигу?

Общеизвестно, что при делении целых чисел на степень двойки хороший компилятор сведет это к сдвигу битов.

Например:

int main(int argc, char **argv) {
    return argc/2;
}

Clang -O2 компилирует это в:

movl    %ecx, %eax
shrl    $31, %eax
addl    %ecx, %eax
sarl    %eax
retq

Стоит отметить, что хотя эта последовательность инструкций намного быстрее, чем фактическая инструкция деления, это не просто сдвиг на один бит, как можно было бы надеяться. Предположительно, это связано с тем, что типичные процессоры, наряду с C, в конечном итоге остановились на усеченном делении (частное округляется до нуля), и это происходит не совсем точно соответствует арифметическому сдвигу вправо (и для точного сохранения семантики требуется уменьшение силы).

Какая разновидность целочисленного деления со знаком будет точно соответствовать арифметическому сдвигу вправо?


c bit-manipulation bit-shift integer-division
person rwallace    schedule 21.07.2020    source источник

Ответы (1)


arrow_upward
5
arrow_downward

В случае, если выполняется арифметический сдвиг вправо, floor в степени 2 является наиболее подходящей операцией, которая соответствует сдвигу вправо целого числа со знаком (округление в сторону -inf).

Обратите внимание, что сдвиг вправо целого числа со знаком определяется реализацией. Это может быть либо арифметический сдвиг вправо (реализуемый большинством известных компиляторов), либо логический сдвиг вправо. Подробнее о разнице между этими двумя операциями можно узнать здесь.

Пример с арифметическим сдвигом вправо: https://godbolt.org/z/zhhfbc

#include <stdio.h>
#include <math.h>

int main(void)
{
    int val1 = 7;
    int val2 = -7;
    
    printf("Value1 = %.1lf\n", floor(val1/2.0));
    printf("Value2 = %.1lf\n", floor(val2/2.0));

    printf("Value1 = %d\n", val1 >> 1);
    printf("Value2 = %d\n", val2 >> 1);  

    return 0;
}

И вывод:

Value1 = 3.0

Value2 = -4.0

Value1 = 3

Value2 = -4
person Alex Lop.    schedule 21.07.2020
comment
Другими словами, округление до минус бесконечности. - person Nate Eldredge; 21.07.2020
comment
@NateEldredge Вероятно, округление до ближайшего целого числа было бы лучшей формулировкой. - person Alex Lop.; 21.07.2020
comment
@АлексЛоп. нет, правильный термин округляется в сторону -inf en.wikipedia.org/wiki/IEEE_754#Directed_roundings, en.wikipedia.org/wiki/ - person phuclv; 08.10.2020