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 в степени номера бита.
- 165 -
Внутреннее отличие имеют представления целых типов со знаком: 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 будут рассмотрены чуть позже.
- 166 -
| { ФУНКЦИЯ ПЕРЕВОДА ЦЕЛОГО ЧИСЛА В ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ}
| { 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
or
Логическое сложение
A1 or A2
xor
Исключающее 'ИЛИ'
A1 xor A2
4 (низший)
Not — поразрядное отрицание — «переворачивает» значение каждого бита на противоположное. Так, если A в двоичном виде представляется как 01101100, то not A станет 10010011:
not [1] = 0
not [0] = 1
Квадратные скобки вокруг аргументов обозначают действие над одним битом.
- 167 -
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 дает число 25 = 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). Исключить — значит, задать нулем. Первым делом определяется
- 168 -
число, в котором все биты равны 1, кроме бита номер 3. Для типа Byte оно равно (255 – 23) = 247, где 255 — максимальное значение, вписываемое в байт. Если теперь это число логически умножить на A, то единицы в 247 никак не повлияют на состояние битов в переменной A, а ноль в третьем бите заместит любое значение в A на том же месте. Таким образом, можно записать
A := A and (255 – 8);
чтобы получить значение A с отключенным 3-м битом.
Все это верно и для нескольких битов сразу: если надо исключить биты 3 и 7, то просто запишем
A := A and (255 – 8 – 128);
где 8 = 23 и 128 = 27.
Or — логическое сложение; оно же операция 'ИЛИ', определяется следующими действиями над битами:
[1] or [0] = [0] or [1] = [1]
[0] or [0] = [0]
[1] or [1] = [1]
Квадратные скобки обозначают один бит. Эта операция может с успехом применяться при включении (установки в 1) отдельных битов двоичного представления целых чисел. Так, если надо, чтобы бит 4 значения A стал равным единице, а остальные не изменились, то следует записать
A := A or 16;
где 16 = 24 . При этом не имеет значения, что было в 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 можно с успехом применять при смене значения бита (или нескольких битов) на противоположные. Пусть необходимо
- 169 -
переключить состояние бита 5 числа А. Это будет сделано операцией A xor 32 , где 32 = 25.
Исключающее 'ИЛИ' обладает одной особенностью: примененное дважды к одной и той же переменной, оно восстановит ее исходное значение, т.е. всегда выполняется равенство:
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 освобождаемое слева место заполняется единицами.
- 170 -
Конечно, операции сдвига достаточно специфичны и реально нужны только при обработке битовых последовательностей. Пример их использования был дан на рис. 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 байт — экономия шестикратная.
- 171 -
| { Процедура кодирования 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