Вопросы
Где это можно попробовать?
Битовый калькулятор показывает каждый бит результата для AND, OR, XOR, сдвигов и вращений на 8–64 битах, а калькулятор битовых масок строит маски по позициям.
Шпаргалка по битовым трюкам
Каждая идиома здесь работает в C, Go, Rust, Java и JavaScript (32 бита) с теми же операторами; в Python тоже, с неограниченными целыми.
Помещается на одну вертикальную страницу A4 / Letter; выберите «Сохранить как PDF» в диалоге печати, чтобы оставить себе копию.
Операторы
| a & b | AND: 1 там, где оба равны 1 |
| a | b | OR: 1 там, где хотя бы один равен 1 |
| a ^ b | XOR: 1 там, где они различаются |
| ~a | NOT: инвертирует все биты (= −a − 1 в дополнительном коде) |
| a << n | сдвиг влево: × 2ⁿ |
| a >> n | сдвиг вправо: ÷ 2ⁿ, округляет к −∞ для знаковых (арифметический) |
| a >>> n | логический сдвиг вправо (JS, Java); в других языках — беззнаковые типы |
Отдельные биты (бит n, 0 = младший)
| x & (1 << n) | проверка: не ноль, если установлен |
| (x >> n) & 1 | получить бит как 0 или 1 |
| x | (1 << n) | установить |
| x & ~(1 << n) | сбросить |
| x ^ (1 << n) | переключить |
| (x & ~(1 << n)) | (b << n) | установить бит n в b |
Маски и поля
| (1 << n) - 1 | маска младших n битов |
| ((1 << w) - 1) << lo | маска w битов начиная с lo |
| (x >> lo) & ((1 << w) - 1) | извлечь w-битное поле в позиции lo |
| (x & ~m) | ((v << lo) & m) | вставить v в поле с маской m |
| (x & FLAGS) == FLAGS | все флаги установлены |
| x & FLAGS | хотя бы один флаг установлен |
Младший / старший бит
| x & -x | выделить младший установленный бит |
| x & (x - 1) | сбросить младший установленный бит |
| x | (x + 1) | установить младший нулевой бит |
| x & (x + 1) | сбросить завершающие единицы |
| x | (x - 1) | установить завершающие нули |
| ctz(x) = log₂(x & -x) | индекс младшего установленного бита (__builtin_ctz, bits.TrailingZeros) |
| 31 - clz(x) | индекс старшего установленного бита = ⌊log₂ x⌋ |
Проверки
| x && !(x & (x - 1)) | является степенью двойки |
| (x & 1) == 0 | чётное |
| (x ^ y) < 0 | противоположные знаки (знаковые) |
| (x & (a - 1)) == 0 | выровнено по a (a = 2ⁿ) |
| x == (x & 0xFF) | помещается в байт |
Арифметика
| (x + a - 1) & -a | округлить вверх до кратного a (a = 2ⁿ) |
| x & -a | округлить вниз до кратного a |
| x & (a - 1) | x mod a (a = 2ⁿ, x ≥ 0) |
| (x + y) >> 1 | среднее (может переполниться); (x & y) + ((x ^ y) >> 1) — нет |
| x ^= y; y ^= x; x ^= y | обмен без временной переменной (медленнее, чем с ней; курьёз) |
| (x ^ (x >> 31)) - (x >> 31) | модуль, 32-битное знаковое |
| x ^ (x >> 1) | двоичный → код Грея |
Подсчёт и разворот
| while (x) { x &= x - 1; n++; } | popcount (Керниган); или __builtin_popcount, bits.OnesCount, int.bit_count() |
| x ^ y, затем popcount | расстояние Хэмминга |
| popcount(x) & 1 | чётность |
| bswap32(x) / bits.ReverseBytes32 | поменять порядок байтов (endianness) |
| bits.Reverse32(x) | развернуть порядок битов |
Осторожно
- Сдвиг на ≥ ширины не определён в C/C++; в JS и Java маскируется (
1 << 32 == 1). - Битовые операции в JS усекают до 32 бит; выше используйте BigInt.
~на беззнаковых типах в C расширяет тип; приводите обратно.- Сдвиг вправо отрицательного знакового значения в C определяется реализацией до C++20 (на практике везде арифметический).
- Приоритет:
&связывает слабее, чем==; пишите(x & m) == m.
Результаты и сообщения этого инструмента выводятся на английском языке.