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

Поразрядные операции выполняются над отдельными разрядами или битами чисел. Данные операции производятся только над целыми числами. Но сначала вкратце рассмотрим, что представляют собой разряды чисел.

Двоичное представление чисел

На уровне компьютера все данные представлены в виде набора бит. Каждый бит может иметь два значения: 1 (есть сигнал) и 0 (нет сигнала). И все данные фактически представляют набор нулей и единиц. 8 бит представляют 1 байт. Подобную систему называют двоичной.

Например, число 13 в двоичной системе будет равно 1101₂. Как мы это получили:

// перевод десятичного числа 13 в двоичную систему
13 / 2 = 6      // остаток 1 (13 - 6 *2 = 1)
6 / 2 = 3      // остаток 0 (6 - 3 *2 = 0)
3 / 2 = 1      // остаток 1 (3 - 1 *2 = 1)
1 / 2 = 0      // остаток 1 (1 - 0 *2 = 1)

Общий алгоритм состоит в последовательном делении числа и результатов деления на 2 и получение остатков, пока не дойдем до 0. Затем выстраиваем остатки в линию в обратном порядке и таким образом формируем двоичное представление числа. Конкретно в данном случае по шагам:

1. Делим число 13 на 2. Результат деления - 6, остаток от деления - 1 (так как 13 - 6 *2 = 1)

2. Далее делим результат предыдущей операции деления - число 6 на 2. Результат деления - 3, остаток от деления - 0

3. Делим результат предыдущей операции деления - число 3 на 2. Результат деления - 1, остаток от деления - 1

4. Делим результат предыдущей операции деления - число 1 на 2. Результат деления - 0, остаток от деления - 1

5. Последний результат деления равен 0, поэтому завершаем процесс и выстраиваем остатки от операций делений, начиная с последнего - 1101

При обратном переводе из двоичной системы в десятичную умножаем значение каждого бита (1 или 0) на число 2 в степени, равной номеру бита (нумерация битов идет от нуля):

// перевод двоичного числа 1101 в десятичную систему
1(3-й бит)1(2-й бит)0(1-й бит)1(0-й бит)
1 * 23 + 1 * 22 + 0 * 21 + 1 * 20
=
1 * 8 + 1 * 4 + 0 * 2 + 1 * 1
=
8 + 4 + 0 + 1 
=
13

Представление отрицательных чисел

Для записи чисел со знаком в С++ применяется дополнительный код (two's complement), при котором старший разряд является знаковым. Если его значение равно 0, то число положительное, и его двоичное представление не отличается от представления беззнакового числа. Например, 0000 0001 в десятичной системе 1.

Если старший разряд равен 1, то мы имеем дело с отрицательным числом. Например, 1111 1111 в десятичной системе представляет -1. Соответственно, 1111 0011 представляет -13.

Чтобы получить из положительного числа отрицательное, его нужно инвертировать и прибавить единицу:

Например, получим число -3. Для этого сначала возьмем двоичное представление числа 3:

310 = 0000 00112 

Инвертируем биты

~0000 0011 = 1111 1100

И прибавим 1

1111 1100 + 1 = 1111 1101

Таким образом, число 1111 1101 является двоичным представлением числа -3.

Рассмотрим, как будет идти сложение числа со знаком и без знака. Например, сложим 12 и -8:

1210 = 000011002
+
-810 = 111110002 (8 - 00001000, после инверсии - 11110111, после +1 = 11111000)
=
410 = 000001002

Мы видим, что в двоичной системе получилось число 00000100₂ или 4₁₀ в десятичной системе.

Для большей наглядности в C++ удобно использовать бинарную запись числа, которая предваряется символами 0b:

#include <iostream>

int main()
{
    unsigned int number{0b0000'1100};   // 12
    std::cout << number << std::endl;
}

В данном случае переменная number имеет значение 0b0000'1100, что в десятичной системе соответствует числу 12.

Операции сдвига

Каждое целое число в памяти представлено в виде определенного количества разрядов. И операции сдвига позволяют сдвинуть битовое представление числа на несколько разрядов вправо или влево. Операции сдвига применяются только к целочисленным операндам. Есть две операции:

• <<

  Сдвигает битовое представление числа, представленного первым операндом, влево на определенное количество разрядов, которое задается вторым операндом.

• >>

  Сдвигает битовое представление числа вправо на определенное количество разрядов.

Применение операций:

unsigned int a = 2 << 2;			// 10  на два разрядов влево = 1000 - 8
unsigned int b = 16 >> 3;			// 10000 на три разряда вправо = 10 - 2

Число 2 в двоичном представлении 10. Если сдвинуть число 10 на два разряда влево, то получится 1000, что в десятичной системе равно число 8.

Число 16 в двоичном представлении 10000. Если сдвинуть число 10 на три разряда вправо (три последних разряда отбрасываются), то получится 10, что в десятичной системе представляет число 2.

Можно заметить, что сдвиг на один разряд влево фактически аналогично умножению на 2, тогда как сдвиг вправо на один раз эквивалентно делению на два. Мы можем обобщить: сдвиг влево на n аналогичен умножению числа на 2n, а сдвиг вправо на n разрядов аналогичен делению на 2n, что можно использовать вместо умножения/деления на степени двойки:

#include <iostream>

int main()
{
    unsigned int x{3};
    unsigned int number{7};
    unsigned int result{number << x};    // 7 * 2*2*2 = 56
    std::cout << "Result: " << result << std::endl;
    number = 26;
    result = number >> x;       // 26 / (2*2*2) = 3
    std::cout << "Result: " << result << std::endl;
}

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

Поразрядные операции также проводятся только над соответствующими разрядами целочисленных операндов:

• &: поразрядная конъюнкция (операция И или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1

• |: поразрядная дизъюнкция (операция ИЛИ или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1

• ^: поразрядное исключающее ИЛИ. Возвращает 1, если только один из соответствующих разрядов обоих чисел равен 1

• ~: поразрядное отрицание или инверсия. Инвертирует все разряды операнда. Если разряд равен 1, то он становится равен 0, а если он равен 0, то он получает значение 1.

Применение операций:

int a = 5 | 2;			// 101 | 010 = 111  - 7
int b = 6 & 2;			// 110 & 010 = 10  - 2
int c = 5 ^ 2;			// 101 ^ 010 = 111 - 7
int d = ~9;				// -10

Например, выражение 5 | 2 равно 7. Число 5 в двоичной записи равно 101, а число 2 - 10 или 010. Сложим соответствующие разряды обоих чисел. При сложении если хотя бы один разряд равен 1, то сумма обоих разрядов равна 1. Поэтому получаем:

1	0	1
0	1	0
1	1	1

В итоге получаем число 111, что в десятичной записи представляет число 7.

Возьмем другое выражение 6 & 2. Число 6 в двоичной записи равно 110, а число 2 - 10 или 010. Умножим соответствующие разряды обоих чисел. Произведение обоих разрядов равно 1, если оба этих разряда равны 1. Иначе произведение равно 0. Поэтому получаем:

1	1	0
0	1	0
0	1	0

Получаем число 010, что в десятичной системе равно 2.

Пример практического применения операций

Многие недооценивают поразрядные операции, не понимают, для чего они нужны. Тем не менее они могут помочь в решении ряда задач. Прежде всего они позволяют нам манипулировать данными на уровне отдельных битов. Один из примеров. У нас есть три числа, которые находятся в диапазоне от 1 до 3:

int value1 {3};  // 0b0000'0011
int value2 {2};  // 0b0000'0010
int value3 {1};  // 0b0000'0001

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

#include <iostream>

int main()
{
    int value1 {3};  // 0b0000'0011
    int value2 {2};  // 0b0000'0010
    int value3 {1};  // 0b0000'0001
    int result {0b0000'0000};
    // сохраняем в result значения из value1
    result = result | value1; // 0b0000'0011
    // сдвигаем разряды в result на 2 разряда влево
    result = result << 2;   // 0b0000'1100
    // сохраняем в result значения из value2
    result = result | value2;  // 0b0000'1110
    // сдвигаем разряды в result на 2 разряда влево
    result = result << 2;   // 0b0011'1000
    // сохраняем в result значения из value3
    result = result | value3;  // 0b0011'1001
    std::cout << result << std::endl;   // 57
}

Разберем этот код. Сначала определяем все сохраняемые числа value1, value2, value3. Для хранения результата определена переменная result, которая по умолчанию равна 0. Для большей наглядности ей присвоено значение в бинарном формате:

int result = 0b0000'0000;

Сохраняем первое число в result:

result = result | value1; // 0b0000'0011

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

0b0000'0000
+
0b0000'0011
=
0b0000'0011

Итак, первое число сохранили в result. Мы будем сохранять числа по порядку. То есть сначала в result будет идти первое число, затем второе и далее третье. Поэтому сдвигаем число result на два разряда влево (наши числа занимают в памяти не более двух разрядов):

result = result << 2;   // 0b0000'1100

То есть фактически выполняем следующее вычисление:

0b0000'0011 << 2 = 0b0000'1100

Далее повторяем логическую операцию сложения, сохраняем второе число:

result = result | value2;  // 0b0000'1110

что эквивалентно

0b0000'1100
+
0b0000'0010
=
0b0000'1110

Далее повторяем сдвиг на два разряда влево и сохраняем третье число. В итоге мы получим в двоичном представлении число 0b0011'1001. В десятичной системе это число равно 57. Но это не имеет значения, потому что нам важны конкретные биты числа. Стоит отметить, что мы сохранили в одно число три числа, и в переменной result еще есть свободное место. Причем в реальности не важно, сколько именно битов надо сохранить. В данном случае для примера сохраняем лишь два бита.

Для восстановления данных прибегнем к обратному порядку:

#include <iostream>

int main()
{
    int result {0b0011'1001};
    // обратное получение данных
    int newValue3 = result & 0b000'0011;
    // сдвигаем данные на 2 разряда вправо
    result = result >> 2;
    int newValue2 = result & 0b000'0011;
    // сдвигаем данные на 2 разряда вправо
    result = result >> 2;
    int newValue1 = result & 0b000'0011;
    std::cout << newValue1 << std::endl;   // 3
    std::cout << newValue2 << std::endl;   // 2
    std::cout << newValue3 << std::endl;   // 1
}

Получаем числа в порядке, обратном тому, в котором они были сохранены. Поскольку мы знаем, что каждое сохраненное число занимает лишь два разряда, то по сути нам надо получить лишь последние два бита. Для этого применяем битовую маску 0b000'0011 и операцию логического умножения, которая возвращает 1, если каждый из двух соответствующих разрядов равен 1. То есть операция

int newValue3 = result & 0b000'0011;

эквивалентна

0b0011'1001
*
0b0000'0011
=
0b0000'0001

Таким образом, последнее число равно 0b0000'0001 или 1 в десятичной системе

Стоит отметить, что если мы точно знаем структуру данных, то мы легко можем составить битовую маску, чтобы получить нужно число:

#include <iostream>

int main()
{
    int result {0b0011'1001};
    int recreatedValue1 = (result & 0b0011'0000) >> 4;
    std::cout << recreatedValue1 << std::endl;
}

Здесь получаем первое число, которое, как мы знаем, что оно занимает третий и четвертый бит совокупного числа. Для этого применяем умножение на битовую маску 0b0011'0000. И затем сдвигаем число на 4 разряда вправо.

0b0011'1001
*
0b0011'0000
=
0b0011'0000
>> 4
=
0b0000'0011

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

#include <iostream>

int main()
{
    int value1 {3};  // 0b0000'0011
    int value2 {2};  // 0b0000'0010
    int value3 {1};  // 0b0000'0001
    int result {0b0000'0000};
    // сохраняем в result значения из value1
    result = result | (value1 << 4);
    // сохраняем в result значения из value2
    result = result | (value2 << 2);
    // сохраняем в result значения из value3
    result = result | value3;  // 0b0011'1001
    std::cout << result << std::endl;   // 57
}