Побитовые операции
Предпосылки: Двоичная система и байты, Целые числа.
← Целые числа | Числа с плавающей точкой →
До сих пор число было единым значением: мы складывали, вычитали, сравнивали. Но иногда важно не число целиком, а конкретный бит внутри него. Включён ли флаг? Есть ли разрешение на запись? Установлен ли признак ошибки? Один байт может хранить восемь независимых «да/нет» — и для доступа к каждому из них нужны операции, которые работают не с числом как с величиной, а с каждым битом по отдельности.
Побитовые операции (bitwise operations, от bit + wise — «побитно») делают именно это: берут одно или два числа и применяют логическое действие к каждой паре бит на одной и той же позиции, независимо от остальных позиций.
NOT: инверсия всех бит
Простейшая побитовая операция — NOT (логическое отрицание). Она принимает одно число и переключает каждый бит на противоположный: 0 становится 1, 1 становится 0.
| Бит | NOT |
|---|---|
| 0 | 1 |
| 1 | 0 |
Пример на 8-битном числе:
11010110
--------
NOT = 00101001Если вспомнить обратный код из целых чисел, это ровно та операция, которая давала обратный код (ones’ complement): NOT превращает число в его побитовую инверсию. Для 8-битного беззнакового числа NOT(x) = 255 - x, потому что 11111111 минус любой набор бит даёт зеркальный набор.
NOT — единарная операция: принимает одно число. Все остальные побитовые операции — бинарные: принимают два числа и обрабатывают их попарно, бит за битом.
AND: оба бита равны единице
AND (логическое «и») сравнивает биты попарно. Результат — 1, только если оба бита равны 1. Во всех остальных случаях — 0.
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Зачем это нужно? AND позволяет извлечь определённые биты из числа, обнулив все остальные. Число, в котором единицы стоят только на интересующих позициях, называется маской (mask).
11010110 <-- исходное число
AND
00001111 <-- маска: единицы в младших 4 битах
--------
00000110 <-- результат: только младшие 4 бита сохранилисьМаска 00001111 пропустила младшие 4 бита без изменений, а старшие 4 бита обнулила. Единица в маске означает «пропустить этот бит», ноль — «стереть».
Почему AND работает как фильтр? Потому что 1 AND x = x (единица в маске пропускает исходный бит), а 0 AND x = 0 (ноль в маске стирает бит независимо от того, что там было). Маска — это трафарет: вырезанные места пропускают, закрытые — блокируют.
OR: хотя бы один бит равен единице
OR (логическое «или») даёт 1, если хотя бы один из двух бит равен 1.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
OR позволяет установить конкретный бит, не затрагивая остальные. Если нужно включить бит на позиции 3 (считая с нуля от младшего бита):
11010000 <-- исходное число (бит 3 = 0)
OR
00001000 <-- единица на позиции 3
--------
11011000 <-- бит 3 теперь 1, остальные не изменилисьOR с нулём не меняет бит (0 OR x = x). OR с единицей всегда даёт единицу (1 OR x = 1). Поэтому единицы в правом операнде «включают» нужные позиции, а нули оставляют исходные биты как были.
XOR: ровно один бит равен единице
XOR (exclusive OR, исключающее «или») даёт 1, когда биты различаются, и 0, когда совпадают.
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR переключает бит: если бит был 0, станет 1; если был 1, станет 0. Не нужно знать текущее значение — XOR с единицей гарантированно инвертирует.
11010110 <-- исходное число
XOR
00001000 <-- маска: единица на позиции 3
--------
11011110 <-- бит 3 переключился с 0 на 1У XOR есть полезное свойство: a XOR a = 0 для любого числа. Каждый бит XOR с самим собой даёт 0, потому что биты всегда совпадают. А из этого следует: a XOR b XOR b = a — двойное применение XOR возвращает исходное значение.
Это свойство самообратимости используется на практике. В шифровании: данные XOR ключ = шифротекст, шифротекст XOR ключ = исходные данные. В RAID-массивах: если один диск из трёх вышел из строя, его содержимое восстанавливается XOR-ом двух оставшихся. В контрольных суммах сетевых протоколов: XOR всех байт даёт короткий «отпечаток», по которому можно обнаружить однобитную ошибку.
Сводная таблица четырёх логических операций:
| Операция | Слово | Результат = 1, когда… | Типичное применение |
|---|---|---|---|
| NOT | отрицание | бит был 0 | инверсия всех бит |
| AND | и | оба бита = 1 | извлечение (маска) |
| OR | или | хотя бы один бит = 1 | установка бита |
| XOR | искл. или | биты различаются | переключение бита |
Сдвиги: умножение и деление через перемещение бит
Сдвиг (shift) перемещает все биты числа влево или вправо на заданное количество позиций. Освободившиеся позиции заполняются нулями.
Сдвиг влево (left shift, <<) — каждый бит перемещается на одну или несколько позиций в сторону старших разрядов:
00001010 = 10
<< 2
00101000 = 40Число 10 превратилось в 40. Сдвиг влево на 1 — умножение на 2. Сдвиг на 2 — умножение на 4. Сдвиг на N — умножение на 2^N. Та же логика, что и в десятичной системе: дописать ноль справа к числу 10 — значит умножить на 10. Процессор выполняет сдвиг за один такт, а умножение — за несколько, поэтому сдвиг иногда используется как быстрая замена умножения на степень двойки.
Биты, вышедшие за границу разрядной сетки, теряются. Если сдвинуть 8-битное 11000000 влево на 2, старшие два бита (11) «упадут» с левого края, а результат будет 00000000 — число обнулилось. Сдвиг может вызвать переполнение точно так же, как сложение.
Сдвиг вправо (right shift, >>) — обратная операция, биты перемещаются в сторону младших разрядов:
00101000 = 40
>> 2
00001010 = 10Сдвиг вправо на N — целочисленное деление на 2^N (дробная часть отбрасывается).
Для беззнаковых чисел сдвиг вправо всегда заполняет старшие позиции нулями — это логический сдвиг (logical shift). Но для чисел со знаком в дополнительном коде есть проблема: если старший бит (бит знака) равен 1, логический сдвиг превратит отрицательное число в положительное. Поэтому для знаковых чисел применяют арифметический сдвиг (arithmetic shift): старшие позиции заполняются копией знакового бита, сохраняя знак числа.
Логический сдвиг вправо:
10110000 (-80 в дополнительном коде)
>> 2
00101100 = 44 (знак потерян!)
Арифметический сдвиг вправо:
10110000 (-80 в дополнительном коде)
>> 2
11101100 = -20 (знак сохранён)Четыре логические операции и два сдвига — это весь набор. Каждая по отдельности делает что-то элементарное: инвертирует, фильтрует, включает, переключает, двигает. Но на практике задача звучит иначе: «проверить бит номер 5» или «сбросить бит номер 3, не трогая остальные». Для этого нужны готовые формулы, собранные из базовых операций.
Составные операции: формулы для работы с отдельными битами
Стандартные приёмы для работы с конкретным битом на позиции N (позиции нумеруются с 0 от младшего бита).
Проверить бит N — извлечь один бит и посмотреть, равен ли он единице:
результат = (x >> N) AND 1Сдвигаем число вправо на N позиций — интересующий бит оказывается на позиции 0. AND с 1 обнуляет все остальные биты. Если результат = 1, бит был установлен; если 0 — не был.
Установить бит N — включить бит, не трогая остальные:
результат = x OR (1 << N)Выражение 1 << N создаёт маску с единственной единицей на позиции N. OR с этой маской включает нужный бит.
Сбросить бит N — выключить бит, не трогая остальные:
результат = x AND NOT(1 << N)NOT(1 << N) создаёт маску, в которой все биты — единицы, кроме позиции N. AND с такой маской обнуляет только позицию N.
Переключить бит N — инвертировать бит, не зная его текущее значение:
результат = x XOR (1 << N)XOR с единицей инвертирует бит: 0 станет 1, 1 станет 0.
Все четыре формулы используют одну и ту же идею: 1 << N создаёт маску с единственной единицей на позиции N. Дальше выбор операции зависит от того, что нужно сделать с этим битом.
Пример: число x = 01100010, и нужно установить бит 4.
маска = 1 << 4 = 00010000
x OR маска = 01100010 OR 00010000 = 01110010
^
бит 4 стал 1Проверка: бит 4 установлен?
(01110010 >> 4) AND 1 = 00000111 AND 00000001 = 1 (да)Упаковка данных: два значения в одном байте
Зачем работать с отдельными битами? Один пример: экономия места. Допустим, нужно хранить тип сообщения (8 вариантов) и код кодировки (16 вариантов). Для 8 вариантов достаточно 3 бит (2^3 = 8), для 16 — 4 бита (2^4 = 16). Итого 7 бит, это меньше одного байта. Можно упаковать оба значения в один байт вместо двух.
7 6 5 4 3 2 1 0 <-- номера бит
[ тип | кодировка ]
3 бита 4 бита = 7 бит, 1 бит не используетсяУпаковка — запись двух значений в один байт. Пусть тип = 5 (101 в двоичной), кодировка = 9 (1001 в двоичной):
упакованный_байт = (тип << 4) OR кодировка
= (101 << 4) OR 1001
= 01010000 OR 00001001
= 01011001Распаковка — извлечение значений обратно:
кодировка = упакованный_байт AND 00001111 = 00001001 = 9
тип = (упакованный_байт >> 4) AND 00000111 = 00000101 = 5AND с маской 00001111 извлекает младшие 4 бита — кодировку. Сдвиг вправо на 4 и AND с 00000111 извлекает старшие 3 бита — тип.
Тот же принцип работает повсюду: заголовок IP-пакета хранит версию протокола и длину заголовка в одном байте (4 бита + 4 бита). Инструкция процессора кодирует код операции, регистры и смещение в одном 32-битном слове. Формат цвета RGB565 упаковывает красный (5 бит), зелёный (6 бит) и синий (5 бит) каналы в 16 бит. Во всех случаях идея одна: сдвиг размещает подполе на нужной позиции, AND извлекает, OR записывает.
Права доступа в Unix: маски на практике
Команда chmod 755 в Unix-системах задаёт права доступа к файлу. Три цифры — это три группы по 3 бита, и каждый бит отвечает за конкретное разрешение.
Одна группа из 3 бит:
| Бит | Позиция | Разрешение |
|---|---|---|
| r | 2 | read (чтение) |
| w | 1 | write (запись) |
| x | 0 | execute (выполнение) |
Цифра 7 = 111 в двоичной = rwx (все три разрешения). Цифра 5 = 101 в двоичной = r-x (чтение и выполнение, без записи).
chmod 755 = 111 101 101
rwx r-x r-x
^ ^ ^
| | |
владелец | остальные
группаВладелец может всё (7 = rwx). Группа и остальные пользователи могут читать и запускать файл, но не изменять (5 = r-x).
Как проверить конкретное разрешение? Допустим, нужно узнать, имеет ли группа право на выполнение. Права группы — средняя тройка бит (позиции 3, 4, 5 в полном 9-битном числе). Бит execute в этой тройке — позиция 3.
права = 111101101 (755 в двоичной записи для всех 9 бит)
маска = 000001000 (единица на позиции 3 — execute для группы)
права AND маска = 000001000 (не ноль — разрешение есть)Если результат не равен нулю, разрешение установлено. Если ноль — разрешения нет. Тот же приём работает для любого бита: создаёшь маску с единицей на нужной позиции и применяешь AND.
А чтобы добавить право на запись для группы? Бит write в средней тройке — позиция 4:
новые_права = права OR 000010000
= 111101101 OR 000010000
= 111111101
chmod 775 = 111 111 101
rwx rwx r-xГруппа получила право на запись. Остальные биты не изменились — OR гарантирует, что существующие разрешения не затрагиваются.
Флаги, маски, упаковка — всё это работает с целыми числами. А как быть с дробными? Таймер отсчитывает 0.001 секунды, датчик возвращает 3.7 вольта, вероятность равна 0.73. Дробная часть в конечный набор бит не ложится очевидным образом.
Sources
- Patterson D., Hennessy J., 2017, Computer Organization and Design. Morgan Kaufmann.
- Petzold C., 2000, Code: The Hidden Language of Computer Hardware and Software. Microsoft Press.
- Warren H., 2012, Hacker’s Delight, 2nd ed. Addison-Wesley.