Доказательство таблицы истинности дистрибутивного закона

На рис. 1.8, а—е приведены иллюстрации к основным логи­ческим операциям и их композициям (так называемые диа­граммы Эйлера — Венна) — области истинности каждого из высказываний и их объединения (дизъюнкции), пересечения (конъюнкции) и других операций. «Первый» из законов де Мор­гана иллюстрируется рис. 1.8, д, е.

Операции над битовыми строками. В некоторых современных ЯП реализованы операции и/или функции обработки битовых строк (машинных слов, их частей или групп, которые могут со­держать числовые, символьные, мультимедийные и пр. данные). Наиболее распространенными являются побитовые операции, прямо вытекающие из рассмотренных ранее операций над логи­ческими данными (табл. 1.21).

Рис.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 manipu­lation, bit twiddling, bit bashing). Эти операции связаны с задачами обнаружения и коррекции ошибок, алгоритмами шифрации дан­ных и оптимизации, обработки мультимедийных данных и пр. Например, в ЦП Motorolla 68000 — это команды bset (установка битов в «1»), BCLR (установка битов в «0») и btst (переустановка нулевых битов); в системе команд SSE4 — это popcnt («Population Count» — подсчет количества битов, например уста­новленных в «1») и т. д.

В процессорах архитектуры К10 (AMD) добавлен функцио­нальный (исполнительный) блок расширенных битовых манипуляций — Advanced Bit Manipulation (ABM) — см. рис. 3.33.