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

ЧТО ТАКОЕ ПОБИТОВЫЕ ОПЕРАЦИИ И ЗАЧЕМ ОНИ НУЖНЫ
Побитовые операторы манипулируют отдельными битами в пределах переменной.
В далёком прошлом компьютерной памяти было очень мало и ею сильно дорожили. Это было стимулом максимально разумно использовать каждый доступный бит.
Например, в логическом типе данных bool есть всего лишь два возможных значения (true и false), которые могут быть представлены одним битом, но по факту занимают целый байт памяти! А это, в свою очередь, из-за того, что переменные используют уникальные адреса памяти, а они выделяются только в байтах. Переменная bool занимает 1 бит, а другие 7 тратятся впустую.
Используя побитовые операторы, можно создавать функции, которые позволят уместить 8 значений типа bool в переменной размером 1 байт, что значительно сэкономит потребление памяти. В прошлом такой трюк был очень популярен. Но сегодня, по крайней мере, в прикладном программировании, это не так.

ЧТО ТАКОЕ ПОБИТОВЫЕ ОПЕРАЦИИ И ЗАЧЕМ ОНИ НУЖНЫ
С поддерживает все существующие битовые операторы. Поскольку С создавался, чтобы заменить ассемблер, то была необходимость поддержки всех (или по крайней мере большинства) операций, которые может выполнить ассемблер.
Битовые операции — это тестирование, установка или сдвиг битов в байте или слове, которые соответствуют стандартным типам языка С char и int.
Битовые операторы не могут использоваться с float, double, long double, void и другими сложными типами.
При работе с побитовыми операторами используйте целочисленные типы данных unsigned.

ПОБИТОВЫЕ ОПЕРАЦИИ
Правило: При работе с побитовыми операторами используйте целочисленные типы данных unsigned.

& : ПОРАЗРЯДНАЯ КОНЪЮНКЦИЯ
(операция «И» или поразрядное умножение). Возвращает 1, если оба из соответствующих разрядов обоих чисел равны 1.
Рассмотрим выражение 14 & 5:
1 1 1 0 // 14
0 1 0 1 // 5
--------------
0 1 0 0 // 4

| : ПОРАЗРЯДНАЯ ДИЗЪЮНКЦИЯ
(операция «ИЛИ» или поразрядное сложение). Возвращает 1, если хотя бы один из соответствующих разрядов обоих чисел равен 1.
Рассмотрим выражение 10 | 7:
1 0 1 0 // 10
0 1 1 1 // 7
---------------
1 1 1 1 // 15

^ : ИСКЛЮЧАЮЩЕЕ “ИЛИ”
Побитовое исключающее ИЛИ (^) (англ. «XOR» от «eXclusive OR«). При обработке двух операндов, исключающее ИЛИ возвращает true (1), только если один и только один из операндов является истинным (1). Если таких нет или все операнды равны 1, то результатом будет false (0).
Рассмотрим выражение 6 ^ 3:
0 1 1 0 // 6
0 0 1 1 // 3
---------------
0 1 0 1 // 5

~ : ПОРАЗРЯДНОЕ ОТРИЦАНИЕ ИЛИ ИНВЕРСИЯ.
Инвертирует все разряды операнда. Если разряд равен 1, то он становится равен 0, а если он равен 0, то он получает значение 1.
Рассмотрим выражение ~ 9:
1 0 0 1// 9
0 1 1 0 // 6

ОПЕРАЦИИ АРИФМЕТИЧЕСКОГО СДВИГА
Операции битового сдвига могут быть полезны при декодировании информации от внешних устройств и для чтения информации о статусе.
Операторы битового сдвига могут также использоваться для выполнения быстрого умножения и деления целых чисел.

ОПЕРАТОР ПОБИТОВОГО АРИФМЕТИЧЕСКОГО СДВИГА ВПРАВО >>: A>> B
Оператор >> сдвигает вправо биты выражения A на количество битов, указанных в выражении B.
Для заполнения позиций слева используется бит знака значения A.
Цифры, сдвинутые за пределы диапазона, удаляются.
Тип данных, возвращаемых данным оператором, определяется типом данных выражения A.
Например:
short int temp
temp = -14 >> 2
после вычисления этого кода переменная temp имеет значение -4, поскольку при сдвиге значения -14 (11110010 в двоичном выражении) на два бита в право получается значение -4 (11111100 в двоичном выражении).

Получили дополнительный код отрицательного числа. Проделаем обратную процедуру, чтобы получить прямой код числа и применим позиционную формулу для получения десятичного числа
Обратный код: 1’111111111111011: Прямой код: 1’00000000000100 = - 410

ОПЕРАТОР ПОБИТОВОГО АРИФМЕТИЧЕСКОГО СДВИГА ВЛЕВО <<: A<< B
Оператор << сдвигает влево биты выражения A на количество битов, указанных в выражении B.
“Выталкиваемые наружу” биты пропадают, освобождающиеся биты заполняются нулями.
Тип данных, возвращаемых данным оператором, определяется типом данных выражения А.
Например:
short int temp
temp = -14 << 2
после вычисления этого кода переменная temp имеет значение -56, поскольку при сдвиге значения -14 (11110010 в двоичном выражении) на два бита влево получается значение -56 (10111000 в двоичном выражении).

ОСОБЕННОСТИ ПРИМЕНЕНИЯ СДВИГИ
Операторы битового сдвига могут также использоваться для выполнения быстрого умножения и деления целых чисел. Сдвиг влево равносилен умножению на 2, а сдвиг вправо - делению на 2 (четных чисел).
Сдвинутые биты теряются, а с другого конца появляются нули. В том случае, если вправо сдвигается отрицательное число, слева появляются единицы (поддерживается знаковый бит).

ПРИМЕР
Каждый сдвиг влево приводит к умножению на 2. Обратим внимание, что после сдвига х << 2 информация теряется, поскольку биты сдвигаются за конец байта.
Каждый сдвиг вправо приводит к делению на 2. Обратим внимание, что деление не вернуло потерянные при умножении биты.

ДЛЯ ЧЕГО ПРИМЕНЯЮТСЯ БИТОВЫЕ ОПЕРАЦИИ
Битовое «И» чаще всего используется для выключения битов: любой бит, установленный в 0, вызывает установку соответствующего бита в другом операнде также в 0. Например, следующий фрагмент программы читает символы, вводимые с консоли, и сбрасывает бит четности в 0:
char ch, ch1;
cin >> ch;
ch1 = ch & 127;
cout << ch1<

В последовательной передаче данных часто используется формат 7 бит данных, бит чётности, один или два стоповых бита. Такой формат аккуратно размещает все 7-битные ASCII символы в удобный 8-битный байт.
В следующем примере показано, как работает данный фрагмент программы с битами. В нём предполагается, что ch имеет символ 'А' и имеет бит четности:
Бит чётности

В результате работы программы чётность, отображаемая восьмым битом, устанавливается в 0 с помощью битового «И», поскольку биты с номерами от 1 до 7 установлены в 1, а бит с номером 8 — в 0. Выражение ch & 127 означает, что выполняется битовая операция «И» между битами переменной ch и битами числа 127.
В результате получим ch со сброшенным старшим битом.

ДЛЯ ЧЕГО ПРИМЕНЯЮТСЯ БИТОВЫЕ ОПЕРАЦИИ
Битовое «ИЛИ» может использоваться для установки битов: любой бит, установленный в любом операнде, вызывает установку соответствующего бита в другом операнде. Например, в результате операции 128 | 3 получаем:

ДЛЯ ЧЕГО ПРИМЕНЯЮТСЯ БИТОВЫЕ ОПЕРАЦИИ
Исключающее ИЛИ (XOR) ) устанавливает бит, если соответствующие биты в операндах отличаются. Например, в результате операции 127 ^ 120 получаем:

ДЛЯ ЧЕГО ПРИМЕНЯЮТСЯ БИТОВЫЕ ОПЕРАЦИИ
Оператор битового дополнения ~ инвертирует состояние каждого бита указанной переменной, то есть 1 устанавливается в 0, а 0 — в 1.
Битовые операторы часто используются в процедурах шифрования. Если есть желание сделать дисковый файл нечитабельным, можно выполнить над ним битовую операцию.
Одним из простейших методов является использование битового дополнения для инверсии каждого бита в байте, как показано ниже:
Следует обратить внимание, что в результате выполнения двух битовых дополнений получаем исходное число. Следовательно, первое дополнение будет создавать кодированную версию байта, а второе будет декодировать.

П О Б И Т О В Ы Е О П Е Р А Т О Р Ы П Р И С В А И В А Н И Я
Все битовые операции выполняются слева направо. В следующей строке приведены битовые операции в порядке уменьшения их приоритета.
~, << >>, &, ^, |

ЦЕЛОЧИСЛЕННЫЕ КОНСТАНТЫ НА С++
Целочисленные данные в языке Си могут быть представлены в одной из следующих систем счисления:
По умолчанию целочисленные константы имеют тип int.

ПРИМЕР ЗАДАЧИ НА УСТАНОВКУ НЕОБХОДИМЫХ БИТОВ.
Написать программу, которая позволит ввести два числа типа unsigned int с клавиатуры, найти и вывести на консоль их сумму, далее, используя битовые операции сделать в ней, чтобы 2-й и 1-й биты были равны 0, 3-й бит - равен 1, а остальные сохранили свои значения, вывести результат.
Наша задача – подобрать такие двоичные константы, которые позволят сделать необходимые операции с указанными битами.
ПОМНИМ: нумерация битов начинается слева и с нуля!

int main() // главная функция программы
{
unsigned int a, b, sum; /* описание типов переменных */
setlocale(LC_ALL, "rus"); // для вывода русского шрифта в консоль
printf("\nВведите a\n");
scanf_s("%u", &a); /* вводим a */
printf("\nВведите b\n");
scanf_s("%u", &b); /* вводим a */
sum = a + b; /* нашли сумму */
printf("\nСумма равна a и b =%u", sum); /* вывели сумму на монитор */
sum = sum & 0xfff9; /* установили 2 и 1 биты в 0
fff9, в двоичной системе
1111 1111 1111 1111 1111 1111 1111 1001*/
sum |= 0x8; /* установили 3 бит в 1
8, в двоичной системе
0000 0000 0000 0000 0000 0000 0000 1000 */
printf("\nПосле преобразования sum=%u\n", sum);
system("pause");
return 0; // вернулись в среду разработки
}

РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ
2210=1616=0000 0000 0001 01102 – тип unsigned int
0xfff9= 1111 1111 1111 1001 – по умолчанию эта константа имеет тип int и имеет, соответственно, 32 бита, но старшие 16 бит никак не повлияют на тип unsigned int и мы, можем старшие 16 бит не рассматривать.

ПРИМЕР ЗАДАЧИ НА ПРИМЕНЕНИЕ БИТОВЫХ ОПЕРАЦИЙ
Написать программу, которая позволит ввести число x типа unsigned int с клавиатуры, напечатать его и, используя битовые операции, поменять в нем четверки и восьмерки бит по схеме

КОНТРОЛЬНЫЙ ПРИМЕР ДЛЯ 6553710 =1000116
ПОЛУЧИЛИ: 100100016 = 166 + 163 = 1678131210

int main()
{unsigned int lx, l41, l42, l43, l44, l83;
setlocale(LC_ALL, "rus"); // для вывода русского шрифта в консоль
printf("\n Введите число : "); /* поясняющая надпись */
scanf_s("%ld", &lx); /* вводим число */
printf("\n Введено число lx = %ld ( 16-format: %X) \n", lx,lx); /* вывели число */
l41 = lx & 0xf; /* нашли первую четверку */
l42 = lx & 0xf0; /* нашли вторую четверку */
l43 = lx & 0xf00; /* нашли третью четверку */
l44 = lx & 0xf000; /* нашли четвертую четверку */
l83 = lx & 0xff0000; /* нашли третью восьмерку */
/* поставили четвертую восьмерку на место третьей
и обнулили младшие шестнадцать и старшие 8 бит */
lx = (lx >> 8) & 0xff0000;
/* поставили все на место */
lx += (l41 << 12) + (l42 << 4) + (l43 >> 4) + (l44 >> 12) + (l83 << 8);
/* вывели полученное значение на монитор */
printf("\n После преобразования число равно %ld ( 16-format: %X)\n", lx, lx);
system("pause"); return 0; }

ПОЛУЧИЛИ: 100100016 = 166 + 163 = 1678131210

ПРИМЕР ЗАДАЧИ НА ПРИМЕНЕНИЕ БИТОВЫХ ОПЕРАЦИЙ
Дано число k, 0 ≤ k ≤ 31. Не используя арифметические операторы сложения, умножения, вычитания, деления, взятия остатка, вычислить 2k, применяя побитовые операторы
&, |, ~, ^, <<, >>.
Контрольный пример:
20 = 110 = 000000012
21 = 210 = 000000102
22 = 410 = 000001002
…..
Очевидно, что степень k позволяет сместить 1 влево на k позиций