Как сделать циклический сдвиг влево
Обновлено: 08.07.2024
БлогNot. С++: циклический сдвиг числа влево/вправо на k бит
С++: циклический сдвиг числа влево/вправо на k бит
В дополнение к "битовой" теме, выполним циклический побитовый сдвиг значения влево или вправо. Например, при сдвиге влево самый старший (левый) бит числа "переезжает" в крайнюю правую позицию, а остальные биты сдвигаются на 1 влево.
Если n - 16-битное число, а k - количество бит, на которые нужно его сдвинуть (возможен многократный "циклический" сдвиг, так что k не обязано быть меньше 16), то имеем следующую реализацию:
Заменив 2-байтовые константы вида 0x8000 на 4-байтовые, а 15 на 31, можно получить аналогичный код для 32-битных целых.
Особенности
Операция циклического сдвига 16-и битного значения в любую сторону на 8 бит меняет местами его старший и младший байты.
Примеры
Пример №1.
Пример №2.
Циклический сдвиг на 8 бит - обмен местами старшего и младшего байта:
Пример №3.
Насколько я понимаю, циклический сдвиг подразумевает подобную перестановку.
Как реализовать данную операцию в машине Тьюринга?
". насколько я понимаю, циклический сдвиг подразумевает подобную перестановку. "
Нет, не так. У Вас на рисунке организован "просто сдвиг влево".
А циклический сдвиг подразумевает, что информация смещается циклически, то есть, из старшего бита попадёт в самый младший и будет постоянно смещаться "по кругу".
В любом регистре цифровой техники эта операция выполняется легко. Подключаются линии задержки между его ячейками и любой импульс в 1-ю ячейку "сдвинет" их состояния как камень брошенный в воду. Если просто надо составить алгоритм сдвига запятой, то умножай или дели на "2" или на "10", в зависимости от представления числа в том или ином коде.
где 0,1 - состояние машины; [0],[1]-значение ячейки; R,L - направление перемещения машины относительно ленты;
слева от дефиса состояние машины в данный момент времени, справа, состояние, на которое машина должна измениться.
Би́товый сдвиг — изменение позиций битов в слове на одну и ту же величину.
Большинство компьютеров не могут напрямую адресовать биты, которые содержатся группами по 8, 16, 32 или 64 битов в словах. Для обеспечения работы с битами существует множество машинных инструкций, включающие различные типы сдвигов. Все сдвиги похожи друг на друга поведением средних битов, которые просто сдвигаются влево или вправо на определённую величину. Однако, поведение крайних битов, которые уходят из слова и которые появляются в слове, зависит от типа сдвига.
В электронике битовые сдвиги осуществляются в регистрах сдвига.
Содержание
Логический сдвиг
Сдвиг, при котором уходящий бит уходит, не влияя на оставшееся биты, а на место появившегося бита записывается бит 0.
Пример работы операции сдвига:
Пусть у нас есть число 10101010b (в двоичной системе). Если сделать сдвиг влево на 1 бит, то получим число 01010100b Если сделать сдвиг исходного числа вправо на 1 бит, то получим число 01010101b
В большинстве процессоров уходящий бит сохраняется во флаге переноса. Эта функция широко используется при работе со многобайтовыми числами.
Арифметический сдвиг
При этом сдвиге слово рассматривается не просто как группа битов, а как целое число в дополнительном коде. При сдвиге влево ведёт себя как логический сдвиг, при сдвиге вправо: уходящий бит уходит, не влияя на оставшиеся биты, а на место появившегося бита устанавливается бит, соответствующий знаку.
Пример работы операции сдвига:
Пусть у нас есть число 11111010b = −6 (в двоичной системе). Если сделать сдвиг влево на 1 бит, то получим число 11110100b = −12 Если сделать сдвиг исходного числа вправо на 1 бит, то получим число 11111101b = −3
Легко заметить, что при арифметическом сдвиге сдвиг влево соответствует умножению на 2, а сдвиг вправо — делению на 2 (в общем случае — на основание системы счисления) с округлением к −∞. Например:
Схемотехническая реализация операций сдвига очень проста. Именно поэтому эти операции рекомендуют использовать для операций умножения и деления целых чисел на числа, равные степени 2 (2, 4, 8, 16, 32, 64 и т. д.) — если, конечно, такое округление отрицательных чисел не мешает.
Циклический сдвиг
При этом сдвиге уходящий бит появляется на месте появившегося.
Пример работы операции сдвига:
Пусть у нас есть число 11111010b (в двоичной системе). Если сделать сдвиг влево на 1 бит, то получим число 11110101b Если сделать сдвиг вправо на 1 бит, то получим число 01111101b
Циклический сдвиг через бит переноса
В архитектуру многих процессоров входит флаг переноса в следующий разряд (например, cf на x86). Данная операция выполняет циклический сдвиг над (n+1)-битным числом, состоящим из регистра и флага переноса.
Например, если у нас в регистре число 11111010b, флаг переноса равен 0:
После сдвига влево на 1 бит: в регистре 11110101b, флаг переноса равен 1 После сдвига вправо на 1 бит: в регистре 01111101b, флаг переноса равен 0
Операция циклического сдвига через бит переноса используется при работе с многобайтовыми числами. В частности, чтобы сдвинуть вправо на 1 бит длинное число, нужно очистить [1] cf (в случае деления числа со знаком нужно записать в cf старший бит старшего слова) и циклически сдвинуть на единицу через cf каждое слово, начиная с верхнего. Например, пусть у нас есть число 011000111100b, занимающее три 4-битных слова:
Сдвиги через регистр флагов более чем на 1 бит практически не используются.
См. также
Примечания
- ↑ Можно вместо очистки флага для первого обрабатываемого слова использовать арифметический\логический сдвиг, если он присваивает флагу cf значение вышедшего бита.
Ссылки
| Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным. |