Двоичная арифметика

Арифметические действия в двоичной системе производятся по обычным для позиционных систем правилам, которые нам известны из десятичной арифметики, но при этом используются таблицы сложения и умножения двоичной системы:

Таблица сложения

Таблица сложения в двоичной системе очень проста. Надо только помнить, что прибавление нуля не меняет число, а один плюс один, будет два.

Таблица умножения

Таблица умножения ещё проще. Здесь нужно твёрдо знать, что любое число, умноженное на нуль, есть нуль и что умножение на единицу не меняет числа.

Сложение многозначных чисел производится точно так же, как и в десятичной системе, то есть поразрядно, начиная с младшего. Например:

Вычитание в двоичной системе выполняется по таким правилам:

Пример:

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

Умножение и деление двоичных чисел практически не отличается от умножения и деления чисел, записанных в десятичной системе счисления. Единственным отличием является то, что при умножении в столбик не приходится находить произведение первого множителя на значения последовательных разрядов второго множителя, так как значение этих разрядов 1 или 0. А при делении в столбик не нужно подбирать неполное делимое, так как учитывая специфику двоичных чисел, неполное делимое можно определить просто посмотрев на делимое.

Примеры: 1101111 · 101101 = ?, 111100 : 1010 = ?

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

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

Основа вычислений

Двоичная цифровая система использует только две цифры — 0 и 1. Компьютеры работают в двоичном формате, что означает, что они хранят данные и выполняют вычисления, используя только нули и единицы.

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

Применение

Побитовые операторы используются в следующих областях:

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

Побитовые операции — как это работает?

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

Побитовые операторы, используемые в C ++

OR (|) — результат является истиной, если любой из операндов истинен.
AND (&) — результат верен, только если оба операнда верны. 
Его можно использовать для настройки маски проверки значений определенных битов. 
XOR (^) — результат является истиной, только если один из его операндов истинен. 
Он используется, в основном, для переключения определенных бит. 
Он также помогает заменять две переменные без использования третьей. 
NOT (~) — побитовое дополнение или инверсия. 
Предоставляет поразрядное дополнение к операнду путем инвертирования его значения, так что все нули превращаются в единицы, а все единицы превращаются в нули. 
>> (Right-Shift) и << (Left-Shift) — оператор, который перемещает биты в число позиций, заданных вторым операндом в правом или левом направлении. 
Операторы сдвига используются для выравнивания битов.

Пример работы

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

Логическая операция AND (&) каждой битовой пары приводит к 1 (истине), если первый и второй биты равны 1. В противном случае результат равен нулю. Среди других применений AND может использоваться для проверки отдельных битов в битовой строке, чтобы увидеть, являются ли они ложным или истинным значением.

Рассмотрим подробнее на примере:

IsOdd = (ValueToTest & 1)! = 0;

Логическая операция ИЛИ (|) каждой битовой пары приводит к 1, если первый или второй бит равен 1. В противном случае результат равен нулю. Логическая операция XOR (~) каждой битовой пары приводит к 1, если два бита различны, и 0, если они одинаковы.

Логический оператор NOT представлен как ^. Левый сдвиг (<<), правый сдвиг (>>) и правый сдвиг нулевой заливки (>>>>) иногда упоминаются как побитовые операторы и называются операторами сдвига бит.

Приоритезация

Порядок приоритетности (от наивысшего до самого низкого) в побитовых операторах при программировании на C:

NOT; 
Right-Shift и Left-Shift); 
AND; 
XOR; 
OR.
Данные операнды используются в большинстве языков программирования.

Поразрядные операции языка С++

При выполнении операции поразрядного отрицания все биты, равные 1, устанавливаются равными 0, а все биты равные нулю, устанавливаются равными 1. Для выполнения данной операции в языке С++ используется символ ‘~’ как показано в следующем примере:

unsigned char var = 153; //двоичная запись 10011001 
unsigned char not = ~var; //результат 01100110 (число 102)

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

10010011 & 00111101 даст результат 
00010001

Для выполнения операции логического И используется символ & следующим образом:

unsigned char var = 153; //двоичная запись 10011001 
unsigned char mask = 0x11; // число 00010001 (число 17) 
unsigned char res = var & mask; // результат 00010001

или

var &= mask;	// то же самое, что и var = var & mask;

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

unsigned char var = 153; //двоичная запись 10011001 
unsigned char mask = 0x11; // число 00010001 
unsigned char res = var | mask; // результат 10011001

Также допускается применение такой записи

Наконец, при операции исключающее ИЛИ результирующий бит устанавливается равным 0, если оба бита соответствующих операндов равны 1 или 0, и 1 в противном случае. Для выполнения данной операции в языке С++ используется символ ‘^’:

unsigned char var = 153; //двоичная запись 10011001 
unsigned char mask = 0x11; // число 00010001 
unsigned char res = var ^ mask; // результат 10001000

или

var ^= mask; // то же самое, что и var = var ^ mask;

Рассмотрим примеры использования логических операций, которые часто применяются на практике. Самой распространенной по использованию является операция логического И. Данная операция обычно используется совместно с так называемыми масками. Под маской понимают битовый шаблон, который служит для выделения тех или иных битов числа, к которому она применяется. Например, если требуется определить, является ли нулевой бит числа установленным в 1 или нет, то для этого задается маска 00000001, которая соответствует числу 1 и выполняется операция поразрядного И:

unsigned char flags = 3; // 00000011 
unsigned char mask = 1; // 00000001 
if((flag & mask) == 1) printf(“Нулевой бит включен”); 
else printf(“Нулевой бит выключен”);

Здесь переменная flags, представленная одним байтом, содержит восемь флаговых битов. Для того чтобы узнать установлен или нет нулевой флаговый бит задается маска со значением 1 и выполняется операция логического И. В результате все биты переменной flags будут равны нулю за исключением нулевого, если он изначально имел значение 1. Таким образом, маска является шаблоном, который как бы накладывается на битовое представление числа, из которого выделяются биты, соответствующие единичным значениям маски. Рассмотренный пример показывает, как одна байтовая переменная flags может содержать восемь флаговых значений и тем самым экономить память ЭВМ.

Следующим примером использования логических операция является возможность включать нужные биты в переменной, оставляя другие без изменений. Для этого используется логическая операция ИЛИ. Допустим, в переменной flags необходимо установить второй бит равным 1. Для этого задается маска в виде переменной mask = 2 (00000010) и реализуется операция логического ИЛИ:

unsigned char flags = 0; // 00000000 
unsigned char mask = 2; // 00000010 
flags |= mask;

Этот код гарантирует, что второй бит переменной flags будет равен 1 без изменений значений других битов.

Для отключения определенных битов целесообразно использовать две логические операции: логическое И и логическое НЕ. Допустим, требуется отключить второй бит переменной flags. Тогда предыдущий пример запишется следующим образом:

unsigned char flags = 0; // 00000000 
unsigned char mask = 2; // 00000010 
flags = flags & ~mask;

или

flags &= ~mask;

Работа этих двух операций заключается в следующем. Приоритет операции НЕ выше приоритета операции И, поэтому переменная mask в двоичной записи будет иметь вид 11111101. Применяя операцию логического умножения переменной flags с полученным числом ~mask все биты останутся неизменными, кроме второго, значение которого будет равно нулю

Наконец, операция исключающее ИЛИ позволяет переключать заданные биты переменных. Идея переключения битов основывается на свойствах операции исключающего ИЛИ: 1^1 = 0, 1^0 = 1, 0^0 = 0 и 0^1 = 1. Анализ данных свойств показывает, что если значение бита маски будет равно 1, то соответствующий бит переменной, к которой она применяется, будет переключен, а если значение бита маски равно 0, то значение бита переменной останется неизменным. Следующий пример демонстрирует работу переключения битов переменной flags.

unsigned char flags = 0; //00000000 
unsigned char mask = 2; //00000010 
flags ^= mask;	//00000010 
flags ^= mask;	//00000000

Кроме логических операций в языке С++ существуют операции поразрядного смещения битов переменной. Операция смещения битов влево определяется знаком << и смещает биты значения левого операнда на шаг, определенный правым операндом, например, в результате выполнения команды

10001010 << 2;

получится результат 00101000. Здесь каждый бит перемещается влево на две позиции, а появляющиеся новые биты устанавливаются нулевыми. Рассмотрим особенности действия данной операции на следующем примере:

int var = 1; 
var = var << 1; //00000010 – значение 2 
var <<= 1;	//00000100 – значение 4

Можно заметить, что смещение битов переменной на одну позицию влево приводит к операции умножения числа на 2. В общем случае, если выполнить сдвиг битов на n шагов, то получим результат равный умножению переменной 2 в степени n на . Данная операция умножения на число 2 в степени n является более быстрой, чем обычное умножения, рассматриваемое ранее.

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

00101011 >> 2;

приведет к результату 00001010. Здесь, также как и при сдвиге влево, новые появляющиеся биты устанавливаются равными нулю. В результате выполнения последовательностей операций

int var = 128; //1000000 
var = var >> 1; //0100000 – значение 64 
var >>= 1;	//0010000 – значение 32

значение переменной var каждый раз делится на 2. Поэтому сдвиг var >>= n можно использовать для выполнения операции деления значения переменной на величину 2 в степени n