Операторы сдвига (


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

11 102

11 ответов:

по данным K&R 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);

TL; DR

считают i и n быть левым и правым операндами соответственно оператора сдвига; тип i, после целочисленного продвижения, be 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, тем самым сохраняя знак операнда (предполагая a дополнение кодировка для отрицательных значений).

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

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

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

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

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

для X > n = пол(X ÷ 2n)

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

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 [не результат арифметики справа shift]

-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 имеет знаковый тип и неотрицательное значение, и E1×2E2 представляется в типе результата, то есть результирующее значение; в противном случае поведение не определено.

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

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

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

Сдвиг Вправо

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

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

вывод

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

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

~0 >> 1

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

~0U >> 1;

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

когда вы делаете - сдвиг влево на 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 не имеет стандарта, по крайней мере, если это разумно и возможно избежать такой зависимости.

сдвиг влево <<

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

но в сдвиг вправо >> мы должны следовать одному дополнительному правилу, и это правило называется "sign bit copy". Значение "sign bit copy" - это если самый значительный бит (MSB) устанавливается после правой смены снова MSB будет установлен, если он был сброшен, то он снова сброшен, означает, что если Предыдущее значение было равно нулю, то после сдвига снова бит равен нулю, если предыдущий бит был один, то после сдвига он снова один. Это правило не применимо для сдвига влево.

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

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

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

GCC выполняет

  1. for-ve - > арифметический сдвиг

  2. для +ve - > логический сдвиг

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

  1. << - арифметический сдвиг влево или побитовый сдвиг влево.
  2. >> - это арифметический сдвиг вправо побитового сдвига вправо.