Редактор схемы логических элементов

Операции побитового сдвига

Операций сдвига две – битовый сдвиг влево (оператор <<) и битовый сдвиг вправо (оператор >>). Битовый сдвиг вправо сдвигает биты числа
вправо, дописывая слева нули. Битовый сдвиг влево делает противоположное: сдвигает биты влево, дописывая справа нули. Вышедшие за пределы числа биты отбрасываются.

Например, сдвиг числа 5 влево на 2 позиции

Сдвиг числа 19 вправо на 3 позиции

Независимо от архитектуры (big-endian, или little-endian, или middle-endian) числа в двоичном виде представляются слева направо, от более значащего бита к менее значащему.
Побитовый сдвиг принимает два операнда – число, над которым необходимо произвести сдвиг, и число бит, на которое необходимо произвести сдвиг.

int a = 12;
printf("%d << 1 == %d\n", a, a << 1);
printf("%d << 2 == %d\n", a, a << 2);
printf("%d >> 1 == %d\n", a, a >> 1);
printf("%d >> 2 == %d\n", a, a >> 2);

Так как сдвиг вправо (>>) дописывает слева нули, то для целых чисел операция равносильна целочисленному делению пополам, а сдвиг влево умножению на 2.
Произвести битовый сдвиг для числа с плавающей точкой без явного приведения типа нельзя. Это вызвано тем, что
для си не определено представление числа с плавающей точкой. Однако можно переместить число типа float в int, затем сдвинуть и вернуть обратно

float b = 10.0f;
float c = (float) (*((unsigned int*)&b) >> 2);
printf("%.3f >> 2 = %.3f", b, c);

Но мы, конечно же, получим не 5.0f, а совершенно другое число.

Особенностью операторов сдвига является то, что они могут по-разному вести себя с числами со знаком и без знака, в зависимости
от компилятора. Действительно, отрицательное число обычно содержит один бит знака. Когда мы будем производить сдвиг влево, он может пропасть, число станет
положительным. Однако, компилятор может сделать так, что сдвиг останется знакопостоянным и будет проходить по другим правилам. То
же самое и для сдвига вправо.

unsigned int ua = 12;
signed int sa   = -11;
printf("ua = %d, ua >> 2 = %d\n", ua, ua >> 2);
printf("sa = %d, sa >> 2 = %d\n", sa, sa >> 2);
printf("(unsigned) sa = %u, sa >> 2 = %u\n", sa, sa >> 2);
printf("sa = %d, ((unsigned) sa) >> 2 = %d", sa, ((unsigned) sa) >> 2);

В данном случае при первом сдвиге всё работает, как и задумано, потому что число без знака. Во втором случае компилятор VSE2013 оставляет знак. Однако если посмотреть на
представление этого числа, как беззнакового, сдвиг происходит по другим правилам, с сохранением самого левого бита. В последней строчке, если привести число со знаком к
числу без знака, то произойдёт обычный сдвиг, и мы получим в результате положительное число.

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

int a = 10;
int b = 1;
a >>= 3;
a ^= (b << 3);

Практика

До этого момента в статье была сплошь теория. Сейчас я предлагаю закрепить ее практической частью и собрать восьмибитный сумматор. Нам потребуется пара беспаечных макетных плат, несколько DIP-переключателей, светодиоды для индикации, токоограничивающие резисторы на 10 кОм и пара микросхем 74HC283.

Серия 74xx включает в себя микросхемы самого разного назначения. Это могут быть как сборки логических вентилей (например, 74HC04 — шесть инверторов в одном корпусе), так и полноценные АЛУ (74HC181). Помимо комбинационных схем, там есть и последовательностные: триггеры (74НС74), регистры (74НС373) и счетчики (74НС393).

Чтобы ориентироваться во всем этом номенклатурном разнообразии, я рекомендую не скачивать документацию на каждую микросхему в отдельности, а сразу найти целый справочник по всей серии. Например, есть справочник Texas Instruments в PDF.

Расположение выводов у микросхемы 74HC283 можно найти на странице 176 справочника, принципиальную схему и таблицы истинности смотри на страницах 390–391. И хотя это сумматор всего лишь на четыре бита, тут есть функция ускоренного переноса, а сами микросхемы можно объединять, собирая сумматоры на 8, 16 или даже 32 бит.

Хорошо видно, что схема здесь несколько отличается от той, что мы вывели ранее. В этом нет ничего необычного, одну и ту же функцию можно реализовать несколькими способами, и в производстве зачастую используют тот, который дешевле (по элементам) и лучше подходит для техпроцесса.

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

Кроме того, можно понять, что значение для переноса вычисляется параллельно со значениями разрядов — для этого в микросхеме и присутствуют «лишние» элементы. Пожалуй, это самая сложная часть в статье. Поэтому, если у тебя возникли трудности, попробуй рассмотреть схему ускоренного переноса отдельно — это ИС 74HC182 на с. 338 (вот она, польза от полноценного справочника).

Сложение

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

Как правило, значения в АЛУ попадают из регистров — самого быстрого типа памяти в компьютере. Здесь же я для удобства использую пару DIP-переключателей (левый верхний угол), чтобы можно было легко задавать нужные значения. По сути, это регистры А и В нашего протокомпьютера.

К сожалению, производитель переключателей явно не рассчитывал на такое применение, поэтому нумерация битов в каждом регистре мало того что начинается с единицы, так еще и идет в «неправильном» порядке, слева направо! Учитывай это, когда будешь работать со схемой.

Пара 74НС283 располагается по центру на нижней макетке, а результат операции отображается на линии из светодиодов (правый верхний угол). В левом нижем углу роль источника питания выполняет преобразователь USB — UART (другого способа подать стабильные 5 В я в тот момент не нашел).

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

Вычитание

Удивительно, но такую схему без каких-либо изменений и доработок можно использовать и для вычитания. Да, раньше я не говорил об этом ни слова, но такое действительно возможно. Если использовать представление отрицательных чисел в дополнительном коде, нам никак не нужно переопределять операцию сложения — все будет работать на имеющемся железе.

Наверняка ты уже представляешь, как на уровне цифровой схемы из положительного числа можно сделать отрицательное (в дополнительном коде). Действительно, достаточно только к каждому биту применить операцию , а затем подать на вход сумматора вместе с единицей. Как видишь, подобное представление неочевидно с точки зрения человека, но очень удобно для реализации из набора логических вентилей.

Побитовые И, ИЛИ, НЕ, исключающее ИЛИ

Напомню для начала, что логические операции И, ИЛИ, исключающее ИЛИ и НЕ могут быть описаны с помощью таблиц истинности

В побитовых (bit-wise) операциях значение бита, равное 1, рассматривается как логическая истина, а 0 как ложь. Побитовое И (оператор &) берёт два числа и логически умножает
соответствующие биты. Например, если логически умножить 3 на 8, то получим 0

char a = 3;
char b = 8;
char c = a & b;
printf("%d", c);

Так как в двоичном виде 3 в виде однобайтного целого представляет собой

а 8

Первый бит переменной c равен логическому произведению первого бита числа a и первого бита числа b. И так для каждого бита.

Соответственно, побитовое произведение чисел 31 и 17 даст 17, так как 31 это

, а 17 это

Побитовое произведение чисел 35 и 15 равно 3.

Аналогично работает операция побитового ИЛИ (оператор |), за исключением того, что она логически суммирует соответствующие биты чисел без переноса.

Например,

char a = 15;
char b = 11;
char c = a | b;
printf("%d", c);

выведет 15, так как 15 это , а 11 это 00001011

Побитовое ИЛИ для чисел 33 и 11 вернёт 43, так как 33 это , а 11 это

Побитовое отрицание (оператор ~) работает не для отдельного бита, а для всего числа целиком. Оператор инверсии меняет ложь на истину, а истину на ложь, для каждого бита.
Например,

char a = 65;
char b = ~a;
printf("%d", b);

Выведет -66, так как 65 это , а инверсия даст

что равно -66. Кстати, вот алгоритм для того, чтобы сделать число отрицательным: для нахождение дополнительного кода числа его надо инвертировать и
прибавить к нему единицу.

char a = 107;
char b = ~a + 1;
printf("a = %d, -a = %d", a, b);

Исключающее ИЛИ (оператор ^) применяет побитово операцию XOR. Например, для чисел

char a = 12;
char b = 85;
char c = a ^ b;
printf("%d", c);

будет выведено 89, так как a равно , а b равно . В итоге получим

Иногда логические операторы && и || путают с операторами & и |. Такие ошибки могут существовать в коде достаточно долго,
потому что такой код в ряде случаев будет работать. Например, для чисел 1 и 0. Но так как в си истиной является любое ненулевое значение,
то побитовое умножение чисел 3 и 4 вернёт 0, хотя логическое умножение должно вернуть истину.

int a = 3;
int b = 4;
printf("a & b = %d\n", a & b);	//выведет 0
printf("a && b = %d\n", a && b);//выведет не 0 (конкретнее, 1)

Побитовое И (&), Побитовое ИЛИ (|), Сложение по модулю два (^)

Битовые операторы выполняют свои расчеты на уровне битов переменных. Они помогают решать широкий круг общих проблем программирования. Хорошую статью по битовым операциям можно найти на Википедии.

Побитовое И (&)

В С++ оператор побитового И указывается одиночным амперсандом, он ставится между двумя целыми выражениями. Побитовое И действует на позиции каждого бита, окружающих выражения независимо от того какой из операндов стоит первым, а какой вторым. В соответствии с правилом: если оба входных бита равны 1, результирующий выходной сигнал равен 1, в противном случае выход равен 0. Иллюстрация:

    0  0  1  1    операнд1
    0  1  0  1    операнд2
    ----------
    0  0  0  1    результат (операнд1 & операнд2)

В среде разработки Arduino тип int это 16-битное значение, таким образом оператор побитовое И между двумя int выражениями делает 16 одновременных И операций. Иллюстрация:

int a =  92;    // в двоичном виде: 0000000001011100
int b = 101;    // в двоичном виде: 0000000001100101
int c = a & b;  // результат:    0000000001000100, или 68 в десятичном представлении

Каждый бит значений a и b проходит операцию побитового И, в результате все 16 битов попадают в переменную c, полученное значение будет 01000100, что равносильно 65 в двоичном представлении.
Наиболее часто операция побитового И используется для выбора конкретного бит (или битов) от целого значения, часто называемая маска. См. пример ниже.

Побитовое ИЛИ (|)

Побитовое ИЛИ в C++ обозначается вертикальной чертой, |. Как и оператор &, оператор | работает независимо с каждым битом окружающиъ его чисел. Результат операции побитового ИЛИ двух бит будет 1, если хотя бы один из этих битов 1, иначе резульат будет 0. Другими словами:

    0  0  1  1    операнд1
    0  1  0  1    операнд2
    ----------
    0  1  1  1    (операнд1 | операнд2) - результат

Пример использования операции побитового ИЛИ в фрагменте кода на C++:

int a =  92;    // в бинарном виде: 0000000001011100
int b = 101;    // в бинарном виде: 0000000001100101
int c = a | b;  // результат:    0000000001111101, или 125 в десятичном виде.

Пример программы

Основная область примернения операторов побитовое И/ИЛИ это операции чтение/записи в порт. В микроконтроллерах порт это 8-битовое число, через которое можно получить информацию о состоянии контактов. Записи в порт контролирует все контакты сразу.

PORTD является встроенной константой, которая относится к выходному состоянию цифровых выводов 0,1,2,3,4,5,6,7. Если в каком-то бите установлена 1, значит на выводе состояние HIGH. Вывод при этом должен быть установлен как выход командой pinMode(). Таким образом, если записать PORTD = B00110001; мы установим выводы 2,3 и 7 в состояние логической 1.

Наш алгоритм будет выглядеть вот так:

• Получить значение PORTD и очистить биты относящиеся к выводам, значение которые мы хотим изменить (с помощью побитового И).
• Скомбинировать значение PORTD с нашим новым значением (через операцию побитового ИЛИ).

int i;     // переменная счетчика
int j;
 
void setup(){
DDRD = DDRD | B11111100; 
// установить биты направлений для выводов с 2 по 7, 
// оставить нетронутыми для выводов 0 и 1 (xx | 00 == xx)
// это тоже самое что и оператор pinMode(pin, OUTPUT) для выводов с 2 по 7
Serial.begin(9600);
}
 
void loop(){
for (i=0; i<64; i++){
 
PORTD = PORTD & B00000011;  
// очистить биты с 2 по 7, оставить биты (а занчить и выводы) 0 и 1 неизмененными (xx & 11 == xx)
j = (i << 2);               
// сдвинуть переменную на два бита влево к пинам 2 -7, чтобы не затронуть пины 0 и 1
PORTD = PORTD | j;          
// скомбинирвать значение порта с новым значением
Serial.println(PORTD, BIN); 
// для отладки выведем значение порта в терминал
delay(100);
   }
}

побитовое XOR или исключающее ИЛИ (^)

Еще один побитовый оператор, немного похожий на обычное бинарное ИЛИ, но небольшим отлиием — он вернет 0, если оба бита будут равны 1. Обозначается символом ^.

    0  0  1  1    операнд1
    0  1  0  1    операнд2
    ----------
    0  1  1  0    (операнд1 ^ операнд2) - результат

Другими словами, после операции илсключающего ИЛИ будет 1 в том случае, если входные биты различны или оба равны 0.

Пример кода:

int x = 12;     // в бинарном представлении: 1100
int y = 10;     // в бинарном представлении: 1010
int z = x ^ y;  // в бинарном представлении: 0110, или десятчиная 6

Оператор ^ часто используется для переключения (т.е. чтобы изменить 0 на 1 или 1 на 0) каких-либо битов в цифровом представлении. Пример программы для переключения цифрового вывода 5.

void setup(){
DDRD = DDRD | B00100000; // установили цифровой вывод 5 как выход
Serial.begin(9600);
}

void loop(){
PORTD = PORTD ^ B00100000;  
// переключили бит 5 (цифровой вывод 5),
// остальные оставили нетронутыми
delay(100);
}

Связь с естественным языком

В естественном языке операция «сложение по модулю» эквивалентна двум выражениям:

1. «результат истинен (равен 1), если A не равно B (A≠B)»;
2. «если A не равно B (A≠B), то истина (1)».

Часто указывают на сходство между сложением по модулю 2 и конструкцией «либо … либо …» в естественном языке. Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно. Это в точности соответствует определению операции в булевой алгебре, если «истину» обозначать как 1{\displaystyle 1}, а «ложь» как {\displaystyle 0}.

Эту операцию нередко сравнивают с дизъюнкцией потому, что они очень похожи по свойствам, и обе имеют сходство с союзом «или» в повседневной речи. Сравните правила для этих операций:

1. A∨B{\displaystyle A\lor B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, или оба сразу («хотя бы один из двух»).
2. A⊕B{\displaystyle A\oplus B} истинно, если истинно A{\displaystyle A} или B{\displaystyle B}, но не оба сразу («только один из двух»).

Операция ⊕{\displaystyle \oplus }исключает последний вариант («оба сразу») и по этой причине называется исключающим «ИЛИ».
Операция ∨{\displaystyle \lor }включает последний вариант («оба сразу») и по этой причине иногда называется включающим «ИЛИ».
Неоднозначность естественного языка заключается в том, что союз «или» может применяться в обоих случаях.

FAQ: What do the operators , &, |, ~, and ^ do?

These are Python’s bitwise operators.

Preamble: Twos-Complement Numbers

All of these operators share something in common — they are «bitwise» operators. That is, they operate on numbers (normally), but instead of treating that number as if it were a single value, they treat it as if it were a string of bits, written in twos-complement binary. A two’s complement binary is same as the classical binary representation for positve integers but is slightly different for negative numbers. Negative numbers are represented by performing the two’s complement operation on their absolute value. So a brief summary of twos-complement binary is in order:

Two’s Complement binary for Positive Integers:

• 0 is written as «0»
• 1 is written as «1»
• 2 is written as «10»
• 3 is «11»
• 4 is «100»
• 5 is «101»
• .
• .
• 1029 is «10000000101» == 2**10 + 2**2 + 2**0 == 1024 + 4 + 1

Two’s Complement binary for Negative Integers:

Negative numbers are written with a leading one instead of a leading zero. So if you are using only 8 bits for your twos-complement numbers, then you treat patterns from «00000000» to «01111111» as the whole numbers from 0 to 127, and reserve «1xxxxxxx» for writing negative numbers. A negative number, -x, is written using the bit pattern for (x-1) with all of the bits complemented (switched from 1 to 0 or 0 to 1). So -1 is complement(1 — 1) = complement(0) = «11111111», and -10 is complement(10 — 1) = complement(9) = complement(«00001001») = «11110110». This means that negative numbers go all the way down to -128 («10000000»).

Of course, Python doesn’t use 8-bit numbers. It USED to use however many bits were native to your machine, but since that was non-portable, it has recently switched to using an INFINITE number of bits. Thus the number -5 is treated by bitwise operators as if it were written «…1111111111111111111011».

Whew! With that preamble out of the way (and hey, you probably knew this already), the operators are easy to explain:

The Operators:

x << y

Returns x with the bits shifted to the left by y places (and new bits on the right-hand-side are zeros). This is the same as multiplying x by 2**y.

x >> y

Returns x with the bits shifted to the right by y places. This is the same as //’ing x by 2**y.

x & y

Does a «bitwise and». Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it’s 0.

x | y

Does a «bitwise or». Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it’s 1.

~ x

Returns the complement of x — the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x — 1.

x ^ y

Does a «bitwise exclusive or». Each bit of the output is the same as the corresponding bit in x if that bit in y is 0, and it’s the complement of the bit in x if that bit in y is 1.

Just remember about that infinite series of 1 bits in a negative number, and these should all make sense.

Other Classes

One more point: Python allows operator overloading, so some classes may be written to allow the bitwise operators, but with some other meaning. For instance, the new sets module for Python 2.3 uses | and & for union and intersection.

Таблица операторов

В PHP есть несколько уровней приоритетов, в таблице приведен перечень операторов, отсортированных по уровню приоритета, от высшего к низшему. Операторы на одном уровне имеют одинаковый приоритет.

В колонке «Ассоциативность» помечены операторы, которые имеют правую ассоциативность, остальные относятся к левой.

С этой темой смотрят:

• Присваивание
• Арифметические операторы
• Операторы сравнения
• Логические операторы
• Побитовые операторы

Проверка флага чётности после операции XOR

Команда XOR работает с 8-, 16- и 32-разрядными операциями.

Иногда есть необходимость после выполнения операции проверить флаг чётности PF,
для того, чтобы узнать, какое количество единичных битов (чётное или нечётное)
содержится в младшем байте результата (это бывает необходимо не только в случае
выполнения операции XOR, но и при выполнении других арифметических и логических
операций).

Если флаг чётности установлен, то в результате получилось чётное количество единичных битов. Иначе флаг будет сброшен.

Можно также просто проверить на чётность любое число, не меняя значения результата. Для этого надо выполнить команду XOR с нулевым значением. То есть в ПРИЁМНИКЕ должно быть проверяемое число, а в ИСТОЧНИКЕ должен быть ноль. А затем надо проверить флаг чётности. Пример:

MOV  AL,  10110101b             ;Поместить в AL число с нечётным
                                ;количеством единичных битов (5)
XOR  AL,  0                     ;При этом флаг чётности PF не
                                ;устанавливается (PO)
MOV  AL,  10110111b             ;Поместить в AL число с чётным
                                ;количеством единичных битов (6)
XOR  AL,  0                     ;При этом флаг чётности PF 
                                ;будет установлен (PE)

В отладчиках обычно для обозначения чётного количества единиц в полученном результате используется сокращение PE (Parity Even), а для нечётного — PO (Parity Odd).

Побитовые Операции

Побитовые операции рассматривают каждый операнд как набор из 32 битов (0 и 1), а не как десятеричное, 16-ричное или 8-ричное число. Например, 10-ричное число 9 имеет двоичное представление 1001. Побитовые операции выполняются над такими двоичными представлениями чисел, но возвращают стандартные числовые значения JavaScript.

Таблица 5.4 Побитовые Операции

a & b

a | b

a ^ b

~ a

a << b

a >> b

a >>> b

Побитовые Логические Операции

Концептуально побитовые логические операции работают так:

• Операнды конвертируются в 32-битные целые числа и выражаются сериями битов (0 и 1).
• Каждый бит первого операнда образует пару с битом второго операнда в этой же позиции: первый с первым, второй со вторым и т.д.
• Операция выполняется для каждой пары битов, и результат конструируется побитно.

Например, двоичное представление 9 выглядит как 1001, а представление 15 — как 1111. Поэтому при выполнении побитовых операций с этими значениями, результаты будут такими:

• 15 & 9 даёт 9 (1111 & 1001 = 1001)
• 15 | 9 даёт 15 (1111 | 1001 = 1111)
• 15 ^ 9 даёт 6 (1111 ^ 1001 = 0110)

Операции Побитового Сдвига

Операции побитового сдвига принимают два операнда: первый операнд сдвигается, а второй специфицирует количество битовых позиций, на которое сдвигается первый операнд. Направление операции сдвига контролируется самой операцией.

Операции сдвига конвертируют операнды в 32-битные целые числа, и возвращают результат того же типа, что у левого операнда.

<< (Сдвиг влево)

Эта операция сдвигает влево первый операнд на специфицированное вторым операндом количество бит. Излишние биты, сдвинутые влево, отбрасываются. Справа заполнение идёт нулями.

Например, даёт 36, поскольку 1001, сдвинутое на 2 бита влево становится 100100, что равно 36.

>> (Сдвиг вправо с сохранением знака)

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

Например, 9>>2 даёт 2, поскольку 1001, сдвинутое на 2 позиции вправо, становится 10, то есть 2. Аналогично, -9>>2 даёт -3, поскольку знак сохраняется.

>>> (Сдвиг вправо с заполнением нулями)

Эта операция сдвигает вправо первый операнд на специфицированное вторым операндом количество бит. Излишние биты, сдвинутые вправо, отбрасываются. Слева заполнение идёт нулями.

Например, 19>>>2 даст 4, поскольку 10011, сдвинутое на два бита вправо даст 100, то есть 4. Для неотрицательных значений сдвиг вправо с заполнением нулями и сдвиг вправо с сохранением знака дают один результат.

Заключение

Статья подошла к концу, но цифровая схемотехника на этом отнюдь не заканчивается. Скорее наоборот, только начинается! Мы рассмотрели лишь самые простые комбинационные схемы (за исключением, может быть, ускоренного переноса). За бортом оказались дешифраторы, мультиплексоры, буферы и все последовательностные схемы (они несколько сложнее для понимания).

Кроме того, можно было бы спуститься на уровень ниже и рассказать о том, как собирать логические вентили из дискретных элементов — транзисторов, диодов и резисторов. В разные времена для этого использовали разные технологии, в зависимости от развития промышленности — ТТЛ (транзисторно-транзисторная логика), КМОП (комплиментарный металл-оксид-полупроводник) и другие.

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

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

Интересно, сможем ли мы когда-нибудь собирать квантовые компьютеры так же просто, как сейчас на основе полупроводниковых микросхем?