Являются ли операторы сдвига (<<, >>) арифметическими или логическими в C?
В С операторы сдвига (<<, >>арифметический или логический?
11 ответов
Согласно K&R 2nd edition, результаты зависят от реализации правильных сдвигов подписанных значений.
Википедия говорит, что C/C++ "обычно" реализует арифметический сдвиг в знаковых значениях.
По сути, вам нужно либо протестировать свой компилятор, либо не полагаться на него. Моя справка VS2008 для текущего компилятора MS C++ говорит, что их компилятор выполняет арифметическое изменение.
При сдвиге влево нет разницы между арифметическим и логическим сдвигом. При смещении вправо тип смещения зависит от типа смещаемого значения.
(В качестве фона для тех читателей, которые не знакомы с разницей, "логический" сдвиг вправо на 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);
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++ имеют только арифметическое смещение с некоторыми областями, оставленными неопределенными и определяемыми реализацией. Причина, по которой я считаю их арифметическими, связана со стандартной математической формулировкой операции, а не с обработанным сдвинутым операндом как потоком битов; возможно, это причина того, что эти области не определяются / не определяются реализацией, вместо того, чтобы просто определять все случаи как логические сдвиги.
Вот функции, гарантирующие логическое смещение вправо и арифметическое смещение вправо от целого числа в 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;
}
С точки зрения типа сдвига, который вы получаете, важным является тип значения, которое вы сдвигаете. Классический источник ошибок - это когда вы переводите литерал, скажем, для маскировки битов. Например, если вы хотите удалить самый левый бит целого числа без знака, то вы можете попробовать это в качестве маски:
~0 >> 1
К сожалению, это доставит вам неприятности, потому что в маске будут установлены все биты, потому что смещаемое значение (~0) подписано, поэтому выполняется арифметическое смещение. Вместо этого вы захотите вызвать логический сдвиг, явно объявив значение как unsigned, то есть сделав что-то вроде этого:
~0U >> 1;
Когда вы делаете - сдвиг влево на 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 не имеет стандарта, по крайней мере, если это разумно и возможно избежать такой зависимости.
gcc обычно будет использовать логические сдвиги для переменных без знака и для сдвигов влево для переменных со знаком. Арифметическое смещение вправо является действительно важным, потому что оно будет подписывать расширение переменной.
gcc будет использовать это, когда это применимо, как и другие компиляторы.
Сдвиг влево <<
Это как-то легко, и всякий раз, когда вы используете оператор сдвига, это всегда побитовая операция, поэтому мы не можем использовать ее с операциями типа double и float. Всякий раз, когда мы оставляем сдвиг на один ноль, он всегда добавляется к младшему значащему биту (LSB).
Но в правую смену >> мы должны следовать одному дополнительному правилу, и это правило называется "знаковая битовая копия". Значение "знакового бита", если самый значимый бит (MSB) устанавливается после правого сдвига снова MSB будет установлен, если он был сброшен, то он снова сброшен, означает, что если предыдущее значение было равно нулю, то после повторного сдвига бит равен нулю, если предыдущий бит был равен единице, а после сдвига он снова равен единице. Это правило не применимо для левого смещения.
Самый важный пример для правого сдвига, если вы сдвинете любое отрицательное число к правому сдвигу, то после некоторого сдвига значение, наконец, достигнет нуля, а затем после этого, если сдвинуть это -1, любое число раз, значение останется тем же. Пожалуйста, проверьте.
GCC делает
для -ve - > Арифметический сдвиг
For +ve -> Logical Shift
По мнению многих c компиляторов:
<<арифметический сдвиг влево или побитовый сдвиг влево.>>является арифметическим сдвигом вправо или побитовым сдвигом вправо.