9.2. Битовая арифметика

Кроме стандартных для всех языков математических действий над вещественными и целыми числами, Турбо Паскаль вводит дополнительные операции над целыми числами, в том числе и так называемую битовую, или поразрядную, арифметику.

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

Ограничение на битовые операции одно: они должны применяться только над целыми типами — Byte, ShortInt, Word, Integer, LongInt и совместимыми с ними. Именно эти типы кодируют значения в правильные двоичные числа, как в школьном учебнике по информатике. (То, что в памяти некоторые целые типы хранят свои байты значений в обратном порядке, никак не влияет на поразрядные действия и логику работы с ними. Все особенности учитываются самими поразрядными операциями, и мы можем о них даже не вспоминать.) Например, значения 4 и 250 типа Byte представляются как двоичные наборы 00000100 и 11111010, число 65535 типа Word — это уже 16 бит: 11111111 11111111 и т.д.

Общая формула для значений типов Byte и Word имеет вид

Byte : Значение = B7*27 + B6*2б + B5*25 +...+ B1*2* + B0;

Word : Значение = B15*215 + B14*214+...+B7*27 +...+ B0.

Множители B0, B1 и т.п. — это значения соответствующих битов, равные либо 0, либо 1, а числовые множители — это 2 в степени номера бита. {164}

Внутреннее отличие имеют представления целых типов со знаком: ShortInt, Integer и LongInt. По размеру тип ShortInt равен типу Byte, a Integer — типу Word. Но они могут хранить отрицательные целые числа, правда, меньшие по абсолютному значению чем 255 и 65535:

ShortInt : -128 ..127 ( 8 бит ),

Integer : -32768 .. 32767 ( 16 бит ),

LongInt : -2147483648 .. 2147483647 ( 32 бит ).

Самый левый бит в представлении отрицательного числа всегда равен 1, если значение отрицательное, и 0 в противном случае. Формула перевода битов в значение для типов ShortInt, Integer, LongInt такова:

Shortlnt : Знач= -B7*27 + B6*26 + B5*25 +...+ B1*21 + B0;

Integer : Знач=-B15*215 + B14*214+...+B7*27 +...+ B0;

LongInt : Знач=-B31*231 + B30*230+...+B15*215 +...+ B0;

Примеры кодировки отрицательных чисел для типа ShortInt (бит знака числа отделен здесь пробелом) :

-1 :1 1111111 ( -1*128 + 127 )

-2 : 1 1111110 ( -1*128 + 126 )

-3 : 1 1111101 ( -1*128 + 125 )

-125 : 1 0000011 ( -1*128 + 3 )

-128 : 1 0000000 ( -1*128 + 0 )

Если в кодировании положительных значений абсолютное значение числа тем больше, чем больше единиц в его записи, то для отрицательных значений нули и единицы как бы поменяются местами — и абсолютное значение числа тем больше, чем больше будет в записи нулей. Поэтому, например, двоичное представление того же числа -128 в формате Integer (это уже 16 бит) будет 11111111 10000000.

Вещественные типы кодируются каждый раз по-разному, но всегда достаточно сложно: одна группа битов составляет мантиссу числа, вторая — порядок, да еще знак... Битовые операции к вещественным числам (типам) не применяются.

Посмотреть двоичную форму представления целых чисел можно с помощью функции (рис. 9.1). Операции shl и shr из примера на рис. 9.1 будут рассмотрены чуть позже. {165}

{ФУНКЦИЯ ПЕРЕВОДА ЦЕЛОГО ЧИСЛА В ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ} { X - целое число (можно передавать и другие типы ) } { NumOfBits - число позиций в двоичном представлении } FUNCTION Binary( X:LongInt; NumOfBits : Byte ) : String; VAR bit, i : Byte; { вспомогательные переменные } s : String[32]; BEGIN s: = ' '; { обязательная чистка строки } for i:=0 to 31 do begin { цикл перевода } bit := ( X shl i ) shr ( 31 ); { выделение бита } s := s + Chr( Ord( '0' ) + bit ) { запись в строку } end; {for} { конец цикла } Delete( s, 1, 32-NumOfBits ); { отсечение лишних битов} Binary :- s { возвращаемая строка } END; VAR i : Integer; {=== ПРИМЕР ВЫЗОВА === } BEGIN for i:=-5 to 5 do WriteLn(i:7, '--> ', Binary( i, 8*SizeOf(i))); Readln { пауза до нажатия клавиши ввода } END.

Рис. 9.1

Итак, какие же действия предоставляет поразрядная арифметика? Первая группа — это логические операции над битами (табл. 9.2).

Таблица 9.2

Операции	Название	Форма записи	Приоритет
not	Поразрядное отрицание	not A	1 (высший)
and	Логическое умножение	A1 and A2	2
or	Логическое сложение	A1 or A2	3
xor	Исключающее 'ИЛИ'	A1 xor A2	4 (низший)

Not — поразрядное отрицание — «переворачивает» значение каждого бита на противоположное. Так, если A в двоичном виде представляется как 01101100, то not A станет 10010011:

not [1] = 0

not [0] = 1

Квадратные скобки вокруг аргументов обозначают действие над одним битом. {166}

And — так называемое логическое умножение или поразрядная операция 'И':

[0] and [1] = [1] and [0] = [0]

[0] and [0] = [0]

[1] and [1] = [1]

Здесь аргументы специально взяты в скобки — их надо рассматривать как отдельные единичные биты; реальные же примеры не столь очевидны:

(6 and 4) = 4

(6 and 1) = 0

и т.п. Все станет ясно, если 6 и 4 представить как двоичные числа:

0000110 (6) 0000110 (6)

and 0000100 (4) и and 0000001 (1)

______________ ______________

0000100 (4) 0000000 (0)

Впрочем, вовсе не обязательно записывать числа в виде нулей и единиц. Операция and в 99% случаев нужна для двух целей: проверить наличие битов или убрать ( т.е. обнулить) некоторые из них.

Такая проверка нужна, когда число является набором флагов. Например, большое число системных ячеек памяти ПЭВМ содержит сведения о конфигурации машины или ее состоянии. При этом один байт может трактоваться так: бит 6 равен 1 — значит включен режим CapsLock, бит 4 равен 0 — следовательно какой-либо другой режим Lock выключен и т.д. Пусть A содержит этот самый байт с восемью флагами, и надо проверить состояние бита номер 5 (нумерация идет справа налево, от 0 до 7). Единица в бите 5 дает число 2⁵ = 32. Это второй аргумент. Если в A в пятом бите есть единица, то должно выполниться условие

( A and 32 ) = 32

Осталось оформить все это в оператор IF. Можно проверить наличие сразу нескольких «включенных» битов, например, 5-го, 2-го и 0-го. Число с единицами в этих позициях и нулями в остальных равно 2+2 + 1 = 32+4+1 = 37. Если A среди прочих имеет единицы в битах 5, 2 и 0, то в этом случае будет истинным выражение

( A and 37 ) = 37

Исключение или выключение битов достигается следующим образом. Пусть надо исключить бит 3 из переменной A типа Byte (здесь важно знать тип, в который «умещается» текущее значение A). Исключить — значит, задать нулем. Первым делом определяется {167} число, в котором все биты равны 1, кроме бита номер 3. Для типа Byte оно равно (255 – 2³) = 247, где 255 — максимальное значение, вписываемое в байт. Если теперь это число логически умножить на A, то единицы в 247 никак не повлияют на состояние битов в переменной A, а ноль в третьем бите заместит любое значение в A на том же месте. Таким образом, можно записать

A := A and (255 – 8);

чтобы получить значение A с отключенным 3-м битом.

Все это верно и для нескольких битов сразу: если надо исключить биты 3 и 7, то просто запишем

A := A and (255 – 8 – 128);

где 8 = 2³ и 128 = 2⁷.

Or — логическое сложение; оно же операция 'ИЛИ', определяется следующими действиями над битами:

[1] or [0] = [0] or [1] = [1]

[0] or [0] = [0]

[1] or [1] = [1]

Квадратные скобки обозначают один бит. Эта операция может с успехом применяться при включении (установки в 1) отдельных битов двоичного представления целых чисел. Так, если надо, чтобы бит 4 значения A стал равным единице, а остальные не изменились, то следует записать

A := A or 16;

где 16 = 2⁴ . При этом не имеет значения, что было в 4-м бите значения A. В любом случае там появится единица.

Аналогичным образом можно включать сразу несколько битов, например, 4-й, 1-й и 0-й:

A := A or (16 + 2 + 1);

Кроме перечисленных, введена еще одна операция xor — исключающее 'ИЛИ' (математическое название — «сложение по модулю 2»). Эта операция возвращает 0, если оба ее аргумента равны, и 1 в противном случае:

[1] xor [1] = [0]

[0] xor [0] = [0]

[1] xor [0] = [0] xor [1] = [1]

Операцию xor можно с успехом применять при смене значения бита (или нескольких битов) на противоположные. Пусть необходимо {168} переключить состояние бита 5 числа А. Это будет сделано операцией A xor 32 , где 32 = 2⁵.

Исключающее 'ИЛИ' обладает одной особенностью: примененное дважды к одной и той же переменной, оно восстановит ее исходное значение, т.е. всегда выполняется равенство:

A = ( A xor B ) xor B

Следующая группа поразрядных операций — циклические сдвиги (табл. 9.3).

Таблица 9.3

Операция	Название	Форма записи
shl	Циклический сдвиг влево на N позиций	A shl N
shr	Циклический сдвиг вправо на N позиций	A shr N

Приоритет операций shl и shr одинаков и среди всех остальных невысок (см. табл. 9.1). Поэтому, как правило, выражения сдвига должны быть заключены в скобки.

Суть операций shr и shl одинакова: они сдвигают двоичную последовательность значения A на N ячеек (битов) вправо или влево. При этом те биты, которые «уходят» за край разрядности (8, 16 и 32 в зависимости от значения A), теряются, а освободившееся место с другой стороны заполняется нулями (всегда при сдвиге влево и иногда вправо) или единицами (только при сдвиге вправо отрицательных значений типа ShortInt, Integer и LongInt). Например, число с двоичным представлением 11011011 будет трансформироваться при сдвигах влево следующим образом:

( 11011011 shl 0 ) = 11011011

( 11011011 shl 1 ) = 10110110

( 11011011 shl 2 ) = 01101100

( 11011011 shl 3 ) = 11011000

( 11011011 shl 4 ) = 10110000

...

( 11011011 shl 7 ) = 10000000 ( 11011011 shl 8 } = 00000000

Если бы число имело значение типа Word от 256 до 65535, то эффект был бы тем же, только биты «переезжали» бы в поле длиной 16 бит. Для LongInt поле составит 32 бита. При применении операций shl и shr к отрицательным величинам типов ShortInt, Integer, LongInt освобождаемое слева место заполняется единицами.{169}

Конечно, операции сдвига достаточно специфичны и реально нужны только при обработке битовых последовательностей. Пример их использования был дан на рис. 9.1. Там каждый бит последовательно сдвигается к самому левому краю, стирая тем самым все впереди стоящие биты, а затем возвращается в самую правую позицию, стирая тем самым все стоящие правее его биты. В итоге получаем число, равное 0 или 1, в зависимости от содержимого очередного бита.

Операция shl может заменять умножение целых чисел на степени двойки:

J shl 1 = J*2

J shl 2 = J*4

J shl 3 = J*8

Сжатие и кодирование информации. Обычная емкость памяти ПЭВМ (640K) — не так уж велика, как может показаться. Часто вопросы эффективного хранения данных становятся важными для работоспособности программ. Пусть, к примеру, нужно хранить в памяти выборку целых чисел со значениями от 0 до 15, состоящую из 80000 чисел. Так как минимальный тип для каждого числа применительно к Турбо Паскалю — Byte, то всего понадобится 80000 байт. Массив на 80000 байт не пропустит компилятор (максимум, что он сможет «переварить», — это 64K). Кроме того, для представления значения от 0 до 15 достаточно четырех битов, а отводится восемь.

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

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

К сожалению, подобный подход нельзя применить к вещественным значениям. Единственное, что можно посоветовать — это посмотреть, нужны ли именно вещественные формы хранения данных. Так, если хранится массив вещественных (Real — 6 байт на элемент) значений размеров чего-либо в метрах с точностью до сантиметра, и самое длинное измерение не превосходит 2,55 м, то гораздо эффективнее будет хранить их как массив размеров в сантиметрах. И одно значение будет свободно размещаться в одном байте! Тип Byte занимает 1 байт — экономия шестикратная. {170}

{Процедура кодирования X1 и X2 в один байт (X1, X2<=15) } PROCEDURE Code2to1( X1,X2 : Byte; VAR X1X2 : Byte ); BEGIN X1X2 := X1 + (X2 shl 4 ) END; {Процедура декодирования X1 и X2 из одного байта } PROCEDURE DeCode1to2{ X1X2 : Byte; VAR X1,X2 : Byte ); BEGIN X1 := X1X2 and 15; { X1X2 and $F } X2 := X1X2 shr 4 END; VAR {== ПРИМЕР ВЫЗОВА ==} C, C1, C2 : Byte; BEGIN Code2to1(8,7, C); WriteLn('8 и 7 - кодируются в —> ',C); DeCode1to2(C, C1, C2); WriteLn(C:3, — декодируются в --> ',C1:-3,' и ',C2); ReadLn { пауза до нажатия клавиши ввода } END.

Рис. 9.2