Бинарные сдвиги и побитовые операции
| English | Русский |
|---|---|
| bit/bɪt/ | бит |
| mask/mæsk/ | маска |
| logical shift/ˈlɒdʒɪkl ʃɪft/ | логический сдвиг |
| sign bit/saɪn bɪt/ | знаковый бит |
| arithmetic right shift/ˌærɪθˈmetɪk raɪt ʃɪft/ | арифметический сдвиг вправо |
| cyclic shift/ˈsaɪklɪk ʃɪft/ | циклический сдвиг |
Умножение на чипе, который не умеет умножать
- Процессор в Game Boy 1989 года вообще не имел инструкции умножения. Каждый счет, каждая координата, требующая удвоения, удваивалась путем сдвига битов на одну позицию влево.
- Сдвиг занимает такт процессора. Умножение, построенное из сдвигов и сложений, позволяло тем играм работать на нескольких килобайтах памяти и паре милливатт мощности.
- Те же приемы управляют отдельными проводами во встроенном устройстве: один бит регистра на каждый датчик или исполнительный механизм, проверяется и устанавливается с помощью маски.
- Этот урок охватывает три вида сдвигов и четыре операции маскировки, согласно инструкциям самого экзамена.
Логические сдвиги
- Логический сдвиг перемещает каждый бит влево или вправо на определенное количество позиций, заполняя освободившиеся места нулями 0.
LSL #1сдвигает биты влево, и справа появляется 0: для беззнакового числа это означает × 2.LSR #1сдвигает их вправо, и слева появляется 0: целочисленное ÷ 2.- Сдвиг на $n$ позиций умножает или делит на $2^{n}$.
00001011(11) послеLSL #1становится00010110(22); послеLSR #1оно становится00000101(5, остаток потерян).
Логический левый (× 2), логический правый (÷ 2) и арифметический правый (сохраняет знаковый бит)
Сдвиньте и отфильтруйте биты байта
Выберите оператор и посмотрите на каждый результатный бит. Левый сдвиг (<<) moves every bit up one place (×2); a right shift (>>) перемещает их вниз (÷2); AND с маской обнуляет ненужные биты.
8-битное значение 00001011 (11) сдвигается влево на 1 раз(LSL #1). Какое новое десятичное значение?
Левый сдвиг на 1 умножает на 2: $11 \times 2 = 22$ (00010110).
Сдвиг беззнакового числа влево на 3 позиции умножает его на какое число?
Сдвиг на $n$ позиций умножает на $2^n$, значит сдвиг на 3 позиции — это $2^3 = 8$.
Разборчивый пример: когда × 4 перестает быть верным
- Биты, сдвинутые за пределы, теряются, поэтому умножение остается верным только до тех пор, пока они были нулями.
- Сдвиг⟩
LSL #2⟨ байта со знакомом по补码 (two's complement)⟩11001010⟨ дает результат⟩00101000⟨. Два бита⟩1⟨, которые отвалились слева, потеряны, знак изменился, и результат больше не равен четырем исходным значениям. LSL #2на00001011(11) дает00101100(44), что верно, потому что были потеряны только нули.- Экзамен требует указать оба: сдвинутое представление и комментарий о том, осталось ли значение верным.
Арифметический правый сдвиг
- Обычный логический правый сдвиг ставит 0 в старший бит, что превратило бы отрицательное число в положительное.
- Арифметический правый сдвиг копирует знаковый бит в каждое освободившееся место, поэтому отрицательное число остается отрицательным, а сдвиг все еще делит на 2.
- Арифметический сдвиг⟩
10011110⟨ вправо на⟩3⟨ позиций дает⟩11110011⟨;⟩01011100⟨ дает⟩00001011⟨.
Логический и арифметический правый сдвиг на одном и том же байте: отличается только входящий бит
Арифметический правый сдвиг отличается от логического правого сдвига тем, что он:
Он сохраняет знак, поэтому деление отрицательного знакового числа на степень 2 сохраняет его отрицательным.
Логический правый сдвиг всегда ставит 0 в старший бит, поэтому он может сделать отрицательное знаковое число положительным.
Именно поэтому деление знаковых чисел требует арифметического правого сдвига, который копирует знаковый бит.
Арифметический правый сдвиг 10011110 на 3 позиции дает 8-битную последовательность ____.
Три освобожденных места слева заполняются копиями знакового бита, 1, а три крайних правых бита 110 отбрасываются.
Циклические сдвиги
- Циклический сдвиг, или вращение, подает бит, выпадающий с одного конца, обратно на другой конец, так что ни один бит не теряется.
- Циклический левый сдвиг на 1 для
10000110дает00001101: ведущая 1 снова появляется справа. - Логические сдвиги заполняются нулями, арифметические сдвиги заполняются знаковым битом, циклические сдвиги заполняются битом, который ушел. Это и есть вся разница между тремя.
К ⟨10000110⟩ применяется циклический сдвиг влево на ⟨1⟩ позиций. Каков результат?
Старшая 1 уходит слева и входит справа, поэтому ни один бит не теряется. 00001100 был бы логическим сдвигом.
Разборчивый пример: 240 или минус 16?
- Возьмем
11110000. Если читать как беззнаковое число, это 240; если как двухкомплементное, это −16. LSR #1вносит 0 и дает01111000= 120, правильную половину 240.ASR #1копирует знаковый бит и дает11111000= −8, правильную половину −16.- Ни одно из них не является неправильным. Каждое делит значение пополам в рамках одной интерпретации, поэтому процессору нужны обе инструкции.
Какие утверждения о байте 11110000 верны? Выберите все подходящие варианты.
Два результата отличаются только битом, входящим слева: 0 для логического сдвига, знаковый бит для арифметического сдвига.
Маскирование битов
- Во встроенных устройствах часто используется один бит регистра на каждый сигнал. Маска — это шаблон, применяемый к регистру, чтобы изменился только выбранный бит.
- Установить бит⟩$n$⟨:⟩
OR⟨ с маской, имеющей единицу⟩1⟨ в позиции⟩$n$⟨. Очистить бит⟩$n$⟨:⟩AND⟨ с маской, имеющей там ноль⟩0⟨ и все остальные единицы⟩1⟨. - Переключить бит $n$:
XORс маской, имеющей 1 там. Проверить бит $n$:ANDс этой маской, затемCMP #0: неравенство означает, что бит был установлен.
Установка с помощью OR, очистка с помощью AND, переключение с помощью XOR; каждое действие выполняется с использованием маски
Сопоставьте каждую побитовую операцию с побитовым оператором (и маской), который ее выполняет.
OR устанавливает, AND очищает, XOR переключает, а AND + ненулевой тест читает бит — четыре маскирующих движения.
Чтобы УСТАНОВИТЬ конкретный бит в 1, вы комбинируете регистр с маской с помощью:
OR с маской, у которой этот бит = 1, принудительно устанавливает бит в 1 и оставляет остальные без изменений.
Разобранный пример: инструкции для одного байта
- ACC содержит
10101100. Маску можно записать как#nв десятичной системе,Bnв двоичной или&nв шестнадцатеричной. AND B00001111дает00001100: выживают только младшие четыре бита.OR #1дает10101101: установлен наименьший значащий бит, остальные не изменяются.XOR &FFдаёт01010011: каждый бит инвертирован. ЗатемAND B00001000иCMP #0проверяют бит 3; результат00001000не равен нулю, значит бит 3 был установлен.LSL #2дает10110000, теряя два старших бита;LSR #3дает00010101.
Инструкция, устанавливающая младший значащий разряд ACC в 1 и не изменяющая остальные разряды, — это OR ____.
OR с маской, имеющей 1 только в последнем разряде. Десятичное #1, двоичное B00000001 и шестнадцатеричное &1 — одна и та же маска.
Расставьте шаги для проверки того, установлен ли бит 3 в ACC, в правильном порядке.
Маска, сравнение, переход. AND оставляет либо 00001000, либо 00000000, а сравнение с нулем различает их.
Мониторинг и управление по одному биту
- В устройстве мониторинга один бит регистра на каждый датчик означает, что один操作
ANDпроверяет, включен ли конкретный датчик. - В устройстве управления один操作
ORвключает управляющий бит актуатора, не затрагивая остальные, а один操作ANDвыключает его. - Это быстро, почти не требует памяти, а один байт хранит восемь независимых состояний «вкл/выкл». Именно это требуется ответить на экзамене.
Потерянные баллы
- Сдвиг влево умножает на × 2 за позицию только пока отбрасываемые биты равны нулю. Укажите это, когда теряется единичный бит⟩1⟨.
- Логический сдвиг вправо подставляет 0; арифметический сдвиг вправо копирует знаковый бит. Выбирайте в зависимости от того, является ли число знаковым.
- Для очистки бита маска должна иметь 0 в этой позиции и 1 во всех остальных. Маска из одних нулей очищает весь регистр.
XORпереключает; она не устанавливает. Для установки используйтеOR, для проверки используйтеANDи сравните с нулем.
Вы поняли
- Логический сдвиг заполняет нулями 0: влево × 2 за позицию, вправо ÷ 2, а потерянные 1s нарушают арифметику
- арифметический сдвиг вправо копирует знаковый бит; циклический сдвиг переносит бит по кругу
- маски: OR устанавливает · AND очищает · XOR переключает · AND затем CMP #0 проверяет
- один бит на датчик или актуатор делает мониторинг и управление быстрыми и компактными; маски записываются как
#n,Bnили&n