Являются ли операторы сдвига (<<, >>) арифметическими или логическими в C?

https://stackoverflow.com/questions/7622

08-06-2019
|

Вопрос

В C операторы сдвига (<<, >>) арифметический или логический?

Решение

В соответствии с К&Р 2-е издание результаты зависят от реализации для сдвигов вправо значений со знаком.

Википедия говорит, что C/C++ «обычно» реализует арифметический сдвиг знаковых значений.

По сути, вам нужно либо протестировать свой компилятор, либо не полагаться на него.В моей справке VS2008 для текущего компилятора MS C++ говорится, что их компилятор выполняет арифметический сдвиг.

Другие советы

При сдвиге влево нет разницы между арифметическим и логическим сдвигом.При сдвиге вправо тип сдвига зависит от типа смещаемого значения.

(Для справки для тех читателей, кто не знаком с этой разницей: «логический» сдвиг вправо на 1 бит смещает все биты вправо и заполняет самый левый бит 0.«Арифметический» сдвиг оставляет исходное значение в крайнем левом бите.Разница становится важной при работе с отрицательными числами.)

При сдвиге беззнакового значения оператор >> в C выполняет логический сдвиг.При сдвиге значения со знаком оператор >> выполняет арифметический сдвиг.

Например, если предположить, что машина 32-битная:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);

ТЛ;ДР

Учитывать i и n быть левым и правым операндами оператора сдвига соответственно;тип i, после целочисленного продвижения, будет T.Предполагая n Быть в [0, sizeof(i) * CHAR_BIT) — в противном случае не определено — у нас есть такие случаи:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined†  |
| Left  (<<) | unsigned |    ≥ 0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |    ≥ 0    | (i * 2ⁿ) ‡               |
| Left       | signed   |    < 0    | Undefined                |

^{† большинство компиляторов реализуют это как арифметический сдвиг}
^{‡ не определено, если значение выходит за пределы типа результата T;продвинутый тип i}

Переключение

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

Другими словами, логический сдвиг рассматривает сдвинутый операнд как просто поток битов и перемещает их, не заботясь о знаке результирующего значения.Арифметический сдвиг рассматривает его как число (со знаком) и сохраняет знак при выполнении сдвигов.

Арифметический сдвиг влево числа X на n эквивалентен умножению X на 2.^н и, таким образом, эквивалентно логическому сдвигу влево;логический сдвиг также даст тот же результат, поскольку MSB все равно отваливается от конца и сохранять нечего.

Арифметический сдвиг вправо числа X на n эквивалентен целочисленному делению X на 2.^н ТОЛЬКО если X неотрицательно!Целочисленное деление – это не что иное, как математическое деление. круглый к 0 (ствол).

Для отрицательных чисел, представленных кодировкой с дополнением до двух, сдвиг вправо на n бит приводит к математическому делению их на 2.^н и округление в сторону −∞ (пол);таким образом, сдвиг вправо различен для неотрицательных и отрицательных значений.

для X ≥ 0, X >> n = X/2^н = trunc(X ÷ 2^н)

для X < 0, X >> n = Floor(X ÷ 2^н)

где ÷ это математическое деление, / это целочисленное деление.Давайте посмотрим на пример:

37)₁₀ = 100101)₂

37 ÷ 2 = 18.5

37/2 = 18 (округление 18,5 в сторону 0) = 10010)₂ [результат арифметического сдвига вправо]

-37)₁₀ = 11011011)₂ (учитывая дополнение до двух, 8-битное представление)

-37 ÷ 2 = -18.5

-37/2 = -18 (округление 18,5 в сторону 0) = 11101110)₂ [НЕ результат арифметического сдвига вправо]

-37 >> 1 = -19 (округление 18,5 в сторону −∞) = 11101101)₂ [результат арифметического сдвига вправо]

Как Гай Стил отметил, это несоответствие привело к ошибки более чем в одном компиляторе.Здесь неотрицательные (математические) значения могут быть сопоставлены с неотрицательными значениями без знака и со знаком (C);оба обрабатываются одинаково, и их сдвиг вправо осуществляется путем целочисленного деления.

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

Типы операндов и результатов

Стандарт C99 §6.5.7:

Каждый из операндов должен иметь целочисленный тип.

Целочисленные повышения выполняются для каждого из операндов.Тип результата соответствует расширенному левому операнду.Если значение правого операнда отрицательное или больше или равно ширине повышенного левого операнда, поведение не определено.

short E1 = 1, E2 = 3;
int R = E1 << E2;

В приведенном выше фрагменте оба операнда становятся int (из-за целочисленного продвижения);если E2 был отрицательным или E2 ≥ sizeof(int) * CHAR_BIT тогда операция не определена.Это связано с тем, что сдвиг большего количества битов, чем доступно, наверняка приведет к переполнению.Имел R был объявлен как short, int результат операции сдвига будет неявно преобразован в short;сужающее преобразование, которое может привести к поведению, определяемому реализацией, если значение не представляется в целевом типе.

Левый "шифт

Результатом E1 << E2 являются позиции битов E2, сдвинутые влево для E1;освободившиеся биты заполняются нулями.Если E1 имеет беззнаковый тип, значение результата равно E1×2.^Е2, уменьшенное по модулю на единицу больше, чем максимальное значение, представленное в типе результата.Если E1 имеет знаковый тип и неотрицательное значение, а E1×2^Е2 представимо в типе результата, то это и есть результирующее значение;в противном случае поведение не определено.

Поскольку сдвиги влево одинаковы для обоих, освободившиеся биты просто заполняются нулями.Затем он утверждает, что как для беззнаковых, так и для знаковых типов это арифметический сдвиг.Я интерпретирую это как арифметический сдвиг, поскольку логические сдвиги не заботятся о значении, представленном битами, они просто рассматривают его как поток битов;но стандарт говорит не в битах, а определяя его в терминах значения, полученного произведением E1 на 2.^Е2.

Предостережение здесь заключается в том, что для знаковых типов значение должно быть неотрицательным, а результирующее значение должно быть представлено в результирующем типе.В противном случае операция не определена. Тип результата будет типом E1 после применения интегрального продвижения, а не типом назначения (переменная, которая будет содержать результат).Результирующее значение неявно преобразуется в целевой тип;если он непредставим в этом типе, то преобразование определяется реализацией (C99 §6.3.1.3/3).

Если E1 — знаковый тип с отрицательным значением, то поведение смещения влево не определено. Это простой путь к неопределенному поведению, которое можно легко упустить из виду.

Правый сдвиг

Результатом E1 >> E2 является сдвиг битов E2 вправо.Если E1 имеет беззнаковый тип или если E1 имеет знаковый тип и неотрицательное значение, значение результата является целой частью частного E1/2.^Е2.Если E1 имеет знаковый тип и отрицательное значение, результирующее значение определяется реализацией.

Сдвиг вправо для беззнаковых и знаковых неотрицательных значений довольно прост;свободные биты заполняются нулями. Для отрицательных значений со знаком результат смещения вправо определяется реализацией. Тем не менее, большинство реализаций, таких как GCC и Визуальный С++ реализовать сдвиг вправо как арифметический сдвиг, сохраняя знаковый бит.

Заключение

В отличие от Java, в которой есть специальный оператор >>> для логического отхода от обычного >> и <<, C и C++ имеют только арифметический сдвиг, при этом некоторые области остаются неопределенными и определяются реализацией.Причина, по которой я считаю их арифметическими, связана со стандартной формулировкой операции математически, а не с трактовкой сдвинутого операнда как потока битов;Возможно, это причина, по которой эти области остаются неопределенными/реализация вместо того, чтобы просто определять все случаи как логические сдвиги.

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

~0 >> 1

К сожалению, это создаст вам проблемы, поскольку в маске будут установлены все биты, поскольку смещаемое значение (~0) подписано, поэтому выполняется арифметический сдвиг.Вместо этого вы захотите вызвать логический сдвиг, явно объявив значение как беззнаковое, т.е.сделав что-то вроде этого:

~0U >> 1;

Вот функции, гарантирующие логический сдвиг вправо и арифметический сдвиг вправо целого числа в C:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}

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

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)

Ну, я посмотрел это есть в википедии, и им есть что сказать:

C, однако, имеет только один оператор правой смены, >>.Многие компиляторы C выбирают, какой правильный сдвиг выполнять в зависимости от того, какой тип целого числа смещается;Часто подписанные целые числа смещаются с использованием арифметического сдвига, а не знаковые целые числа смещаются с использованием логического сдвига.

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

Левый "шифт <<

Это довольно просто, и всякий раз, когда вы используете оператор сдвига, это всегда побитовая операция, поэтому мы не можем использовать его с операциями double и float.Всякий раз, когда мы сдвигаем влево один ноль, он всегда добавляется к младшему биту (LSB).

Но в правую смену >> мы должны следовать еще одному правилу, и это правило называется «копией знакового бита».Значение «копии знакового бита» заключается в том, что самый старший бит (MSB) устанавливается, то после сдвига вправо снова MSB будет установлен, если он был сброшен, то он снова сбрасывается, означает, что если предыдущее значение было нулевым, то после повторного сдвига бит равен нулю, если предыдущий бит был единицей, то после сдвига он снова становится единицей.Это правило не применимо для смещения влево.

Самый важный пример сдвига вправо: если вы сдвинете любое отрицательное число на сдвиг вправо, то после некоторого сдвига значение, наконец, достигнет нуля, а затем после этого, если сдвинуть это -1 любое количество раз, значение останется прежним.Пожалуйста, проверьте.

GCC обычно используются логические сдвиги для беззнаковых переменных и сдвиг влево для знаковых переменных.Арифметический сдвиг вправо действительно важен, поскольку он расширяет знак переменной.

GCC will будет использовать это, когда это применимо, как, вероятно, сделают другие компиляторы.

GCC делает

для -ve -> Арифметический сдвиг
Для +ve -> Логический сдвиг

По мнению многих с составители:

<< представляет собой арифметический сдвиг влево или побитовый сдвиг влево.
>> — арифметический сдвиг вправо или побитовый сдвиг вправо.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow