17. Побитовые операции, сдвиги и маски
В уроке о двоичной записи число было суммой разрядов: 6 = 4 + 2, поэтому его младшие четыре бита — 0110. Теперь научимся проверять и менять отдельные биты. Это нужно, например, когда одно число хранит несколько независимых признаков: разрешено чтение, запись или выполнение.
Логические операторы проверяют истинность целых выражений. Побитовые операторы работают с соответствующими битами целых чисел. Поэтому 6 && 3 даёт 1, а 6 & 3 даёт 2.
И, или и исключающее или для одного бита
Сначала рассмотрим одну пару битов:
Бит a |
Бит b |
a & b |
a | b |
a ^ b |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
& оставляет 1, только если оба бита равны 1. | даёт 1, если хотя бы один бит равен 1. ^ даёт 1, если биты различаются; это исключающее «или», или XOR. В C знак ^ не означает возведение в степень.
Для многобитного числа это правило применяется к каждому разряду отдельно. Для 6 и 3:
0110 (6) 0110 (6) 0110 (6)
& 0011 (3) | 0011 (3) ^ 0011 (3)
---- ---- ----
0010 (2) 0111 (7) 0101 (5)
В схемах показаны младшие четыре бита. Это не означает, что переменная занимает четыре бита: у этих положительных чисел остальные старшие биты равны нулю.
Полная программа:
#include <stdio.h>
int main(void)
{
unsigned int a = 6u;
unsigned int b = 3u;
printf("AND: %u\n", a & b);
printf("OR: %u\n", a | b);
printf("XOR: %u\n", a ^ b);
printf("Logical AND: %d\n", a && b);
return 0;
}
Вывод:
AND: 2
OR: 7
XOR: 5
Logical AND: 1
Для работы с битами здесь используем unsigned int — целый тип без отрицательных значений. Суффикс u в небольших константах 6u и 3u задаёт тип unsigned int. Результаты побитовых операций над этими переменными тоже имеют этот тип, поэтому выводятся через %u. Результат && имеет тип int и равен 0 или 1, поэтому для него нужен %d.
Другие примеры из той же таблицы правил: 5u & 1u даёт 1, 5u | 2u — 7, 5u ^ 1u — 4. В каждом случае можно записать числа двоично и проверить каждый столбец.
У & и | нет короткого вычисления, которое было у && и ||. Нельзя заменить ими логические операторы в проверке, защищающей от деления на ноль. Побитовые операции требуют целочисленных операндов; float и double для них не подходят.
Инверсия: поменять каждый бит
Оператор ~ применяется к одному числу: каждый 0 превращается в 1, каждый 1 — в 0. Он меняет все биты значения, а не только те четыре разряда, которые мы нарисовали.
Поэтому из схемы 0001 → 1110 ещё нельзя заключить, что ~1u равно 14. Для unsigned int результат — UINT_MAX - 1u, где UINT_MAX из <limits.h> обозначает наибольшее значение этого типа.
Чтобы оставить только младшие четыре бита, применим & 15u. Число 15 имеет младшие биты 1111; старшие разряды такого ограничения равны нулю.
#include <stdio.h>
#include <limits.h>
int main(void)
{
unsigned int value = 1u;
unsigned int inverted = ~value;
printf("Expected unsigned value: %d\n", inverted == UINT_MAX - 1u);
printf("Low four bits: %u\n", inverted & 15u);
return 0;
}
Вывод:
Expected unsigned value: 1
Low four bits: 14
Первая строка печатает результат сравнения, а не само большое число. Это позволяет проверить правило независимо от того, сколько битов использует конкретный unsigned int.
В примере лекции ~1 для знакового int даёт -2 в среде с дополнительным кодом: биты ...0001 превращаются в ...1110. Это нужно отличать от ~1u. В C17 представление знаковых отрицательных чисел зависит от реализации; для переносимых операций с наборами битов удобнее выбрать unsigned int.
Сдвиги: передвинуть разряды
В записи value << n биты сдвигаются влево на n позиций. В записи value >> n — вправо. Для unsigned int освободившиеся позиции заполняются нулями, а биты, вышедшие за границу значения, теряются.
0001 >> 1 = 0000 1 → 0
0001 << 2 = 0100 1 → 4
0101 >> 1 = 0010 5 → 2
00000101 << 3 = 00101000 5 → 40
В последней схеме показаны восемь младших битов, чтобы поместился результат 40. Полная программа:
#include <stdio.h>
int main(void)
{
unsigned int a = 1u;
unsigned int b = 5u;
printf("a >> 1: %u\n", a >> 1);
printf("a << 2: %u\n", a << 2);
printf("b >> 1: %u\n", b >> 1);
printf("b << 3: %u\n", b << 3);
return 0;
}
Вывод:
a >> 1: 0
a << 2: 4
b >> 1: 2
b << 3: 40
Для беззнакового числа сдвиг вправо на одну позицию соответствует целочисленному делению на 2: из 5 / 2 получается 2, дробная часть отбрасывается. Сдвиг влево на одну позицию соответствует умножению на 2, пока результат помещается. Если старшие единицы теряются, обычного математического результата уже не будет: беззнаковое значение сокращается по модулю UINT_MAX + 1. Это математическая запись модуля; вычислять UINT_MAX + 1u для его хранения в том же типе не нужно.
Число позиций должно быть неотрицательным и меньше разрядности левого операнда после целочисленных продвижений. Так называют преобразование небольших целочисленных типов, например char, к int или unsigned int перед операцией. В наших примерах левый операнд уже имеет тип unsigned int, поэтому это преобразование не меняет его тип. Например, если unsigned int в выбранной среде имеет 32 разряда, допустимы количества 0…31; сдвиг на 32 недопустим. Сам по себе суффикс u эту ошибку не исправляет.
Для отрицательного знакового числа сдвиг вправо в C17 зависит от реализации. В показанной в лекции среде старшие позиции заполняются единицами: -3 >> 1 даёт -2. Но -3 / 2 даёт -1. Поэтому правило «сдвиг вправо — это деление» нельзя без оговорки переносить на отрицательные числа. Сдвиг отрицательного знакового числа влево в C17 имеет неопределённое поведение; не используйте его как способ умножения. Для неотрицательного знакового значения результат левого сдвига должен помещаться в тип; переполнение здесь тоже нельзя считать обычным беззнаковым оборачиванием.
Маска: выбрать нужный бит
Битовая маска — число, единицы которого отмечают нужные разряды. Номер самого правого бита — 0. Маски для битов 0, 1, 2, 3 равны 1, 2, 4, 8. Например, 1u << 2 даёт маску 4, то есть младшие биты 0100.
Пусть отдельные биты означают разрешения: 4 — читать, 2 — записывать, 1 — выполнять. Полная программа проверяет, включает, выключает и переключает отдельные признаки:
#include <stdio.h>
enum Permission { EXECUTE = 1, WRITE = 2, READ = 4 };
int main(void)
{
unsigned int flags = READ | EXECUTE;
unsigned int write_mask = WRITE;
unsigned int execute_mask = EXECUTE;
printf("Start: %u\n", flags);
printf("Can read: %d\n", (flags & READ) != 0u);
flags = flags | write_mask;
printf("After set: %u\n", flags);
flags = flags & ~execute_mask;
printf("After clear: %u\n", flags);
flags = flags ^ write_mask;
printf("After toggle: %u\n", flags);
return 0;
}
Вывод:
Start: 5
Can read: 1
After set: 7
After clear: 6
After toggle: 4
Начальные флаги — 101: чтение и выполнение. | 010 включает запись и даёт 111. & ~001 выключает выполнение и оставляет 110. ^ 010 переключает запись: здесь она была включена, поэтому выключается, и остаётся 100.
Для инверсии маска сохранена в unsigned int, чтобы ~ работал именно с беззнаковым значением. Для проверки отдельного бита применяют (flags & mask) != 0u. Для проверки, что установлены все биты составной маски, — (flags & mask) == mask.
У беззнакового числа младший бит показывает чётность: (value & 1u) == 0u истинно для чётного значения. Например, у 6 младшие биты 0110, у 7 — 0111.
Похожая идея есть в записи прав 755 в Unix: цифры задаются в восьмеричной системе. Первая относится к владельцу, вторая — к группе, третья — к остальным. 7 означает 111, а 5 — 101. Это девять обычных битов rwx; у реальных прав доступа существуют и другие механизмы, поэтому вся система доступа ими не исчерпывается. Здесь мы только читаем запись, команды изменения прав выполнять не требуется.
Скобки предотвращают другую проверку
У сравнения == приоритет выше, чем у побитового &. Поэтому 6 & 3 == 3 разбирается как 6 & (3 == 3): сначала получается 1, затем 6 & 1, то есть 0.
Если нужно сначала вычислить побитовое «и», пишите (6 & 3) == 3. Здесь результат тоже 0, но по другой причине: 6 & 3 равно 2, а 2 не равно 3. Скобки меняют смысл, даже когда ответ случайно совпал.
Чтобы увидеть разницу в ответе, возьмём value = 2u. Правильная проверка (value & 4u) == 0u даст 1: бит 4 выключен. Запись без скобок value & 4u == 0u даст 0, потому что сначала вычислит 4u == 0u, а затем 2u & 0.
Сравнения == и != связываются сильнее также, чем побитовые ^ и |. Явно отделяйте побитовую часть скобками: сначала выберите биты, затем сравните результат.
Далее научимся повторять действия с помощью while.
