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

Question

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

Answer 1

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

(В качестве фона для тех читателей, которые не знакомы с разницей, «логический» сдвиг вправо на 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);

Answer 2

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

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

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

Answer 3

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                |

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

---

Перемена

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

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

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

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

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

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

для X <0, X >> n = этаж (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 является E1-сдвинутая влево позиция E2; освобожденные биты заполнены нулями. Если E1 имеет тип без знака, значением результата будет E1 × 2 <sup>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 ++ есть только арифметическое смещение, при этом некоторые области остаются неопределенными и определяются реализацией. Причина, по которой я считаю их арифметическими, связана со стандартной математической формулировкой операции, а не с обработанным сдвинутым операндом как потоком битов; возможно, это причина того, что эти области не определяются / не определяются реализацией, а не просто определяются все случаи как логические сдвиги.

Answer 4

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

~0 >> 1

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

~0U >> 1;

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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

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

Answer 8

GCC делает

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

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

Answer 9

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

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

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

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

Answer 10

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

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