Битовые операции

   Добро пожаловать в мир двоичных чисел! 

   В "компьютерной арифметике" все данные сохраняются в двоичном виде. Операнды представляют собой битовые строки (или векторы) некоторой фиксированной длины. Выражения компьютерной арифметики похожи на выражения обычной арифметики, но в этом случае переменные обозначают содержимое регистров компьютера. Значение выражения компьютерной арифметики представляют собой строку битов без какой-либо специальной интерпретации; операнды же могут интерпретироваться по-разному. Например, в команде сравнения операнды интерпретируются либо как двоичные целые числа со знаком, либо как беззнаковые целые числа. Поэтому в зависимости от типов операндов, для обозначения оператора сравнения используются разные символы.

Часть I. Базовые битовые операции

   Наиболее распространённые операции битовой арифметики: побитовое "и", побитовое "или" и побитовое исключающее "или". Результат выполнения этих операций представлены в следующей таблице:

Операнды		побитовое И	побитовое ИЛИ	побитовое исключающее ИЛИ
A	B	&	|	^
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

   Рассмотрим эти, а также некоторые другие операции и их использование более детально.

   §1.1 Сдвиг влево и сдвиг вправо (<< SHIFT LEFT, >> SHIFT RIGHT). Основная функция операций сдвиг влево (<< SHIFT LEFT) и сдвиг вправо (>> SHIFT RIGHT) - это сдвиг целочисельной переменной на указанное количество бит влево (или вправо), при этом старшие (или младшие) биты "исчезают", т.е. приобретают новые значения, старые значения при этом не сохраняются. Примеры:

Исходное десятичное число	Двоичное представление	Операция	Новое двоичное представление	Новое десятичное значение
5	00000101	5 << 1	00001010	10
5	00000101	5 << 2	00010100	20
5	00000101	5 >> 1	00000010	2
5	00000101	5 >> 2	00000001	1

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

... int n = 5; n = n >> 1;  // значение n = n/2 / * Эту же формулу можно записать в виде n >> = 1 или n /= 2 */ ...

   §1.2 Побитовое И (& AND). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если они оба равны 1 в исходных переменных.

	Двоичное представление	Десятичне значение
x	00000000000000000000000001110100	116
y	00000000000000000000000000101001	41
x & y	00000000000000000000000000100000	32

   Примером использования является подсчёт битов в заданном числе.

Первый способ	Второй способ
... int count_bit_1(int n) {  // считаем слева направо удаляя правый бит     int c = 0;     for (int i=0; i<32; ++i)  // int - 32-битная переменная         if (n & (1 << i))             c++;     return c; } ...	... int count_bit_1(int n) { // то же,  но удаляя левый бит     int c = 0;     for (; n; n>>=1)         if (n & 1)             c++;     return c; } ...

   §1.3 Побитовое ИЛИ (| OR). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если хотя бы один из них равен 1 в исходных переменных.

	Двоичное представление	Десятичне значение
x	00000000000000000000000001110100	116
y	00000000000000000000000000101001	41
x | y	00000000000000000000000001111101	125

   Пример применения: установить 5-й бит в числе раным 1:

... int mark_5th_bit(int n) {     return n | (1 << 4); } ...

   §1.4 Побитовое исключительное ИЛИ (^ XOR). Это функция побитового сравнения двух целочисельных переменных, устанавливающая в новой переменной биты в состояние 1 только в том случае, если в одной и только в одной из исходных переменных один из рассматриваемых двух битов равен 1.

	Двоичное представление	Десятичне значение
x	00000000000000000000000001110100	116
y	00000000000000000000000000101001	41
x ^ y	00000000000000000000000001011101	93

   Пример применения: инвертировать 5-й бит в заданном числе:

... int reverse_5th_bit(int n) {     return n ^ (1 << 4); } ...

   §1.5 Побитовое инвертирование (~ NOT). Это функция побитового инвертирования целочисельной переменной, меняющая значение битов на обратные (0 на 1, а 1 на 0).

	Двоичное представление	Десятичне значение
x	00000000000000000000000000000011	3
~x	11111111111111111111111111111100	-4

   Следует отметить, что эту функцию можно применять и в других целях. Например, если в задаче нужно прочесть некоторое наперёд неизвестное количество целочисельных переменных, то это можно организовать так:

… while(~scanf("%d",&n)) {     … } …

Часть II. Битовые трюки

   §2.1 Манипуляции с младшими битами. Приведённые здесь формулы можно с успехом использовать для ускорения работы многих программ.

   Для того, чтобы обнулить крайний справа единичный бит (01011000=>01010000), использутся формула

x&(x-1)

   Эту формулу можно применять для проверки того, является ли беззнаковое целое степенью 2 (путём проверки результата вычислений на равенство 0).

   Обмен значений 2-х целочисельных переменных:

Первый способ	Второй способ
… void swap(int& x, int& y) {     x = x ^ y;     y = x ^ y;     x = x ^ y; } …	… void swap(int& x, int& y) {     x ^= y ^= x ^= y; } …

   Проверка, является ли число степенью двойки:

… bool ispow2(int n) {     return (n & -n) == n; } …

   Увеличить (уменьшить) целочисельную переменную на единицу:

Увеличить на 1	Уменьшить на 1
… void add_one(int& x) {     return -~x; // ++x } …	… void sub_one(int& x) {     return ~-x; // --x } …

   Замена целого на противоположное:

Первый способ	Второй способ
… void negative(int& x) {     return ~x + 1;          // -x; } …	… void negative(int& x) {     return (x ^ -1) + 1;    // -x; } …

   Проверка целого на чётность (нечётность):

… bool even_or_odd(int& x) {     return x & 1;   // x % 2; } …

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

… int mod(int& x, int& m) // m должно быть степенью двойки {     return x & (m - 1); // x % m; } …

   Вычисление абсолютного значения целого числа:

… int abs(int& x) {     // x < 0 ? -x : x;     return (x ^ (x >> 31)) - (x >> 31); } …

  Вычисление квадратного корня из обратного числа, т.е. для заданного целого n найти квадратный корень от 1/n:

… // 1.0 / sqrt(x) float InvSqrt(float x) {     float xhalf = 0.5f*x;     int i = *(int*)&x;     i = 0x5f3759df - (i>>1);     x = *(float*)&i;     x = x*(1.5f-xhalf*x*x);     return x; } …

   Подсчёт количества значущих бит в 32-битном целом:

... int count_bits(int& x) {         x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1);         x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2);         x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4);         x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8);         x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16);         return x; } ...

  В 32-битном целом поменять порядок битов на обратный:

… int reverse_bits(int& x) {     x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);     x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);     x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);     x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);     x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);     return x; } …

 (Продолжение следует...)