4.06. Битовые операции и представление данных в памяти
Битовые операции и представление данных в памяти
Представление целых чисел: прямой, обратный, дополнительный код
Плавающая точка (IEEE 754)
Эндианность
Битовые фокусы: подсчёт битов, проверка степени двойки, обмен без временной переменной
Применение: сетевые протоколы, криптография, сжатие
фундамент для low-level инженерии и понимания работы железа.
Битовые операции и представление данных в памяти
Фундамент для понимания работы аппаратуры и низкоуровневого программирования
Бит
Современные вычислительные машины оперируют данными, представленными в двоичной системе: каждый физический элемент памяти или регистра хранит одно из двух устойчивых состояний — условно обозначаемых как 0 и 1. Такое состояние называется битом — сокращение от binary digit. Бит не является самостоятельной единицей измерения информации в практическом смысле, но именно он лежит в основе всех цифровых представлений: от управляющих сигналов процессора до графических пикселей и шифрованных сообщений.
Группировка битов в более крупные единицы — байты (обычно восемь битов), машинные слова (часто 32 или 64 бита), — позволяет кодировать логические значения, числа, символы, инструкции процессора. Внутри компьютера всё равно остаётся последовательностью битов: разница между числом, текстом и изображением — не в их «природе» на уровне железа, а в том, как интерпретирует эту последовательность программа или устройство.
Таким образом, битовые операции — это базовый слой, через который реализуется любая логика. Они позволяют напрямую манипулировать составом данных, не полагаясь на абстракции языков высокого уровня. Знание принципов их применения необходимо при написании драйверов или компиляторов, при диагностике неочевидных ошибок, оптимизации производительности, проектировании протоколов и работе с аппаратными интерфейсами.
Представление целых чисел
Когда речь заходит о хранении чисел в памяти, возникает несколько фундаментальных вопросов. Как различать положительные и отрицательные значения? Как обеспечить однозначное соответствие между числом и его двоичным представлением? Как сделать так, чтобы операции сложения и вычитания работали одинаково для всех чисел без отдельной обработки знака?
Первый подход, исторически появившийся в ранних ЭВМ, — прямой код. В нём старший бит слова используется как знак: 0 означает неотрицательное число, 1 — отрицательное, а остальные биты кодируют модуль. Простота этой схемы обманчива: при сложении чисел разного знака требуется отдельная логика, а операция +0 и −0 дают два разных представления (0000…0 и 1000…0), что создаёт неоднозначность при сравнении. Прямой код оказался непрактичным для аппаратной реализации арифметики, и на смену ему пришёл обратный код.
В обратном коде отрицательное число получается инверсией всех битов модуля. Например, если +5 — это 00000101, то −5 будет 11111010. Здесь также сохраняется два нуля, и хотя сложение с переносом из старшего разряда частично решает проблему знака (так называемый циклический перенос), оно остаётся громоздким: после обычного сложения нужно дополнительно проверять и прибавлять перенос из знакового разряда. Это увеличивает задержку в арифметико-логическом устройстве и снижает производительность.
Современные процессоры используют дополнительный код — представление, которое устраняет обе проблемы: существует ровно один ноль, и сложение (включая вычитание, реализуемое как сложение с дополнением) выполняется одинаково для всех целых чисел без дополнительных проверок знака. В дополнительном коде отрицательное число получается инверсией всех битов положительного числа и прибавлением единицы к младшему разряду. С точки зрения интерпретации: дополнительный код — это такое представление, при котором значение отрицательного числа −x в n-битном слове равно числу 2ⁿ − x, рассматриваемому как беззнаковое.
Это позволяет рассматривать все n-битные последовательности как элементы кольца вычетов по модулю 2ⁿ. Операция переполнения при сложении тогда становится естественной — она «оборачивается» и даёт корректный результат в рамках модулярной арифметики. Именно поэтому процессоры не генерируют исключения при целочисленном переполнении: с точки зрения аппаратуры, такой результат не является ошибкой — он корректен в контексте дополнительного кода. Исключения возникают только тогда, когда программист явно требует проверки (например, в C# с помощью ключевого слова checked), но по умолчанию арифметика беззнаковая и знаковая ведёт себя одинаково на уровне битов.
Пример: восьмибитное слово 11111111. В беззнаковой интерпретации — это 255. В знаковой, в дополнительном коде — это −1, поскольку 2⁸ − 1 = 256 − 1 = 255, а отрицательное число, соответствующее 255, — это −1. Аналогично, 10000000 — это 128 беззнаково и −128 знаково. Именно −128, а не −0: минимальное представимое число по модулю на единицу больше максимального положительного (127), — это следствие асимметрии диапазона в дополнительном коде, и именно поэтому самое отрицательное число не имеет положительного аналога.
Эта деталь имеет практическое значение: при арифметических операциях, особенно умножении или делении, нужно учитывать, что −(−128) не представимо в восьмибитном знаковом виде. В языках, где знаковый тип фиксированной ширины (например, int8_t в C), такое преобразование приводит к неопределённому поведению или молчаливому переполнению.
Плавающая точка
Целочисленные типы не позволяют представлять дробные значения, а диапазон их значений растёт линейно с увеличением разрядности. Для научных, инженерных и финансовых вычислений требуется иной подход — возможность кодировать числа с широким диапазоном величин и переменной абсолютной точностью. Такой подход реализован в стандарте IEEE 754, принятом в 1985 году и многократно уточнявшемся с тех пор (последняя редакция — IEEE 754-2019).
Основная идея плавающей точки — аналог научной записи в десятичной системе. Число представляется в виде трёх компонентов: знак, мантисса (или сигнификанд), и порядок (экспонента). Например, десятичное число −123.45 можно записать как −1.2345 × 10². Здесь − — знак, 1.2345 — мантисса, 2 — порядок при основании 10.
В двоичной системе основание фиксировано и равно двум. Число имеет вид
±1.ммммм…м × 2ᴱ,
где мммм…м — биты дробной части мантиссы, а E — целочисленный порядок со смещением. Для нормализованных чисел старший бит мантиссы всегда равен единице, поэтому он не хранится явно — его называют неявным битом или ведущей единицей. Это позволяет сэкономить один бит без потери точности.
Стандарт IEEE 754 определяет несколько форматов. Наиболее распространены:
- binary32 (одинарная точность): 1 бит знака, 8 бит порядка, 23 бита дробной части мантиссы (итого 32 бита);
- binary64 (двойная точность): 1 + 11 + 52 бита (64 бита);
- binary16 (половинная точность): 1 + 5 + 10 бит — используется в машинном обучении и графике для экономии памяти.
Порядок хранится со смещением (bias), чтобы не использовать знаковый тип. Для binary32 смещение равно 127, для binary64 — 1023. Таким образом, реальный порядок вычисляется как E = stored_exponent − bias. Значения порядка 0 и максимальное (255 для binary32, 2047 для binary64) зарезервированы для специальных случаев.
Когда сохранённый порядок равен нулю, число считается денормализованным (subnormal). В этом режиме ведущий бит мантиссы становится нулём, и число имеет вид
±0.мммм…м × 2^(1−bias).
Денормализованные числа позволяют постепенно приближаться к нулю, избегая резкого скачка в минимально представимом ненулевом значении. Это важно для численной устойчивости: например, при вычитании двух близких чисел результат не обнулится преждевременно.
Когда порядок максимален, а мантисса нулевая — получаем плюс или минус бесконечность (+∞ / −∞). Это корректные значения, участвующие в арифметике: 1.0 / 0.0 = +∞, log(0) = −∞, ∞ + конечное = ∞. Если при этом мантисса ненулевая — это значение Not a Number (NaN), которое обозначает неопределённый или некорректный результат: 0.0 / 0.0, ∞ − ∞, sqrt(−1). Важно, что NaN не равен ничему, даже самому себе: сравнение x == x возвращает false, если x — NaN.
Особое внимание уделяется нулю. В IEEE 754 существует как +0, так и −0. Их битовые представления различаются только в знаковом бите. Арифметически они ведут себя одинаково в большинстве операций, но различаются при делении (1.0 / +0 = +∞, 1.0 / −0 = −∞) и в некоторых функциях (atan2, copysign). Это позволяет сохранять информацию о направлении предела.
Стандарт также регламентирует поведение при переполнении (overflow — результат слишком велик), исчезновении порядка (underflow — результат слишком близок к нулю), а также политики округления: к ближайшему чётному, вниз, вверх, к нулю и др. По умолчанию используется округление к ближайшему чётному (round to nearest, ties to even), что минимизирует накопление ошибок при последовательных операциях.
Несмотря на широкое распространение, IEEE 754 не гарантирует точной арифметики: из-за конечного числа битов большинство вещественных чисел не представимы точно. Например, десятичная дробь 0.1 имеет бесконечное двоичное разложение, как 1/3 в десятичной системе, и хранится приближённо. Это приводит к известным «странностям» вроде 0.1 + 0.2 ≠ 0.3 в прямом побитовом сравнении. Программист должен осознавать, что плавающая точка — это компромисс между диапазоном, точностью и скоростью, и ни в коем случае не замена для финансовых расчётов (где используют десятичные типы — например, decimal в C# или BigDecimal в Java).
Эндианность
Любое многобайтовое значение — будь то 16-битное целое, 32-битное слово или 64-битное число с плавающей точкой — физически хранится в памяти как последовательность отдельных байтов. Вопрос в том: в каком порядке эти байты располагаются по растущим адресам?
Этот порядок называется эндианностью (от английского endianness), и он определяется архитектурой процессора. Существует два основных варианта:
- Little-endian — младший байт (least significant byte, LSB) располагается по наименьшему адресу, старший байт (most significant byte, MSB) — по наибольшему.
- Big-endian — старший байт по наименьшему адресу, младший — по наибольшему.
Для наглядности рассмотрим 32-битное число 0x12345678 (в шестнадцатеричной записи). Оно состоит из четырёх байтов: 0x12, 0x34, 0x56, 0x78, где 0x12 — старший, 0x78 — младший.
В памяти по адресам A, A+1, A+2, A+3 это число будет храниться так:
| Адрес | Little-endian | Big-endian |
|---|---|---|
| A | 0x78 | 0x12 |
| A+1 | 0x56 | 0x34 |
| A+2 | 0x34 | 0x56 |
| A+3 | 0x12 | 0x78 |
Термин «эндианность» происходит от аллегории в «Путешествиях Гулливера», где спор между лилипутами о том, с какого конца раскалывать яйцо — с большого или с малого — служил метафорой религиозных и политических конфликтов. В вычислительной технике аналогия сохраняется: выбор порядка — это вопрос соглашения и совместимости.
Архитектура x86 и x86-64, доминирующая в настольных и серверных системах, использует little-endian. Это связано с историей: процессоры Intel 8086 и предшествующие (8008, 8080) уже применяли такой порядок, и сохранение совместимости стало приоритетом. Архитектура ARM, хотя и поддерживает оба режима, по умолчанию в большинстве реализаций (особенно в мобильных устройствах) работает в little-endian. В то же время, многие сетевые протоколы, форматы файлов и RISC-процессоры (например, SPARC, PowerPC в некоторых режимах, старые MIPS) используют big-endian. Его часто называют сетевым порядком байтов (network byte order), поскольку протоколы TCP/IP стандартизированы именно на нём.
Зачем это важно? Потому что при передаче данных между системами с разной эндианностью — например, с сервера на ARM (little-endian) клиенту на PowerPC (big-endian), или при чтении двоичного файла, записанного на одной машине, на другой — интерпретация байтов как числа даёт некорректный результат, если не выполнить преобразование.
Рассмотрим пример: в сетевом заголовке TCP поле Source Port занимает два байта и задаётся в big-endian. Если принять эти два байта 0x1F90 как little-endian, то значение будет интерпретировано как 0x901F = 36895, хотя на самом деле это 0x1F90 = 8080, стандартный порт HTTP-прокси. Такая ошибка приводит к неработоспособности соединения.
Для предотвращения подобных ситуаций используются стандартные функции преобразования порядка байтов. В POSIX-совместимых системах это htonl (host to network long), htons (host to network short), ntohl, ntohs. Они проверяют, совпадает ли порядок байтов хоста с сетевым (big-endian), и если нет — переставляют байты. На little-endian машине htons(0x1234) вернёт 0x3412; на big-endian — оставит без изменений.
Эндианность не влияет на отдельные биты внутри байта — бит 0 всегда младший, бит 7 — старший. Проблема возникает только при интерпретации последовательности байтов как единого многобайтового значения. Операции сдвига (<<, >>) также работают одинаково вне зависимости от эндианности, потому что они манипулируют логическим представлением числа, а не его физическим расположением в памяти.
Существуют и гибридные схемы — например, middle-endian или mixed-endian, когда порядок меняется внутри 16-битных слов, но не между ними (как в некоторых старых процессорах PDP-11). Они встречаются крайне редко и считаются историческим курьёзом.
Для разработчика кроссплатформенного ПО хорошей практикой является:
- Избегать прямого каста указателей (например,
*(uint32_t*)buf) при чтении двоичных данных; - Читать байты по одному и собирать число явно с учётом ожидаемого порядка;
- Использовать сериализацию с чётко определённым endianness (как в Protocol Buffers, где порядок big-endian для переменной длины — varint — реализован через побайтовую упаковку, а не через прямую запись машинного слова).
Битовые фокусы
Битовые операции — это не только &, |, ^, ~, <<, >>. Это инструмент для решения задач, которые на первый взгляд кажутся арифметическими или логическими, с помощью манипуляций на уровне битовых последовательностей. Такие приёмы, часто называемые битовыми трюками (bit hacks), возникли в эпоху ограниченных ресурсов, когда каждый такт процессора и каждый байт памяти имели значение. Сегодня они по-прежнему актуальны в системном программировании, драйверах, криптографии, компиляторах и высокопроизводительных библиотеках.
Битовый трюк — это результат глубокого понимания двоичного представления и свойств логических операций. Многие из них основаны на инвариантах дополнительного кода, симметрии инверсии или цикличности сдвига.
Проверка, является ли число степенью двойки
Число, являющееся степенью двойки (например, 1, 2, 4, 8, 16…), в двоичной записи имеет ровно один установленный бит: 1 = 0b0001, 8 = 0b1000. Если вычесть из него единицу, все младшие биты инвертируются, а единственный установленный бит обнулится: 8 − 1 = 7 = 0b0111. Побитовое И исходного числа и результата вычитания будет нулём.
Таким образом, условие (x & (x − 1)) == 0 истинно тогда и только тогда, когда x — степень двойки или ноль. Чтобы исключить ноль, добавляется проверка x != 0. Итоговое выражение:
(x != 0) && ((x & (x − 1)) == 0).
Этот приём используется, например, при проверке размеров буферов в алгоритмах на основе циклических буферов или при выравнивании памяти до границы, кратной степени двойки.
Подсчёт установленных битов (population count)
Число единичных битов в слове — важная метрика в криптографии (вес Хэмминга), сжатии, хешировании и проверке чётности. Наивный подход — цикл по всем битам с проверкой маски. Эффективный способ — метод разделения и накопления.
Идея: сначала складываем пары битов, затем четвёрки, затем восьмёрки и т. д., используя маски и сдвиги. Например, для 32-битного слова:
- Складываем соседние биты:
(x & 0x55555555) + ((x >> 1) & 0x55555555)→ в каждом двухбитовом блоке — количество единиц в исходных двух битах; - Складываем двухбитовые блоки в четырёхбитовые: маска
0x33333333, сдвиг на 2; - Четырёхбитовые в восьмибитовые: маска
0x0F0F0F0F, сдвиг на 4; - И так далее.
Современные процессоры (начиная с Intel Nehalem и ARMv8) имеют аппаратную инструкцию POPCNT, которая выполняет эту операцию за один такт. Компиляторы автоматически заменяют соответствующие последовательности на popcnt, если целевая архитектура её поддерживает.
Обмен значениями без временной переменной
Известный трюк с тремя операциями XOR:
a = a ^ b;
b = a ^ b; // теперь b = (a ^ b) ^ b = a
a = a ^ b; // теперь a = (a ^ b) ^ a = b
Теоретически он экономит один регистр или одну ячейку памяти. На практике он редко даёт выигрыш: современные компиляторы оптимизируют обычный обмен с временной переменной так же эффективно или лучше, а XOR-обмен ломает анализ потока данных, мешает параллелизации и не работает, если a и b — один и тот же объект (например, swap(&x, &x) приведёт к обнулению x). Поэтому его применение считается скорее академическим.
Выравнивание до границы
Часто требуется выровнять адрес addr до ближайшей верхней границы, кратной N, где N — степень двойки (например, 8, 16, 4096). Формула:
(addr + N − 1) & ~(N − 1).
Пояснение: N−1 — маска из k младших единиц, если N = 2ᵏ. Инверсия даёт маску с k нулями в младших разрядах. Прибавление N−1 «подталкивает» значение к следующей границе, а побитовое И обнуляет младшие биты, оставляя только выровненную часть.
Пример: addr = 1005, N = 8.
N−1 = 7 = 0b111, ~7 = ...11111000,
1005 + 7 = 1012 = 0b1111110100,
1012 & ~7 = 1008 — ближайшее кратное 8 ≥ 1005.
Этот приём фундаментален при работе с кэш-линиями, выделении памяти в аллокаторах, организации буферов DMA.
Применение битовых операций в реальных системах
Сетевые протоколы
В заголовках IP, TCP, UDP, Ethernet и других протоколов поля часто имеют неоктетную ширину — 3 бита для типа сервиса в IPv4, 4 бита для версии, 12 бит для идентификатора фрагмента. Это сделано для экономии места: каждый бит имеет смысл, и упаковка позволяет удерживать заголовок в пределах минимального размера.
При разборе пакета программист использует сдвиги и маски:
- Из байта
0x45(первый байт IPv4-заголовка) старшие 4 бита дают версию:0x45 >> 4 = 4; - Младшие 4 бита — длина заголовка в 32-битных словах:
0x45 & 0x0F = 5, то есть 20 байт.
Аналогично, флаги фрагментации (MF, DF) и смещение фрагмента упакованы в одно 16-битное поле. Извлечение требует комбинации & и >>.
Криптография
Большинство симметричных шифров (AES, DES, ChaCha20) и хеш-функций (SHA-2, SHA-3) построены на последовательности битовых операций: XOR для смешивания, циклические сдвиги и вращения (ROL, ROR) для диффузии, подстановки через S-box (которые, в свою очередь, могут быть реализованы через таблицы или комбинации логических операций).
Например, в AES шаг SubBytes использует нелинейное преобразование с инверсией в поле Галуа GF(2⁸), а MixColumns — матричное умножение с коэффициентами, реализуемое через сдвиги и условные XOR. Всё это делается на уровне байтов и слов без арифметики — только логика и перестановки.
Ключевое свойство XOR — обратимость: A ^ B ^ B = A. Это делает его идеальным для шифрования потока (stream cipher): открытый текст XOR ключ → шифротекст; шифротекст XOR ключ → открытый текст.
Сжатие данных
Алгоритмы без потерь (например, DEFLATE, используемый в ZIP и gzip) сочетают словарное сжатие (LZ77) и энтропийное кодирование (Huffman). В LZ77 совпадающие последовательности заменяются на пары (длина, расстояние), которые затем кодируются переменной длины — например, числа до 256 кодируются одним байтом, большие — префиксом и суффиксом. При этом используются битовые потоки: биты из разных полей могут занимать нецелое число байтов, и для записи приходится манипулировать отдельными битами — накапливать в буфере, сдвигать, сбрасывать при переполнении.
Алгоритмы вроде RLE (run-length encoding) тоже полагаются на упаковку: вместо AAAAAABBB хранится (A, 6), (B, 3). Если символ и счётчик упакованы в одно слово (например, 8 бит символа + 24 бита счётчика), доступ осуществляется через & и >>.