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

Ответы:

97

Согласно K&R 2nd edition результаты зависят от реализации для сдвига вправо знаковых значений.

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

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

Ронни
источник
141

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

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

При сдвиге беззнакового значения оператор >> в 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);
Грег Хьюгилл
источник
57
Так близко, Грег. Ваше объяснение почти идеально, но смещение выражения типа со знаком и отрицательного значения определяется реализацией. См. Раздел 6.5.7 ISO / IEC 9899: 1999.
Robᵩ
12
@Rob: На самом деле, для сдвига влево и отрицательного числа со знаком поведение не определено.
JeremyP
5
Фактически, сдвиг влево также приводит к неопределенному поведению для положительных значений со знаком, если результирующее математическое значение (которое не ограничено размером в битах) не может быть представлено как положительное значение в этом типе со знаком. Суть в том, что вы должны действовать осторожно при сдвиге вправо значения со знаком.
Michael Burr
3
@supercat: я действительно не знаю. Однако я знаю, что есть документированные случаи, когда код с неопределенным поведением заставляет компилятор делать очень неинтуитивные действия (обычно из-за агрессивной оптимизации - например, см. Старую ошибку нулевого указателя в драйвере Linux TUN / TAP: lwn.net / Статьи / 342330 ). Если мне не нужна заливка знака при сдвиге вправо (что, как я понимаю, является поведением, определяемым реализацией), я обычно пытаюсь выполнить сдвиг битов, используя значения без знака, даже если это означает использование приведения для этого.
Майкл Берр
2
@MichaelBurr: Я знаю, что гипермодернистские компиляторы используют тот факт, что поведение, которое не было определено стандартом C (хотя оно было определено в 99% реализаций ), как оправдание для включения программ, поведение которых было бы полностью определено на всех платформы, на которых они могли бы работать, в бесполезные связки машинных инструкций без полезного поведения. Я признаю, однако (сарказм) меня озадачивает, почему авторы компиляторов упустили самую масштабную возможность оптимизации: опустить любую часть программы, которая, если она будет достигнута, приведет к
вложению
51

TL; DR

Считайте iи nлевым и правым операндами соответственно оператора сдвига; тип iпосле целочисленного продвижения быть T. Предполагая, nчто находится в [0, sizeof(i) * CHAR_BIT)- в противном случае undefined - мы имеем следующие случаи:

| 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                |

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


перевод

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

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

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

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

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

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

для X <0, X >> n = этаж (X ÷ 2 n )

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

37) 10 = 100 · 10 1) 2

37 ÷ 2 = 18,5

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

-37) 10 = 11011011) 2 (с учетом 8-битного представления с дополнением до двух)

-37 ÷ 2 = -18,5

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

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

Как отметил Гай Стил , это несоответствие привело к ошибкам в более чем одном компиляторе . Здесь неотрицательные (математические) могут быть сопоставлены с неотрицательными значениями без знака и со знаком (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 - E1 сдвинутые влево битовые позиции E2; освобожденные биты заполняются нулями. Если E1 имеет беззнаковый тип, значение результата будет E1 × 2 E2 , уменьшенное по модулю на единицу больше, чем максимальное значение, представленное в типе результата. Если E1 имеет тип со знаком и неотрицательное значение, а E1 × 2 E2 может быть представлен в типе результата, то это результирующее значение; в противном случае поведение не определено.

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

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

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

Сдвиг вправо

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

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

Вывод

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

legends2k
источник
1
Хороший ответ. Что касается округления (в разделе « Сдвиг» ) - сдвиг вправо округляет в сторону -Infкак отрицательных, так и положительных чисел. Округление положительного числа в сторону 0 - это частный случай округления в сторону -Inf. При усечении вы всегда отбрасываете положительно взвешенные значения, поэтому вы вычитаете из иначе точного результата.
ysap
1
@ysap Да, хорошее наблюдение. В основном, округление в сторону 0 для положительных чисел является частным случаем более общего округления в сторону −∞; это можно увидеть в таблице, где как положительные, так и отрицательные числа я отметил округлением до -∞.
legends2k
17

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

~0 >> 1

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

~0U >> 1;
Ник
источник
16

Вот функции, гарантирующие логический сдвиг вправо и арифметический сдвиг вправо для int в 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;
}
Джон Сципионе
источник
7

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

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

 x = 5
 x << 1
 x = 10 (x=5*2)
Срикант Патнаик
источник
В x >> a и x << a, если условие a> 0, тогда ответом будет x = x / 2 ^ a, x = x * 2 ^ a соответственно, тогда каков будет ответ, если a <0?
JAVA
@sunny: a не должно быть меньше 0. Это неопределенное поведение в C.
Джереми
4

Я поискал это в Википедии , и они сказали следующее:

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

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

Майк Стоун
источник
Хотя большинство компиляторов C использовали арифметический сдвиг влево для значений со знаком, такое полезное поведение, похоже, устарело. Существующая философия компилятора, по-видимому, предполагает, что выполнение левой переменной для переменной дает компилятору право предполагать, что переменная должна быть неотрицательной, и, таким образом, пропускает любой код в другом месте, который был бы необходим для правильного поведения, если переменная была отрицательной ,
supercat
0

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

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

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

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

asifaftab87
источник
0

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

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

Кристиан Ромо
источник
-1

GCC делает

  1. для -ve -> Арифметический сдвиг

  2. For + ve -> Logical Shift

Алок Прасад
источник
-7

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

  1. << это арифметический сдвиг влево или побитовый сдвиг влево.
  2. >> - арифметический сдвиг вправо или побитовый сдвиг вправо.
Сринат
источник
3
«Арифметический сдвиг вправо» и «побитовый сдвиг вправо» отличаются. В этом суть вопроса. Был задан вопрос: « >>Арифметический или побитовый (логический)?» Вы ответили " >>арифметически или поразрядно" Это не отвечает на вопрос.
wchargin
Нет, <<и >>операторы логические, а не арифметические
shjeff