Арифметический сдвиг
| Язык или процессор | Левый | Верно |
|---|---|---|
| ActionScript 3, Java , JavaScript , Python , PHP , Ruby , C , C++ , [1] D , C# , Го , Юля , Rust (только подписанные типы) [2] , Swift (только подписанные типы) [примечание 1] | << | >> |
| Есть | Shift_Left [3] | Shift_Right_Arithmetic |
| Котлин | shl | shr |
| Фортран | SHIFTL | SHIFTA [примечание 2] |
| Стандартный ML | << | ~>> |
| Верилог | <<< | >>> [примечание 3] |
| OpenVMS Язык макросов | @ [примечание 4] | |
| Схема | arithmetic-shift[примечание 5] | |
| Общий Лисп | ash | |
| OCaml | lsl | asr |
| Хаскелл | Data.Bits.shift[примечание 6] | |
| VHDL | sla[примечание 7] | sra |
| Сборка: Z80 | SLA[5] | SRA |
| Сборка: х86 | SAL | SAR |
| Сборка: 68к | ASL | ASR |
| Сборка: RISC-V | sll, slli[6] | sra, srai |
В компьютерном программировании арифметический сдвиг — это оператор сдвига , иногда называемый знаковым сдвигом (хотя он не ограничивается знаковыми операндами). Двумя основными типами являются арифметический сдвиг влево и арифметический сдвиг вправо . Для двоичных чисел это побитовая операция , которая сдвигает все биты операнда; каждый бит в операнде просто перемещается на заданное количество битовых позиций, а свободные битовые позиции заполняются. Вместо заполнения всеми нулями, как при логическом сдвиге , при сдвиге вправо самый левый бит (обычно это знаковый бит в представлениях целых чисел со знаком) реплицируется для заполнения всех вакантных позиций (это своего рода расширение знака ).
Некоторые авторы предпочитают термины «липкий сдвиг вправо» и «сдвиг вправо с нулевым заполнением» для арифметических и логических сдвигов соответственно. [7]
Арифметические сдвиги могут быть полезны как эффективные способы умножения или деления целых чисел со знаком на степени двойки. Сдвиг влево на n бит знакового или беззнакового двоичного числа приводит к его умножению на 2. н . Сдвиг вправо на n битов , дополненного до двух, двоичного числа со знаком приводит к делению его на 2. н , но всегда округляется в меньшую сторону (в сторону отрицательной бесконечности). Это отличается от того, как обычно выполняется округление при делении целых чисел со знаком (которое округляется в сторону 0). Это несоответствие привело к ошибкам в ряде компиляторов. [8]
Например, в наборе команд x86 инструкция SAR (арифметический сдвиг вправо) делит число со знаком на степень двойки, округляя в сторону отрицательной бесконечности. [9] Однако инструкция 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 делают такие неверные утверждения [10] [ нужна страница ] .
Логические сдвиги вправо эквивалентны делению на степень основания (обычно 2) только для положительных или беззнаковых чисел. Арифметические сдвиги вправо эквивалентны логическим сдвигам вправо для чисел с положительным знаком. Арифметические сдвиги вправо для отрицательных чисел в дополнении N (обычно в дополнении до двух ) примерно эквивалентны делению на степень системы счисления (обычно 2), где для нечетных чисел применяется округление вниз (а не в сторону 0, как обычно ожидается).
Арифметические сдвиги вправо для отрицательных чисел эквивалентны делению с округлением до 0 в представлении чисел со знаком в виде дополнения до единиц , которое использовалось некоторыми историческими компьютерами, но это больше не используется повсеместно.
Решение проблемы в языках программирования [ править ]
Стандарт ISO (1999 г.) для языка программирования C определяет оператор сдвига вправо в терминах деления на степени 2. [11] Из-за указанной выше неэквивалентности стандарт явно исключает из этого определения сдвиг вправо чисел со знаком, имеющих отрицательные значения. Он не определяет поведение оператора сдвига вправо в таких обстоятельствах, а вместо этого требует, чтобы каждый отдельный компилятор C определял поведение сдвига отрицательных значений вправо. [примечание 8]
Как и C, C++ имел определяемый реализацией сдвиг вправо для целых чисел со знаком до C++20. Начиная со стандарта C++20, сдвиг вправо целого числа со знаком определяется как арифметический сдвиг. [13]
Приложения [ править ]
В приложениях, где требуется последовательное округление в меньшую сторону, полезны арифметические сдвиги вправо для знаковых значений. Примером может служить уменьшение масштаба растровых координат в степени двойки, что позволяет сохранить равномерный интервал. Например, сдвиг вправо на 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.
Примечания [ править ]
- ^
>>Оператор в C и C++ не обязательно является арифметическим сдвигом. Обычно это всего лишь арифметический сдвиг, если он используется с целочисленным типом со знаком в левой части. Если вместо этого он используется для целочисленного типа без знака, это будет логический сдвиг. - ^ Фортран 2008.
- ^ Оператор арифметического сдвига вправо Verilog фактически выполняет арифметический сдвиг только в том случае, если первый операнд подписан. Если первый операнд беззнаковый, оператор фактически выполняет логический сдвиг вправо.
- ^ В языке макросов OpenVMS арифметический сдвиг влево или вправо определяется тем, является ли второй операнд положительным или отрицательным. Это необычно. В большинстве языков программирования два направления имеют разные операторы, причем оператор определяет направление, а второй операнд неявно положителен. (Некоторые языки, такие как Verilog, требуют преобразования отрицательных значений в беззнаковые положительные значения. Некоторые языки, такие как C и C++, не имеют определенного поведения при использовании отрицательных значений.) [4] [ нужна страница ]
- ^ На схеме
arithmetic-shiftможет быть сдвигом как влево, так и вправо, в зависимости от второго операнда, очень похоже на язык макросов OpenVMS, хотя схема R6RS добавляет оба-rightи-leftварианты. - ^
Bitsкласс из HaskellData.Bitsмодуль определяет обаshiftпринимая подписанный аргумент иshiftL/shiftRпринимая беззнаковые аргументы. Они изоморфны ; для новых определений программисту необходимо предоставить только одну из двух форм, а другая форма будет автоматически определена на основе предоставленной. - ^ Арифметический оператор сдвига влево VHDL необычен. Вместо заполнения младшего разряда результата нулем он копирует исходный младший разряд в новый. Хотя это точное зеркальное отражение арифметического сдвига вправо, это не общепринятое определение оператора и не эквивалентно умножению на степень 2. В стандарте VHDL 2008 это странное поведение было оставлено без изменений (для обратной совместимости). ) для типов аргументов, которые не имеют принудительной числовой интерпретации (например, BIT_VECTOR), но «SLA» для типов аргументов без знака и со знаком ведет себя ожидаемым образом (т. е. крайние правые позиции заполняются нулями). Функция логического сдвига влево (SLL) VHDL реализует вышеупомянутый «стандартный» арифметический сдвиг.
- ^ Стандарт C был предназначен для того, чтобы не ограничивать язык C архитектурами с дополнением до одного или до двух. В случаях, когда поведение представлений с дополнением до единицы и представлением с дополнением до двух различается, как в этом случае, стандарт требует, чтобы отдельные компиляторы C документировали поведение своих целевых архитектур. в документации по GNU Compiler Collection (GCC) описано его поведение как использование расширения знака. Например, [12]
Ссылки [ править ]
Перекрестная ссылка [ править ]
- ^ «Битовые манипуляции — Дланг-тур» . www.tour.dlang.org . Проверено 23 июня 2019 г.
- ^ «Операторские выражения: арифметические и логические бинарные операторы» . doc.rust-lang.org . Проверено 13 ноября 2022 г.
- ^ «Аннотированное справочное руководство по Ada 2012» .
- ^ HP 2001 .
- ^ «Синтаксис ассемблера Z80» .
- ^ «Руководство по набору команд RISC-V, том I: непривилегированный ISA» (PDF) . Гитхаб . 13 декабря 2019 г. стр. 18–20. Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 7 августа 2021 г.
- ^ Томас Р. Кейн и Алан Т. Шерман. «Как взломать шифр Гиффорда» .Раздел 8.1: «Прилипчивое и нелипкое смещение битов».Криптология.1997.
- ^ Стил-младший, Гай. «Арифметический сдвиг считается вредным» (PDF) . Лаборатория искусственного интеллекта Массачусетского технологического института. Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 20 мая 2013 г.
- ^ Хайд 1996 , § 6.6.2.2 SAR.
- ^ Стил 1977 .
- ^ ISOIEC9899 1999 , § 6.5.7 Операторы побитового сдвига.
- ^ FSF 2008 , § 4.5 Реализация целых чисел.
- ^ ISOCPP20 2020 , § 7.6.7 Операторы сдвига.
Использованные источники [ править ]
В этой статье использованы общедоступные материалы из Федеральный стандарт 1037C . Управление общего обслуживания . Архивировано из оригинала 22 января 2022 г.
- Кнут, Дональд (1969). Искусство компьютерного программирования , Том 2 — Получисловые алгоритмы . Ридинг, Массачусетс: Аддисон-Уэсли. стр. 169–170.
- Стил, Гай Л. (ноябрь 1977 г.). «Арифметические сдвиги считаются вредными» . Архив уведомлений ACM SIGPLAN . 12 (11). Нью-Йорк: ACM Press: 61–69. дои : 10.1145/956641.956647 . hdl : 1721.1/6090 . S2CID 15420308 . Архивировано из оригинала 22 сентября 2017 года.
- «3.7.1 Оператор арифметического сдвига» . Справочное руководство по VAX MACRO и набору команд . Девелоперская компания Хьюлетт-Паккард. Апрель 2001 г. Архивировано из оригинала 8 августа 2011 г.
{{cite book}}:|work=игнорируется ( помогите ) - Языки программирования — C. ИСО/МЭК 9899:1999. Международная организация по стандартизации . 1999.
- Хайд, Рэндалл (26 сентября 1996 г.). «ГЛАВА ШЕСТАЯ: НАБОР ИНСТРУКЦИЙ 80x86 (Часть 3)». Искусство программирования на языке ассемблера . Архивировано из оригинала 23 ноября 2007 г. Проверено 28 ноября 2007 г.
- «Реализация C» . Руководство GCC . Фонд свободного программного обеспечения . 2008.
- «ISO/IEC 14882:2020(E) – Язык программирования C++» (PDF) . Международная организация по стандартизации. 2020.