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

Правый арифметический сдвиг двоичного числа на 1. Пустая позиция в старшем разряде заполняется копией исходного MSB.
Левый арифметический сдвиг двоичного числа на 1. Пустая позиция в младший бит заполняется нулем.
Операторы арифметического сдвига в различных языках программирования и процессорах
Язык или процессорОставилиПравильно
ActionScript 3, Ява, JavaScript, Python, PHP, Рубин;
C, C ++,[1]D, C #, Идти, Юля, Быстрый (только для подписанных типов)[примечание 1]		 << >>
Ада Shift_Left [2] Shift_Right_Arithmetic
Котлин shl шр
Стандартный ML << ~>>
Verilog <<< >>> [заметка 2]
OpenVMS макроязык@[заметка 3]
Схемаарифметический сдвиг[примечание 4]
Common Lispпепел
OCamllslasr
HaskellData.Bits.shift[примечание 5]
Сборка, 68 тыс.ASLASR
Сборка, x86SALSAR
VHDLsla[примечание 6]сра
Z80SLA[4]SRA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

В приложениях, где желательно последовательное округление в меньшую сторону, полезны арифметические сдвиги вправо для значений со знаком. Пример есть в уменьшение масштаба растровые координаты в степени двойки, что обеспечивает равномерный интервал. Например, сдвиг вправо на 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 ++, не имеют определенного поведения при использовании отрицательных значений.)[3][страница нужна ]
  4. ^ В схеме арифметический сдвиг может быть сдвиг как влево, так и вправо, в зависимости от второго операнда, очень похоже на макроязык OpenVMS, хотя схема R6RS добавляет оба -верно и -оставили варианты.
  5. ^ В Биты класс из Haskell's Data.Bits модуль определяет как сдвиг взяв подписанный аргумент и shiftL/shiftR принимая беззнаковые аргументы. Это изоморфный; для новых определений программисту необходимо предоставить только одну из двух форм, а другая форма будет автоматически определена в терминах предоставленной.
  6. ^ Оператор арифметического сдвига влево VHDL необычен. Вместо того, чтобы заполнять LSB результата нулем, он копирует исходный LSB в новый LSB. Хотя это точное зеркальное отображение арифметического сдвига вправо, это не является обычным определением оператора и не эквивалентно умножению на степень 2. В стандарте VHDL 2008 это странное поведение было оставлено без изменений (для обратной совместимости ) для типов аргументов, которые не имеют принудительной числовой интерпретации (например, BIT_VECTOR), но 'SLA' для беззнаковый и подписанный типы аргументов ведут себя ожидаемым образом (т. е. крайние правые позиции заполняются нулями). Функция логического сдвига влево (SLL) VHDL реализует вышеупомянутый «стандартный» арифметический сдвиг.
  7. ^ Стандарт C был предназначен для того, чтобы не ограничивать язык C архитектурами с дополнением до одного или двумя. В случаях, когда поведение представлений дополнения единиц и двух дополнений различается, как, например, в этом, стандарт требует, чтобы отдельные компиляторы C документировали поведение своих целевых архитектур. Документация для Коллекция компиляторов GNU (GCC), например, документирует свое поведение как использование расширения знака.[10]

Рекомендации

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

  1. ^ «Битовые манипуляции - Dlang Tour». tour.dlang.org. Получено 2019-06-23.
  2. ^ «Справочное руководство по Ada 2012 с аннотациями».
  3. ^ HP 2001.
  4. ^ "Синтаксис ассемблера Z80".
  5. ^ Томас Р. Кейн и Алан Т. Шерман."Как взломать шифр Гиффорда".Раздел 8.1: «Прилипчивое или незакрепленное битовое смещение» .Cryptologia.1997.
  6. ^ Стил-младший, Гай. «Арифметический сдвиг считается вредным» (PDF). Лаборатория искусственного интеллекта Массачусетского технологического института. Получено 20 мая 2013.
  7. ^ Гайд 1996, § 6.6.2.2 SAR.
  8. ^ Стил 1977.
  9. ^ ISOIEC9899 1999, § 6.5.7 Операторы побитового сдвига.
  10. ^ ФСПО 2008, § 4.5 Реализация целых чисел.

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

Эта статья включаетматериалы общественного достояния от Администрация общих служб документ: «Федеральный стандарт 1037С».