Редактирование: Битовое поле

'''Би́товое поле''' ({{lang-en|bit field}}) в [[программирование|программировании]] — некоторое количество [[бит]], расположенных последовательно в [[Оперативная память|памяти]], значение которых [[процессор]] не способен прочитать из-за особенностей аппаратной реализации.

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

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

* выставляет адрес ячейки на [[Шина адреса|шину адреса]];

* выставляет код команды «чтение» на [[Шина управления|шину управления]];

* читает значение с [[Шина данных|шины данных]].

[[Файл:Computer system bus.svg|thumb|

<li> CPU ({{lang-en|central processing unit}}) — [[центральный процессор]].

<li> Memory — [[оперативная память|оперативное запоминающее устройство (ОЗУ)]].

<li> Input and output — другие [[Устройство ввода-вывода|устройства]] [[Ввод-вывод|ввода-вывода]].

<li> Control bus — [[шина управления]].

<li> Address bus — [[шина адреса]].

<li> Data bus — [[шина данных]].

<li> System bus — {{iw|системная шина||en|System bus}}.

]]

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

Разрядность [[Шина адреса|шины адреса]] определяет минимально адресуемый размер [[Оперативная память|памяти]]. [[Контроллер памяти]] требует, чтобы адрес ячейки был [[Выравнивание данных|выровнен]] по границе [[Машинное слово|машинного слова]].

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

* инструкции <code>and</code> — операции «[[Конъюнкция|битовое И]]» (используется для записи значения 0 в биты [[Машинное слово|слова]], не входящие в битовое поле (или выбора бит по [[битовая маска|маске]]));

* инструкции <code>shr</code> — [[Битовый сдвиг#Логический сдвиг|логического сдвига]] бит вправо (используется для сдвига бит битового поля в младшие разряды [[Машинное слово|машинного слова]]).

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

* размер [[Машинное слово|машинного слова]] равен {{nobr|32 [[бит]]а}};

* в ячейке [[Оперативная память|памяти]], расположенной по [[Выравнивание данных|выровненному]] адресу, записано значение:

: 0011 0100 1010 11'''10 01'''00 0111 0100 1100_{[[Двоичная система счисления|2]]}

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

# <li value="1"> [[Процессор]] прочитает из [[Оперативная память|памяти]] [[машинное слово]], равное исходному значению:

: 0011 0100 1010 11'''10 01'''00 0111 0100 1100_{[[Двоичная система счисления|2]]}

# <li value="2"> С помощью [[Код операции|инструкции]] <code>and</code> в биты, не входящие в битовое поле, будут записаны значения 0. Результат:

: 0000 0000 0000 00'''10 01'''00 000 0000 0000_{[[Двоичная система счисления|2]]}

# <li value="3"> С помощью [[Код операции|инструкции]] <code>shr</code> биты битового поля будут [[Битовый сдвиг#Логический сдвиг|сдвинуты]] слева направо так, чтобы младший бит битового поля стал младшим битом [[Машинное слово|машинного слова]]. Результат:

: 0000 0000 0000 0000 0000 0000 0000 '''1001'''_{[[Двоичная система счисления|2]]}

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

* чтение двух значений (двух [[Машинное слово|машинных слов]]) из двух смежных ячеек [[Оперативная память|памяти]], адреса которых [[Выравнивание данных|выровнены]];

* «выделение» из двух прочитанных [[Машинное слово|машинных слов]] значений нужных бит с помощью дополнительных [[Код операции|инструкций]] <code>and</code>, <code>shr</code> и <code>shl</code> ([[Битовый сдвиг#Логический сдвиг|сдвиг]] влево);

* [[конкатенация]] (склейка) полученных значений с помощью [[Код операции|инструкции]] <code>or</code> — операции «[[Дизъюнкция|битовое ИЛИ]]».

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

* размер [[Машинное слово|машинного слова]] равен {{nobr|32 [[бит]]а}};

* в двух смежных ячейках [[Оперативная память|памяти]], расположенных по [[Выравнивание данных|выровненным]] адресам, записаны два значения:

: 0011 0100 1010 1110 0100 011'''1 0100 1100'''_{[[Двоичная система счисления|2]]}

: '''0011 01'''00 1010 1110 0100 0111 0100 1100_{[[Двоичная система счисления|2]]}

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

# <li value="1"> [[Процессор]] прочитает из [[Оперативная память|памяти]] два [[Машинное слово|машинных слова]], содержащих нужные биты; значения равны исходным:

: 0011 0100 1010 1110 0100 011'''1 0100 1100'''_{[[Двоичная система счисления|2]]}

: '''0011 01'''00 1010 1110 0100 0111 0100 1100_{[[Двоичная система счисления|2]]}

# <li value="2"> С помощью двух [[Код операции|инструкций]] <code>and</code> в биты, не входящие в битовое поле, будут записаны значения 0. Результат:

: 0000 0000 0000 0000 0000 000'''1 0100 1100'''_{[[Двоичная система счисления|2]]}

: '''0011 01'''00 0000 0000 0000 0000 0000 0000_{[[Двоичная система счисления|2]]}

# <li value="3"> С помощью [[Код операции|инструкции]] <code>shr</code> биты второго [[Машинное слово|машинного слова]] будут [[Битовый сдвиг#Логический сдвиг|сдвинуты]] слева направо так, чтобы младший бит битового поля стал младшим битом [[Машинное слово|машинного слова]]. С помощью [[Код операции|инструкции]] <code>shl</code> биты первого [[Машинное слово|машинного слова]] будут [[Битовый сдвиг#Логический сдвиг|сдвинуты]] справа налево так, чтобы освободить младшие разряды для бит второго машинного слова (для следующего шага). Результат:

: 0000 0000 0000 0000 0'''101 0011 00'''00 0000_{[[Двоичная система счисления|2]]}

: 0000 0000 0000 0000 0000 0000 00'''00 1101'''_{[[Двоичная система счисления|2]]}

# <li value="4"> С помощью [[Код операции|инструкции]] <code>or</code> биты двух [[Машинное слово|машинных слов]] будут «наложены» друг на друга. Результат:

: 0000 0000 0000 0000 0'''101 0011 0000 1101'''_{[[Двоичная система счисления|2]]}

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

* [[программист]]ом вручную;

* [[компилятор]]ом (при наличии поддержки такой возможности);

* [[процессор]]ом (при наличии поддержки такой возможности).

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

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

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

* чтение значения из битового поля;

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

Само битовое поле воспринимается компилятором как [[Целое (тип данных)#Беззнаковые целые|число без знака]]. Порядок расположения битовых полей в [[Структура данных|структуре данных]] зависит от [[Аппаратная платформа|аппаратной платформы]] и реализации [[компилятор]]а: одни компиляторы размещают битовые поля, начиная с младших битов, а другие — начиная со старших.

== Применение ==

Битовые поля применяются для максимально полной упаковки [[Данные|информации]], если не важна скорость доступа к этой информации. Например, для увеличения [[Пропускная способность|пропускной способности]] [[Канал передачи данных|канала]] при передаче информации по [[Вычислительная сеть|сети]] или для [[Сжатие данных|уменьшения размера]] информации при хранении. Также использование битовых полей оправдано, если [[процессор]] поддерживает специализированные инструкции для работы с битовыми полями, а [[компилятор]] использует эти инструкции при генерировании [[Машинный код|машинного кода]].

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

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

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

* битовые поля <tt>a</tt> и <tt>b</tt>, занимающие по одному биту;

* битовое поле <tt>c</tt>, занимающее 2 бита;

* битовое поле <tt>d</tt>, занимающее 4 бита.

{| class="wikitable" style="text-align:center"

! Номер бита

| 7<ref group=*>7-й бит — старший бит.</ref> || 6 || 5 || 4 || 3 || 2 || 1 || 0<ref group=*>0-й бит — младший бит.</ref>

|-

! Битовое поле

| colspan="4" | d

| colspan="2" | c

| | b

| | a

|-

| colspan="9" | {{примечания|group=*}}

|}

Значение восьмибитового числа <tt>x</tt>, составленного из битовых полей <tt>a</tt>, <tt>b</tt>, <tt>c</tt> и <tt>d</tt>, можно вычислить по формуле:

<math> x = a \cdot 2^0 + b \cdot 2^1 + c \cdot 2^2 + d \cdot 2^4 </math> {{якорь2|formula_1|текст=(1)}}.

Если <tt>a=1</tt>, <tt>b=0</tt>, <tt>c=2=10_{[[Двоичная система счисления|2]]}</tt> и <tt>d=5=0101_{[[Двоичная система счисления|2]]}</tt>, число <tt>x</tt> будет равно <math>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</math>.

=== Сборка одного числа из битовых полей ===

Если [[процессор]] оперирует [[Двоичная система счисления|двоичными]] числами, [[#formula 1|формула (1)]] может быть [[Оптимизация (информатика)|оптимизирована]]. После замены операций «[[возведение в степень]]» на «[[Битовый сдвиг#Логический сдвиг|логический сдвиг]]», «[[Умножение|умножения]]» на «[[Дизъюнкция|битовое ИЛИ]]» [[#formula 1|формула (1)]] примет вид:

<source lang="c">

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

</source>

[[Битовый сдвиг#Логический сдвиг|Логический сдвиг]] двоичного числа эквивалентен умножению/делению на число, кратное степени двойки: 2¹=2, 2²=4, 2³=8 и т. д.

=== Извлечение битового поля ===

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

* {{cpp|1=v = ( x & mask_1 ) >> offset}};

* {{cpp|1=v = ( x >> offset ) & mask_2}}.

При первом способе сначала выполняется операция «[[Конъюнкция|битовое И]]», затем — [[Битовый сдвиг#Логический сдвиг|логический сдвиг]] вправо. При втором способе операции выполняются в обратном порядке. [[Математическая константа|Константа]] <tt>mask_2</tt> может быть получена из константы <tt>mask_1</tt>:<br>{{cpp|1=mask_2 = mask_1 >> offset}}.<br><tt>offset</tt> — номер первого младшего бита битового поля <tt>v</tt>, показатель степени в [[#formula 1|формуле (1)]].

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

# вычисляют «битовую маску» <tt>mask_1</tt> — число, у которого в соответствующих битовому полю разрядах установлены единицы, а в остальных разрядах — нули;

{| class="wikitable"

|-

! Номер бита

| 7 || 6 || 5 || 4 || 3 || 2 || 1 || 0

|-

! Маска для <tt>a</tt>

| 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1

|-

! Маска для <tt>b</tt>

| 0 || 0 || 0 || 0 || 0 || 0 || 1 || 0

|-

! Маска для <tt>c</tt>

| 0 || 0 || 0 || 0 || 1 || 1 || 0 || 0

|-

! Маска для <tt>d</tt>

| 1 || 1 || 1 || 1 || 0 || 0 || 0 || 0

|-

|}

# <li value="2"> умножают «битовую маску» на число с помощью операции «[[Конъюнкция|битовое И]]»;

# выполняют [[Битовый сдвиг#Логический сдвиг|логический сдвиг]] вправо на <tt>offset</tt> бит.

{| class="wikitable"

|-

! Битовое поле

! <tt>offset</tt>

|-

| a || 0

|-

| b || 1

|-

| c || 2

|-

| d || 4

|-

|}

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

<source lang="c">

c = ( x & 00001100b ) >> 2

</source>

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

# выполняют [[Битовый сдвиг#Логический сдвиг|логический сдвиг]] вправо;

# вычисляют «битовую маску» <tt>mask_2</tt> — число, у которого в первых <tt>n</tt> младших разрядах установлены единицы, а остальных разрядах — нули; <tt>n</tt> — число разрядов битового поля;

{| class="wikitable"

|-

! Номер бита

| 7 || 6 || 5 || 4 || 3 || 2 || 1 || 0

|-

! Маска для <tt>a</tt>

| 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1

|-

! Маска для <tt>b</tt>

| 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1

|-

! Маска для <tt>c</tt>

| 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1

|-

! Маска для <tt>d</tt>

| 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1

|-

|}

# <li value="3"> умножают «битовую маску» на число с помощью операции «[[Конъюнкция|битовое И]]».

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

<source lang="c">

c = ( x >> 2 ) & 00000011b

</source>

Для '''младшего''' битового поля (поля <tt>a</tt> в данном примере) логический сдвиг на ноль разрядов не выполняется. Пример:<br>

<s>{{cpp|1=a = ( x & 00000001b ) >> 0}}</s><br>

<s>{{cpp|1=a = ( x >> 0 ) & 00000001b )}}</s><br>

<source lang="c">

a = x & 00000001b

</source>

При втором способе для '''старшего''' поля (поля <tt>d</tt> в данном примере) логическое умножение не выполняется, так как операция логического сдвига вправо добавляет в число нулевые биты. Пример:<br>

<s>{{cpp|1=d = ( x >> 4 ) & 00001111b )}}</s><br>

<source lang="c">

d = x >> 4

</source>

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

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

# вычисляют маску — число, у которого в битах, соответствующих битовому полю, установлены нули;

# операцией «[[Конъюнкция|битовое И]]» умножают число <tt>x</tt> на маску; операция выполняет установку нулей в биты, соответствующие маске;

# операцией «[[Дизъюнкция|битовое включающее ИЛИ]]» складывают полученное произведение и число <tt>x</tt>, сдвинутое на количество битов, соответствующее смещению битового поля от начала слова.

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

<source lang="c">

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

</source>

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

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

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

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

<source lang="c">

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

</source>

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

<source lang="c">

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

</source>

Для проверки равенства единице всех бит из группы используют «[[Конъюнкция|побитовое И]]» и операцию «<tt>==</tt>»:

<source lang="c">

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

</source>

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

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

<source lang="c">

x1 = x | 00000001b

</source>

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

<source lang="c">

x2 = x | 00000011b

</source>

Для установки в один или несколько битов нулей число <tt>x</tt> операцией «[[Конъюнкция|битовое И]]» умножают на маску, у которой в позициях, соответствующих битовому полю, установлены нулевые биты.

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

<source lang="c">

x3 = x & 11111101b

</source>

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

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

<source lang="c">

x4 = x ^ 00000010b

</source>

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

* [[Прямой код (представление числа)|прямой код]];

* [[Обратный код (представление числа)|обратный код]];

* [[Дополнительный код (представление числа)|дополнительный код]].

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

Рассмотрим двоичное представление нескольких целых чисел в [[Дополнительный код (представление числа)|дополнительном коде]]:

4 = 00000100₂

3 = 00000011₂

2 = 00000010₂

1 = 00000001₂

0 = 00000000₂

-1 = 11111111₂

-2 = 11111110₂

-3 = 11111101₂

-4 = 11111100₂

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

'''Внимание!''' В языке программирования [[Java]] всё наоборот: знаком {{cpp|1=>>}} обозначается [[Битовый сдвиг#Арифметический сдвиг|арифметический сдвиг]], а знаком {{cpp|1=>>>}} — [[Битовый сдвиг#Логический сдвиг|логический]].

В [[Язык программирования|языках]] [[Си (язык программирования)|C]] и [[C++]] при объявлении ({{lang-en|declaration}}) битового поля используется [[Двоеточие|символ двоеточия {{Symbol|:}}]]. После двоеточия указывается константное [[Выражение (информатика)|выражение]], определяющее количество [[бит]]ов в битовом поле<ref>{{книга

| автор = Рэй Лишнер

| заглавие = С++. Справочник

| оригинал = C++ In a Nutshell

| место = [[Санкт-Петербург|СПб.]]

| издательство = [[Питер (издательство)|Питер]]

| год = [[2003 год|2003]]

| страницы = 193

| страниц = 907

| isbn = 5-94723-928-0, ББК 32.973-018.1я22, УДК 681.3.06(03)

| ответственный = гл. ред. Е. Строгонова

| тираж = {{formatnum:3500}}

}}</ref>. Пример:

<source lang="c">

struct rgb

{

unsigned r : 3;

unsigned g : 3;

unsigned b : 3;

};

</source>

== См. также ==

* [[Битовые операции]]

* [[Битовая карта]]

* [[Битовая маска]]