Битовое поле

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Битовое поле (англ. bit field) — в программировании некоторое количество бит, расположенных последовательно в памяти, значение которых процессор не способен прочитать из-за особенностей аппаратной реализации. Обычно, процессор способен прочитать значение размером в 1, 2, 4, 8 и др. байт по адресу, кратному числу 8 (1 байт == 8 бит). То есть, процессор не способен прочитать произвольное число бит, имеющих адрес, не кратный 8.

Например, на машинах с 32-х битовым словом все поля IP-пакета (кроме IP-адресов отправителя и получателя) будут битовыми полями, так как их размер не равен 32-х битам и адреса не кратны 8.

Если разрядность битового поля не кратна размеру слова и/или битовое поле не выровнено по границе слова, для получения значения битового поля требуются дополнительные команды процессора:

  • and - операция «битовое И»; используется для выбора бит битового поля по маске;
  • shr - логический сдвиг вправо; используется для сдвига бит битового поля в младшие разряды слова.

Недостаток: дополнительные команды замедляют выполнение кода. Достоинство: при использовании битовых полей достигается максимально плотная упаковка информации.

Битовые поля применяются для максимально полной упаковки информации, если не важна скорость доступа к этой информации. Также использование битовых полей оправдано, если процессор поддерживает специализированные инструкции для работы с битовыми полями, а компилятор использует эти инструкции при генерировании машинного кода.

Компиляторы, как правило, позволяют выполнять с битовыми полями только следующие операции:

  • извлечение значения битового поля;
  • запись значения в битовое поле.

Само битовое поле воспринимается как число без знака. Порядок расположения битовых полей в структуре данных зависит от архитектуры процессора и реализации компилятора: одни компиляторы размещают битовые поля, начиная с младших битов, а другие — начиная со старших.

Операции над многобитовыми полями[править | править вики-текст]

Пусть в одном байте находятся четыре битовых поля:

  • битовые поля a и b, занимающие по одному биту;
  • битовое поле c, занимающее 2 бита;
  • битовое поле d, занимающее 4 бита.
Номер бита 7[* 1] 6 5 4 3 2 1 0[* 2]
Битовое поле d c b a
  1. 7-й бит — старший бит.
  2. 0-й бит — младший бит.

Значение восьмибитового числа x, составленного из битовых полей a, b, c и d, можно вычислить по формуле:  x = a \cdot 2^0 + b \cdot 2^1 + c \cdot 2^2 + d \cdot 2^4 (1).

Если a=1, b=0, c=2=102 и d=5=01012, число x будет равно x = \underbrace{0101}_{d}\underbrace{10}_{c}\underbrace{0}_{b}\underbrace{1}_{a} = 1 \cdot 2^0 + 0 \cdot 2^1 + 2 \cdot 2^2 + 5 \cdot 2^4 = 89.

Сборка одного числа из битовых полей[править | править вики-текст]

Если процессор оперирует двоичными числами формула (1) может быть оптимизирована. После замены операций «возведение в степень» на «логический сдвиг», «умножения» на «битовое ИЛИ» формула (1) примет вид:

x = ( d << 4 ) | ( c << 2 ) | ( b << 1 ) | a

Логический сдвиг двоичного числа эквивалентен умножению/делению на число, кратное степени двойки: 21=2, 22=4, 23=8 и т. д.

Извлечение битового поля[править | править вики-текст]

Получить значение v некоторого битового поля числа x можно двумя способами:

  • v = ( x & mask_1 ) >> offset;
  • v = ( x >> offset ) & mask_2.

При первом способе сначала выполняется операция «битовое И», затем — логический сдвиг вправо. При втором способе операции выполняются в обратном порядке. Константа mask_2 может быть получена из константы mask_1:
mask_2 = mask_1 >> offset.
offset — номер первого младшего бита битового поля v, показатель степени в формуле (1).

Для получения значения битового поля из числа x первым способом выполняют три операции:

  1. вычисляют «битовую маску» mask_1 — число, у которого в соответствующих битовому полю разрядах установлены единицы, а в остальных разрядах — нули;
Номер бита 7 6 5 4 3 2 1 0
Маска для a 0 0 0 0 0 0 0 1
Маска для b 0 0 0 0 0 0 1 0
Маска для c 0 0 0 0 1 1 0 0
Маска для d 1 1 1 1 0 0 0 0
  1. умножают «битовую маску» на число с помощью операции «битовое И»;
  2. выполняют логический сдвиг вправо на offset бит.
Битовое поле offset
a 0
b 1
c 2
d 4

Пример получения значения из битового поля c:

c = ( x & 00001100b ) >> 2

При втором способе:

  1. выполняют логический сдвиг вправо;
  2. вычисляют «битовую маску» mask_2 — число, у которого в первых n младших разрядах установлены единицы, а остальных разрядах — нули; n — число разрядов битового поля;
Номер бита 7 6 5 4 3 2 1 0
Маска для a 0 0 0 0 0 0 0 1
Маска для b 0 0 0 0 0 0 0 1
Маска для c 0 0 0 0 0 0 1 1
Маска для d 0 0 0 0 1 1 1 1
  1. умножают «битовую маску» на число с помощью операции «битовое И».

Пример получения значения из битового поля c:

c = ( x >> 2 ) & 00000011b

Для младшего битового поля (поля a в данном примере) логический сдвиг на ноль разрядов не выполняется. Пример:
a = ( x & 00000001b ) >> 0
a = ( x >> 0 ) & 00000001b )

a = x & 00000001b

При втором способе для старшего поля (поля d в данном примере) логическое умножение не выполняется, так как операция логического сдвига вправо добавляет в число нулевые биты. Пример:
d = ( x >> 4 ) & 00001111b )

d = x >> 4

Замена битового поля[править | править вики-текст]

Для замены битового поля выполняют три операции:

  1. вычисляют маску - число, у которого в битах, соответствующих битовому полю, установлены нули;
  2. операцией «битовое И» умножают число x на маску; операция выполняет установку нулей в биты, соответствующие маске;
  3. операцией «битовое включающее ИЛИ» складывают полученное произведение и число x, сдвинутое на количество битов, соответствующее смещению битового поля от начала слова.

Пример замены значения для битового поля d:

xnew = ( x & 00001111b ) | ( d << 4 )

Операции над однобитовыми полями[править | править вики-текст]

Для работы с битовыми полями шириной в один бит существуют более простые методы.

Битовые поля a и b занимают по одному биту.

Проверка отдельного бита[править | править вики-текст]

Для получения значения отдельного бита выполняют логическое умножение (операцию «битовое И») числа x на маску, у которой установлен один бит, соответствующий биту однобитового поля. Если результат равен 0, бит равен 0.

Пример получения значения однобитового поля b:

b = ( ( x & 00000010b ) != 0 )

Для проверки равенства единице одного или нескольких бит из группы берут маску, у которой в позициях проверяемых бит установлены единицы:

a_or_b = ( ( x & 00000011b ) != 0 )

Для проверки равенства единице всех бит из группы используют «побитовое И» и операцию «==»:

a_and_b = ( ( x & 00000011b ) == 00000011b )

Установка битов[править | править вики-текст]

Для установки битов выполняют логическое сложение (операцию «битовое ИЛИ») числа x с маской, у которой в позициях, соответствующих битовому полю, установлены единицы.

Пример установки бита однобитового поля a:

x1 = x | 00000001b

Для установки нескольких битов числа x, например, битов однобитовых полей a и b, используют маску, у которой в битах, соответствующих битам битовых полей, установлены единицы:

x2 = x | 00000011b

Снятие битов[править | править вики-текст]

Для установки в один или несколько битов нулей число x операцией «битовое И» умножают на маску, у которой в позициях, соответствующих битовому полю, установлены нулевые биты.

Пример установки нулей в биты битового поля b:

x3 = x & 11111101b

Переключение битов[править | править вики-текст]

Для изменения значения битов на противоположное (с 0 на 1 и с 1 на 0) число x операцией «битовое исключающее ИЛИ» складывают с маской, у которой в позициях, соответствующих позициям переключаемых битов, установлены единицы.

Пример изменения значений бит битового поля b:

x4 = x ^ 00000010b

Операции над знаковыми полями в дополнительном коде[править | править вики-текст]

В памяти компьютера целые отрицательные числа могут кодироваться одним из следующих способов:

Большинство современных процессоров реализуют третий способ. Рассмотрим двоичное представление нескольких целых отрицательных чисел в дополнительном коде:

-1 = 11111111b
-2 = 11111110b
-3 = 11111101b
-4 = 11111100b
и т. д.

Считаем, что поля c и d имеют именно такой формат. Тогда поле c может хранить числа от −2=102 до 1=012, а поле d — от −8=10002 до 7=01112.

Сборка и замена чисел[править | править вики-текст]

Каждое из слагаемых (кроме старшего), чтобы оно не испортило более старшие разряды, требуется умножать на битовую маску соответствующей длины. В частности:

x = (d << 4) + ((c & 00000011b) << 2) + (b << 1) + a

Извлечение чисел[править | править вики-текст]

Для извлечения чисел требуется сдвинуть поле на нужное количество битов вправо, заодно размножив знаковый бит. Например, для этого можно воспользоваться арифметическим сдвигом. Если x имеет длину 8 битов, то

c = (x << 4 ) >>a 6
d = x >>a 4

Внимание! В языке программирования Java всё наоборот: знаком >> обозначается арифметический сдвиг, знаком >>> — простой.

Если арифметического сдвига нет, то…

c1 = x >> 2
если (c1 & 00000010b ≠ 0)
  то c = c1 | 0x11111100b
  иначе c = c1 & 0x00000011b

Объявления битовых полей[править | править вики-текст]

В языке C/C++[править | править вики-текст]

В объявлении (англ. declaration) битового поля используется символ двоеточия. После двоеточия указывается константное выражение, определяющее количество битов в поле[1]. Пример:

struct rgb
{
   unsigned r : 3;
   unsigned g : 3;
   unsigned b : 3;
};

Примечания[править | править вики-текст]

  1. Рэй Лишнер [[1] С++. Справочник] = C++ In a Nutshell / гл. ред. Е. Строгонова. — СПб.: Питер, 2003. — С. 193. — 907 с. — 3 500 экз. — ISBN 5-94723-928-0, ББК 32.973-018.1я22, УДК 681.3.06(03).