Битовый сдвиг

Поделись знанием:
(перенаправлено с «Циклический сдвиг»)
Перейти к: навигация, поиск

Би́товый сдвиг — изменение позиций битов в слове на одну и ту же величину.

Большинство компьютеров не могут напрямую адресовать биты, которые содержатся группами по 8, 16, 32 или 64 битов в словах. Для обеспечения работы с битами существует множество машинных инструкций, включающие различные типы сдвигов. Все сдвиги похожи друг на друга поведением средних битов, которые просто сдвигаются влево или вправо на определённую величину. Однако, поведение крайних битов, которые уходят из слова и которые появляются в слове, зависит от типа сдвига.

В электронике битовые сдвиги осуществляются в регистрах сдвига.





Логический сдвиг

Сдвиг, при котором уходящий бит исчезает, не влияя на оставшиеся биты, а на месте появившегося бита записывается бит 0.

Пример работы операции сдвига:

Пусть у нас есть число 10101010b (в двоичной системе).
Если сделать сдвиг влево на 1 бит, то получим число 01010100b.
Если сделать сдвиг исходного числа вправо на 1 бит, то получим число 01010101b.

В большинстве процессоров уходящий бит сохраняется во флаге переноса. Эта функция широко используется при работе со многобайтовыми числами.

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

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

Пример работы операции сдвига:

Пусть у нас есть число 11111010b = −6 (в двоичной системе).
Если сделать сдвиг влево на 1 бит, то получим число 11110100b = −12.
Если сделать сдвиг исходного числа вправо на 1 бит, то получим число 11111101b = −3.

Легко заметить, что при арифметическом сдвиге сдвиг влево соответствует умножению на 2, а сдвиг вправо — делению на 2 (в общем случае — на основание системы счисления) с округлением к −∞. Например:

 1011 = −5          1111 = −1
>>a 1              >>a 1
 ----               ----
 1101 = −3          1111 = −1

Схемотехническая реализация операций сдвига очень проста. Именно поэтому эти операции рекомендуют использовать для операций умножения и деления целых чисел на числа, равные степени 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-битных слова:

Было:              HI=0110, MED=0011, LO=1100, cf=0
После сдвига HI:   HI=0011, MED=0011, LO=1100, cf=0
После сдвига MED:  HI=0011, MED=0001, LO=1100, cf=1
После сдвига LO:   HI=0011, MED=0001, LO=1110, cf=0

Сдвиги через регистр флагов более чем на 1 бит практически не используются.

См. также

Напишите отзыв о статье "Битовый сдвиг"

Примечания

  1. Можно вместо очистки флага для первого обрабатываемого слова использовать арифметический\логический сдвиг, если он присваивает флагу cf значение вышедшего бита.

Ссылки

  • [www.programmersclub.ru/assembler11/ «Assembler&Win32. Курс молодого бойца.» Урок 11. «Биты, сдвиг логический, арифметический и циклический.»]


Отрывок, характеризующий Битовый сдвиг

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


Генерал, за которым скакал Пьер, спустившись под гору, круто повернул влево, и Пьер, потеряв его из вида, вскакал в ряды пехотных солдат, шедших впереди его. Он пытался выехать из них то вправо, то влево; но везде были солдаты, с одинаково озабоченными лицами, занятыми каким то невидным, но, очевидно, важным делом. Все с одинаково недовольно вопросительным взглядом смотрели на этого толстого человека в белой шляпе, неизвестно для чего топчущего их своею лошадью.
– Чего ездит посерёд батальона! – крикнул на него один. Другой толконул прикладом его лошадь, и Пьер, прижавшись к луке и едва удерживая шарахнувшуюся лошадь, выскакал вперед солдат, где было просторнее.
Впереди его был мост, а у моста, стреляя, стояли другие солдаты. Пьер подъехал к ним. Сам того не зная, Пьер заехал к мосту через Колочу, который был между Горками и Бородиным и который в первом действии сражения (заняв Бородино) атаковали французы. Пьер видел, что впереди его был мост и что с обеих сторон моста и на лугу, в тех рядах лежащего сена, которые он заметил вчера, в дыму что то делали солдаты; но, несмотря на неумолкающую стрельбу, происходившую в этом месте, он никак не думал, что тут то и было поле сражения. Он не слыхал звуков пуль, визжавших со всех сторон, и снарядов, перелетавших через него, не видал неприятеля, бывшего на той стороне реки, и долго не видал убитых и раненых, хотя многие падали недалеко от него. С улыбкой, не сходившей с его лица, он оглядывался вокруг себя.
– Что ездит этот перед линией? – опять крикнул на него кто то.
– Влево, вправо возьми, – кричали ему. Пьер взял вправо и неожиданно съехался с знакомым ему адъютантом генерала Раевского. Адъютант этот сердито взглянул на Пьера, очевидно, сбираясь тоже крикнуть на него, но, узнав его, кивнул ему головой.
– Вы как тут? – проговорил он и поскакал дальше.
Пьер, чувствуя себя не на своем месте и без дела, боясь опять помешать кому нибудь, поскакал за адъютантом.
– Это здесь, что же? Можно мне с вами? – спрашивал он.
– Сейчас, сейчас, – отвечал адъютант и, подскакав к толстому полковнику, стоявшему на лугу, что то передал ему и тогда уже обратился к Пьеру.
– Вы зачем сюда попали, граф? – сказал он ему с улыбкой. – Все любопытствуете?
– Да, да, – сказал Пьер. Но адъютант, повернув лошадь, ехал дальше.
– Здесь то слава богу, – сказал адъютант, – но на левом фланге у Багратиона ужасная жарня идет.
– Неужели? – спросил Пьер. – Это где же?
– Да вот поедемте со мной на курган, от нас видно. А у нас на батарее еще сносно, – сказал адъютант. – Что ж, едете?
– Да, я с вами, – сказал Пьер, глядя вокруг себя и отыскивая глазами своего берейтора. Тут только в первый раз Пьер увидал раненых, бредущих пешком и несомых на носилках. На том самом лужке с пахучими рядами сена, по которому он проезжал вчера, поперек рядов, неловко подвернув голову, неподвижно лежал один солдат с свалившимся кивером. – А этого отчего не подняли? – начал было Пьер; но, увидав строгое лицо адъютанта, оглянувшегося в ту же сторону, он замолчал.
Пьер не нашел своего берейтора и вместе с адъютантом низом поехал по лощине к кургану Раевского. Лошадь Пьера отставала от адъютанта и равномерно встряхивала его.
– Вы, видно, не привыкли верхом ездить, граф? – спросил адъютант.
– Нет, ничего, но что то она прыгает очень, – с недоуменьем сказал Пьер.
– Ээ!.. да она ранена, – сказал адъютант, – правая передняя, выше колена. Пуля, должно быть. Поздравляю, граф, – сказал он, – le bapteme de feu [крещение огнем].
Проехав в дыму по шестому корпусу, позади артиллерии, которая, выдвинутая вперед, стреляла, оглушая своими выстрелами, они приехали к небольшому лесу. В лесу было прохладно, тихо и пахло осенью. Пьер и адъютант слезли с лошадей и пешком вошли на гору.
– Здесь генерал? – спросил адъютант, подходя к кургану.
– Сейчас были, поехали сюда, – указывая вправо, отвечали ему.
Адъютант оглянулся на Пьера, как бы не зная, что ему теперь с ним делать.
– Не беспокойтесь, – сказал Пьер. – Я пойду на курган, можно?
– Да пойдите, оттуда все видно и не так опасно. А я заеду за вами.
Пьер пошел на батарею, и адъютант поехал дальше. Больше они не видались, и уже гораздо после Пьер узнал, что этому адъютанту в этот день оторвало руку.
Курган, на который вошел Пьер, был то знаменитое (потом известное у русских под именем курганной батареи, или батареи Раевского, а у французов под именем la grande redoute, la fatale redoute, la redoute du centre [большого редута, рокового редута, центрального редута] место, вокруг которого положены десятки тысяч людей и которое французы считали важнейшим пунктом позиции.