Арифметический сдвиг - Arithmetic shift

Правый арифметический сдвиг двоичного числа на 1. Пустая позиция в старшем разряде заполняется копией исходного MSB.
Левый арифметический сдвиг двоичного числа на 1. Пустая позиция в младшем разряде заполняется нулем.
Операторы арифметического сдвига в различных языках программирования и процессорах
Язык или процессор Левый Правильно
ActionScript 3, Java , JavaScript , Python , PHP , Ruby ;
C , C ++ , D , C # , Go , Julia , Swift (только для подписанных типов)
<< >>
Ада Shift_Left Shift_Right_Arithmetic
Котлин shl shr
Стандартный ML << ~>>
Verilog <<< >>>
OpenVMS Макроязык @
Схема arithmetic-shift
Common Lisp ash
OCaml lsl asr
Haskell Data.Bits.shift
Сборка, 68к ASL ASR
Сборка, x86 SAL SAR
VHDL sla sra
RISC-V sll, slli sra, srai
Z80 SLA SRA

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

Некоторые авторы предпочитают термины липкие сдвиг вправо и вправо с заполнением нулями сдвига для арифметических и логических сдвигов соответственно.

Арифметические сдвиги могут быть полезны как эффективные способы выполнения умножения или деления целых чисел со знаком на степени двойки. Сдвиг влево на n бит для двоичного числа со знаком или без знака приводит к его умножению на 2 n . Сдвиг вправо на п бит на величинуХ дополнения до двух Подписанные двоичное число имеет эффект деления его на 2 п , но она всегда округляет вниз (к отрицательной бесконечности). Это отличается от способа округления, который обычно выполняется при целочисленном делении со знаком (которое округляется до 0). Это несоответствие привело к ошибкам в ряде компиляторов.

Например, в наборе команд x86 инструкция SAR (арифметический сдвиг вправо) делит число со знаком на степень двойки, округляя в сторону отрицательной бесконечности. Однако инструкция IDIV (разделение со знаком) делит число со знаком, округляя его до нуля. Таким образом, инструкция SAR не может быть заменена IDIV инструкцией степени двойки или наоборот.

Формальное определение

Формальное определение арифметического сдвига из Федерального стандарта 1037C состоит в том, что это:

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

Важное слово в определении FS 1073C - «обычно».

Эквивалентность арифметических и логических сдвигов влево и умножения

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

Неэквивалентность арифметического сдвига и деления вправо

Однако арифметические сдвиги вправо являются серьезной ловушкой для неосторожных, особенно при обработке округления отрицательных целых чисел. Например, в обычном представлении отрицательных целых чисел с дополнением до двух , -1 представляется как все единицы. Для 8-битового целого числа со знаком это 1111 1111. Арифметический сдвиг вправо на 1 (или 2, 3, ..., 7) снова дает 1111 1111, что по-прежнему равно -1. Это соответствует округлению в меньшую сторону (в сторону отрицательной бесконечности), но не является обычным условием деления.

Часто утверждается, что арифметические сдвиги вправо эквивалентны делению на (положительную, целую) степень основания системы счисления (например, деление на степень 2 для двоичных чисел), и, следовательно, это деление на степень основания системы счисления может быть оптимизирован путем реализации арифметического сдвига вправо. (Устройство сдвига намного проще делителя. На большинстве процессоров инструкции сдвига будут выполняться быстрее, чем инструкции деления.) Большое количество руководств по программированию 1960-х и 1970-х годов, руководств и других спецификаций от компаний и организаций, таких как DEC , IBM , Data General , и ANSI делают такие неверные утверждения.

Логический сдвиг вправо эквивалентен делению на степень основания (обычно 2) только для положительных или беззнаковых чисел. Арифметические сдвиги вправо эквивалентны логическим сдвигам вправо для положительных чисел со знаком. Арифметические сдвиги вправо для отрицательных чисел в дополнении N − 1 (обычно два дополнения ) примерно эквивалентны делению на степень системы счисления (обычно 2), где для нечетных чисел применяется округление в меньшую сторону (а не в сторону 0, как обычно ожидается).

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

Решение проблемы в языках программирования

Стандарт ISO (1999) для языка программирования C определяет оператор сдвига вправо в терминах деления на степень 2. Из-за указанной выше неэквивалентности стандарт явно исключает из этого определения сдвиги вправо чисел со знаком, которые имеют отрицательные значения. Он не определяет поведение оператора сдвига вправо в таких обстоятельствах, но вместо этого требует, чтобы каждый отдельный компилятор C определял поведение сдвига отрицательных значений вправо.

Приложения

В приложениях, где желательно последовательное округление в меньшую сторону, полезны арифметические сдвиги вправо для значений со знаком. Примером может служить масштабирование координат растра до степени двойки, при которой сохраняется равномерный интервал. Например, сдвиг вправо на 1 отправляет 0, 1, 2, 3, 4, 5, ... в 0, 0, 1, 1, 2, 2, ... и −1, −2, −3, От −4, ... до −1, −1, −2, −2, ..., сохраняя четный интервал как −2, −2, −1, −1, 0, 0, 1, 1, 2, 2 , ... Напротив, целочисленное деление с округлением до нуля отправляет −1, 0 и 1 все в 0 (3 балла вместо 2), что дает −2, −1, −1, 0, 0, 0, 1, 1, 2, 2, ... вместо этого, что не соответствует норме в 0.

Примечания

  1. ^ Оператор в C и C ++, не обязательно является арифметическим сдвигом. Обычно это только арифметический сдвиг, если он используется с целочисленным типом со знаком в левой части. Если вместо этого он используется для целочисленного типа без знака, это будет логический сдвиг. >>
  2. ^ Оператор арифметического сдвига вправо Verilog фактически выполняет арифметический сдвиг, только если первый операнд подписан. Если первый операнд беззнаковый, оператор фактически выполняет логический сдвиг вправо.
  3. ^ Вмакроязыке OpenVMS , является ли арифметический сдвиг влево или вправо, определяется тем, является ли второй операнд положительным или отрицательным. Это необычно. В большинстве языков программирования два направления имеют разные операторы, причем оператор определяет направление, а второй операнд неявно положительный. (Некоторые языки, такие как Verilog, требуют преобразования отрицательных значений в положительные значения без знака. Некоторые языки, такие как C и C ++, не имеют определенного поведения при использовании отрицательных значений.)
  4. ^ В схемеarithmetic-shiftможет быть как левый и правый сдвиг,зависимости от второго операнда, очень похожий на OpenVMS макро языка, хотя R6RS схема добавляет как-rightи-leftварианты.
  5. ^ Класс от Хаскелямодуля определяет ипринимает подписанный аргумент и/принимать неподписанные аргументы. Они изоморфны ; для новых определений программисту необходимо предоставить только одну из двух форм, а другая форма будет автоматически определена в терминах предоставленной.BitsData.BitsshiftshiftLshiftR
  6. ^ Оператор арифметического сдвига влево VHDL необычен. Вместо того, чтобы заполнять LSB результата нулем, он копирует исходный LSB в новый LSB. Хотя это точное зеркальное отображение арифметического сдвига вправо, это не обычное определение оператора и не эквивалентно умножению на степень 2. В стандарте VHDL 2008 это странное поведение было оставлено без изменений (для обратной совместимости ) для типов аргументовкоторые не заставили числовую интерпретацию (например, bit_vector)но «» SLA для неподписанных и подписанных типов аргументов ведет себя ожидаемым образом (т.е. правые позиции заполняются нулями). Функция логического сдвига влево (SLL) VHDL действительно реализует вышеупомянутый «стандартный» арифметический сдвиг.
  7. ^ Стандарт C был предназначен для того, чтобы не ограничивать язык C архитектурой дополнения до одного или двух. В случаях, когда поведение представлений дополнения единиц и двух дополнений различается, как, например, этот, стандарт требует, чтобы отдельные компиляторы C документировали поведение своих целевых архитектур. Документация для GNU Compiler Collection (GCC), например, документирует его поведение как использование расширения знака.

использованная литература

Перекрестная ссылка

Используемые источники

Всеобщее достояние Эта статья включает  материалы, являющиеся общественным достоянием, из документа Управления общих служб : «Федеральный стандарт 1037C» .