На рис. 1.8, а—е приведены иллюстрации к основным логическим операциям и их композициям (так называемые диаграммы Эйлера — Венна) — области истинности каждого из высказываний и их объединения (дизъюнкции), пересечения (конъюнкции) и других операций. «Первый» из законов де Моргана иллюстрируется рис. 1.8, д, е.
Рис.1.8. Некоторые примеры диаграмм Эйлера — Венна:
а — конъюнкция высказываний А и В (AND); б — дизъюнкция высказываний А и В
(or); в — исключающая дизъюнкция (xor); г — разность высказываний (А — В);
д — иллюстрация к законам де Моргана (дополнение пересечения высказываний);
е — иллюстрация к законам де Моргана (объединение дополнений)
Таблица 1.21. Операнды и результаты некоторых побитовых операций
X | У | х & у | X v у | X IMP y | .x EQV y | х XOR y |
Логические операции.
NOT. Поразрядный оператор not (he), или дополнение, является одноместной операцией, которая выполняет логическое отрицание на каждом бите, формируя дополнение данного бинарного значения. Биты, содержавшие бывшие «0», устанавливаются в «1»; и наоборот. Например:
1000 = NOT 0111
Во многих языках программирования (включая С), поразрядный оператор not обозначается как «~» (тильда). Этот оператор не следует путать с «логическим отрицанием» («!» — восклицательный знак), который обрабатывает все значение как отдельное булевское.
OR. Побитовый оператор OR (или, «включающее или») обрабатывает две битовые строки равной длины и создает третью (той же длины), где каждый бит является результатом операции «включающее или» над каждой парой входных битов. Например:
0111 = 0101 OR 0011
В ЯП С поразрядный оператор OR обозначается символом «|» (вертикальная черта). Его булевский аналог обозначается как «||».
XOR («исключающее или») выполняет логическую операцию XOR на каждой паре соответствующих битов двух строк одинаковой длины. Например:
0110 = 0101 XOR 0011
В ЯП С поразрядный оператор XOR обозначается как «^» («крышка»).
Ассемблерные программисты иногда используют операцию XOR как краткую команду обнуления значения регистра. Выполнение XOR над двумя одинаковыми значениями всегда дает нуль в результате, и во многих архитектурах эта операция требует меньшего количества циклов центрального процессора, чем последовательность операций, которые загружают нулевое значение в регистр.
AND. Поразрядный and (и) выполняет логическую операцию AND на каждой паре соответствующих битов двух битовых строк. Например:
0001 = 0101 AND ООН
В ЯП С поразрядный оператор and обозначается как «&» (амперсанд). Булевский аналог записывается как «&&» (два ам-персанда).
Битовые сдвиги (bit shifts). Эти операции также осуществляются на битовом уровне и являются унарными. В этих операциях биты сдвигаются в регистре (влево или вправо). Поскольку регистры компьютера имеют ограниченный размер, некоторые биты будут «выдвинуты из регистра» с одной из его сторон, и аналогичное число бит должно быть «вдвинуто в регистр» с другой. Основное различие в операциях битовых сдвигов заключается в том, как именно они обрабатывают эти «вдвиги/вы-двиги».
Арифметический сдвиг. При арифметическом сдвиге аннулируются биты, которые сдвинуты из любого конца регистра. Однако при арифметическом сдвиге влево с правой стороны вдвигаются нули, а при сдвиге вправо знаковый разряд остается в крайнем правом разряде, сохраняя знак операнда (рис. 1.9, а, б). Арифметический сдвиг влево на п разрядов эквивалентен умножению на 2" (если не происходит переполнения), в то время как арифметический сдвиг вправо на п эквивалентен делению на 2".
Логический сдвиг. При логическом сдвиге аннулируются биты, которые сдвинуты, и их место занимают нули (в любом конце регистра) — рис. 1.9, в, г. Поэтому, логический и арифметический сдвиги влево оказываются тождественными. Однако логический сдвиг вправо вставляет биты со значением «0» вместо копии знакового разряда. Следовательно, логический сдвиг является более подходящим для двоичных чисел без знака, в то время как арифметический сдвиг — для двоичных со знаком
Рис. 1.9. Битовые сдвиги:
а — арифметический сдвиг вправо; б — арифметический сдвиг влево; в — логический сдвиг вправо; г — логический сдвиг влево; д — правый циклический сдвиг (вращение); е — левый циклический сдвиг; ж — правый циклический сдвиг через перенос; з — левый циклический сдвиг через перенос
Циклический сдвиг или разрядное вращение. В этой операции биты, «выдвигаемые» из регистра в любую сторону, «вдвигаются» в регистр с другой его стороны (рис. 1.9, д, е). Эта операция используется, если необходимо сохранить все существующие биты, и часто применяется в цифровой криптографии.
Циклический сдвиг «через перенос». В отличие от обычного сдвига (или сдвига «не через перенос») здесь считается, что два конца регистра отделены флажком переноса («п» на Рис. J.9, ж, з). Бит, который «вдвинут» (с любой стороны регистра), — старое значение флажка переноса, а бит, который «выдвинут» (с противоположной стороны) становится новым значением флажка переноса. Единичный сдвиг через перенос может моделировать логический или арифметический сдвиг позиции, устанавливая флажок переноса заранее. Например, если флажок переноса содержит «О», то правый сдвиг через перенос соответствует логическому сдвигу вправо, а если флажок переноса содержит копию знакового разряда, то это арифметический сдвиг. Поэтому некоторые микроконтроллеры имеют только команды циклического сдвига. Циклический сдвиг через перенос особенно полезен, если операция осуществляется над числами, большими разрядности процессора (двойной или более длины). Если число хранится в двух регистрах, то бит, который «выдвинут» из первого регистра, должен быть «вдвинут» во второй. В данном случает этот бит сохраняется во флажке переноса в течение первого сдвига и готов к участию во втором сдвиге без какой-либо дополнительной подготовки.
Битовые манипуляции. Кроме перечисленных команд, существует большая группа операций, в том или ином виде реализованная в различных процессорах и объединяемая под общим названием «битовые манипуляции/жонглирование» (bit manipulation, bit twiddling, bit bashing). Эти операции связаны с задачами обнаружения и коррекции ошибок, алгоритмами шифрации данных и оптимизации, обработки мультимедийных данных и пр. Например, в ЦП Motorolla 68000 — это команды bset (установка битов в «1»), BCLR (установка битов в «0») и btst (переустановка нулевых битов); в системе команд SSE4 — это popcnt («Population Count» — подсчет количества битов, например установленных в «1») и т. д.
В процессорах архитектуры К10 (AMD) добавлен функциональный (исполнительный) блок расширенных битовых манипуляций — Advanced Bit Manipulation (ABM) — см. рис. 3.33.