Битовое поле

Би́товое поле (англ. bit field) в программировании — некоторое количество бит, расположенных последовательно в памяти, значение которых процессор не способен прочитать из-за особенностей аппаратной реализации.

Об аппаратных реализациях

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

выставляет адрес ячейки на шину адреса;
выставляет код команды «чтение» на шину управления;
читает значение с шины данных.

CPU (англ. central processing unit) — центральный процессор.

Memory — оперативное запоминающее устройство (ОЗУ).

Input and output — другие устройства ввода-вывода.

Control bus — шина управления.

Address bus — шина адреса.

Data bus — шина данных.

System bus — системная шина.

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

Разрядность шины адреса определяет минимально адресуемый размер памяти. Контроллер памяти требует, чтобы адрес ячейки был выровнен по границе машинного слова.

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

инструкции and — операции «битовое И» (используется для записи значения 0 в биты слова, не входящие в битовое поле (или выбора бит по маске));
инструкции shr — логического сдвига бит вправо (используется для сдвига бит битового поля в младшие разряды машинного слова).

Пример. Пусть:

размер машинного слова равен 32 бита;
в ячейке памяти, расположенной по выровненному адресу, записано значение:

0011 0100 1010 1110 0100 0111 0100 1100₂

требуется прочитать биты, выделенные жирным шрифтом.

Процессор прочитает из памяти машинное слово, равное исходному значению:

0011 0100 1010 1110 0100 0111 0100 1100₂

С помощью инструкции and в биты, не входящие в битовое поле, будут записаны значения 0. Результат:

0000 0000 0000 0010 0100 0000 0000 0000₂

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

0000 0000 0000 0000 0000 0000 0000 1001₂

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

чтение двух значений (двух машинных слов) из двух смежных ячеек памяти, адреса которых выровнены;
«выделение» из двух прочитанных машинных слов значений нужных бит с помощью дополнительных инструкций and, shr и shl (сдвиг влево);
конкатенация (склейка) полученных значений с помощью инструкции or — операции «битовое ИЛИ».

Пример. Пусть:

размер машинного слова равен 32 бита;
в двух смежных ячейках памяти, расположенных по выровненным адресам, записаны два значения:

0011 0100 1010 1110 0100 0111 0100 1100₂

0011 0100 1010 1110 0100 0111 0100 1100₂

требуется прочитать биты, выделенные жирным шрифтом и расположенные по не выровненному адресу.

Процессор прочитает из памяти два машинных слова, содержащих нужные биты; значения равны исходным:

0011 0100 1010 1110 0100 0111 0100 1100₂

0011 0100 1010 1110 0100 0111 0100 1100₂

С помощью двух инструкций and в биты, не входящие в битовое поле, будут записаны значения 0. Результат:

0000 0000 0000 0000 0000 0001 0100 1100₂

0011 0100 0000 0000 0000 0000 0000 0000₂

С помощью инструкции shr биты второго машинного слова будут сдвинуты слева направо так, чтобы младший бит битового поля стал младшим битом машинного слова. С помощью инструкции shl биты первого машинного слова будут сдвинуты справа налево так, чтобы освободить младшие разряды для бит второго машинного слова (для следующего шага). Результат:

0000 0000 0000 0000 0101 0011 0000 0000₂

0000 0000 0000 0000 0000 0000 0000 1101₂

С помощью инструкции or биты двух машинных слов будут «наложены» друг на друга. Результат:

0000 0000 0000 0000 0101 0011 0000 1101₂

Описанные дополнительные действия могут выполняться:

программистом вручную;
компилятором (при наличии поддержки такой возможности);
процессором (при наличии поддержки такой возможности).

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

О компиляторах

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

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

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

Применение

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

Например, на машинах с 32-битовым словом все поля IPv4-пакета (кроме полей «адрес отправителя» и «адрес получателя») будут битовыми полями, так как их размер не равен 32 битам и их адреса не кратны 4 байтам. Если, в дополнение к этому, процессор поддерживает прямое чтение и запись 8- и 16-битовых чисел, битовыми полями будут только поля «версия», «размер заголовка», «DSCP», «ECN», флаги и «смещение фрагмента».

Операции над многобитовыми полями

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

битовые поля a и b, занимающие по одному биту;
битовое поле c, занимающее 2 бита;
битовое поле d, занимающее 4 бита.

Номер бита	7[* 1]	6	5	4	3	2	1	0[* 2]
Битовое поле	d				c		b	a
7-й бит — старший бит. 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=10₂ и d=5=0101₂, число 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

Логический сдвиг двоичного числа эквивалентен умножению/делению на число, кратное степени двойки: 2¹=2, 2²=4, 2³=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 первым способом выполняют три операции:

вычисляют «битовую маску» 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

умножают «битовую маску» на число с помощью операции «битовое И»;
выполняют логический сдвиг вправо на offset бит.

Битовое поле	`offset`
a	0
b	1
c	2
d	4

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

c = ( x & 00001100b ) >> 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

умножают «битовую маску» на число с помощью операции «битовое И».

Пример получения значения из битового поля 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

Замена битового поля

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

вычисляют маску — число, у которого в битах, соответствующих битовому полю, установлены нули;
операцией «битовое И» умножают число x на маску; операция выполняет установку нулей в биты, соответствующие маске;
операцией «битовое включающее ИЛИ» складывают полученное произведение и число 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

Операции над знаковыми полями в дополнительном коде

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

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

 4 = 00000100₂
 3 = 00000011₂
 2 = 00000010₂
 1 = 00000001₂
 0 = 00000000₂
-1 = 11111111₂
-2 = 11111110₂
-3 = 11111101₂
-4 = 11111100₂
и т. д.

Пусть поля c и d имеют формат «дополнительный код». Тогда поле c может хранить числа от −2=10₂ до 1=01₂, а поле d — от −8=1000₂ до 7=0111₂.

Сборка и замена чисел

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

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;
};

См. также

Примечания

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 7-й бит — старший бит.

[2] 0-й бит — младший бит.

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