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

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

11.08.2008 08:55:13
В чем смысл арифметики и логики? Связанный вопрос для подписанных ints: stackoverflow.com/questions/4009885/…
Ciro Santilli 冠状病毒审查六四事件法轮功 9.08.2016 16:03:05
11 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

92
9.10.2016 17:43:54

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

(В качестве фона для тех читателей, которые не знакомы с разницей, «логический» сдвиг вправо на 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);
133
11.08.2008 09:16:34
Так близко, Грег. Ваше объяснение почти идеально, но смещение выражения со знаком и отрицательного значения определяется реализацией. См. ISO / IEC 9899: 1999, раздел 6.5.7.
Robᵩ 22.09.2008 22:53:15
@Rob: На самом деле, для левого сдвига и отрицательного числа со знаком поведение не определено.
JeremyP 4.04.2012 15:24:38
На самом деле, сдвиг влево также приводит к неопределенному поведению для положительных значений со знаком, если результирующее математическое значение (которое не ограничено размером в битах) не может быть представлено как положительное значение в этом типе со знаком. Суть в том, что вы должны действовать осторожно при смещении значения со знаком вправо.
Michael Burr 21.06.2013 00:30:20
@supercat: я действительно не знаю. Тем не менее, я знаю, что есть документированные случаи, когда код с неопределенным поведением заставляет компилятор делать не интуитивные вещи (обычно из-за агрессивной оптимизации - например, см. Ошибку нулевого указателя старого драйвера Linux TUN / TAP: lwn.net / Статьи / 342330 ). Если мне не нужно заполнение знака при сдвиге вправо (что, как я понимаю, является поведением, определяемым реализацией), я обычно стараюсь выполнять сдвиги битов, используя значения без знака, даже если это означает использование приведения для достижения этого.
Michael Burr 15.04.2015 07:11:15
@MichaelBurr: Я знаю, что гипермодернистские компиляторы используют тот факт, что поведение, которое не было определено стандартом C (хотя оно было определено в 99% реализаций ), в качестве оправдания для превращения программ, поведение которых было бы полностью определено на всех платформы, на которых они могли бы работать, на бесполезные связки машинных инструкций без полезного поведения. Я признаю, хотя (с сарказмом) я озадачен тем, почему авторы компилятора упустили самую массовую возможность оптимизации: пропустить любую часть программы, которая, если она будет достигнута, приведет к
supercat 15.04.2015 14:30:02

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

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

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

4
11.08.2008 09:18:52
Хотя большинство компиляторов Си раньше использовали арифметическое смещение влево для знаковых значений, такое полезное поведение, по-видимому, не рекомендуется. Существующая философия компилятора, по-видимому, предполагает, что выполнение левой переменной для переменной дает компилятору право предполагать, что переменная должна быть неотрицательной, и, таким образом, пропускает любой код в другом месте, который был бы необходим для правильного поведения, если переменная была отрицательной ,
supercat 16.04.2015 05:47:14

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

~0 >> 1

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

~0U >> 1;
17
13.08.2008 17:20:06

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

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

0
26.06.2017 13:44:50

Вот функции, гарантирующие логическое смещение вправо и арифметическое смещение вправо от целого числа в 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;
}
16
8.08.2015 18:28:47

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

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

 x = 5
 x << 1
 x = 10 (x=5*2)
6
6.09.2012 06:09:47
В x >> a и x << a, если условие a> 0, тогда ответ будет x = x / 2 ^ a, x = x * 2 ^ a соответственно, тогда каков будет ответ, если a <0?
JAVA 23.09.2013 13:51:35
@sunny: a не должно быть меньше 0. Это неопределенное поведение в C.
Jeremy 1.10.2014 20:52:18

По мнению многих компиляторов:

  1. << арифметический сдвиг влево или побитовый сдвиг влево.
  2. >> является арифметическим сдвигом вправо или побитовым сдвигом вправо.
-7
26.06.2017 13:45:07
«Арифметическое смещение вправо» и «побитовое смещение вправо» различны. В этом суть вопроса. Заданный вопрос: "Является ли >>арифметическим или побитовым (логическим)?" Вы ответили « >>арифметически или поразрядно». Это не отвечает на вопрос.
wchargin 8.01.2014 02:46:09
Нет, <<и >>операторы логичны, а не арифметичны
shjeff 10.04.2018 12:59:45

TL; DR

Рассмотрим 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; повышенный тип я


перевод

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

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

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

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

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

для X ≥ 0, X >> n = X / 2 n = усечение (X ÷ 2 n )

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

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

37) 10 = 100101) 2

37 ÷ 2 = 18,5

37/2 = 18 (округление 18,5 до 0) = 10010) 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 являются E1-сдвинутые вправо битовые позиции E2. Если E1 имеет тип без знака или если E1 имеет тип со знаком и неотрицательное значение, значение результата является неотъемлемой частью отношения E1 / 2 E2 . Если E1 имеет тип со знаком и отрицательное значение, результирующее значение определяется реализацией.

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

Заключение

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

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

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

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

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

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

0
26.06.2017 13:44:27

GCC делает

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

  2. For + ve -> Logical Shift

-1
9.02.2018 14:44:45