Двоичная математика
01.01.2007
Двоичная математика.
Введение Наряду с обычными логическими операция над логическими типами Boolean, часто приходится выполнять операции и над отдельными битами, обычно используемыми, как флаги. Для эффективной работы необходимо понимание логических операций. Паскаль поддерживает следующие логические операции AND – логическое И; OR - (включающие) логическое ИЛИ; XOR - (исключающие) логическое ИЛИ; NOT - отрицание или инверсия бита; SHL – логический сдвиг влево; SHR – логический сдвиг вправо. Другие логические операции над числами в Паскаль не включены, но доступны через ассемблерные вставки. Каждый бит может иметь только два состояния ЛОЖЬ (FALSE) или ИСТИНА (TRUE) Состояние бита можно описывать и другими словами, часть которых пришла из математики, часть из электроники, часть из логики. Для значения ЛОЖЬ, альтернативные варианты такие – НЕТ, НОЛЬ, ВЫКЛЮЧЕНО, НЕ УСТАНОВЛЕНО, СБРОШЕНО, FALSE, F, 0, - и другие. Для значения ИСТИНА, альтернативные варианты такие – ДА, ЕДИНИЦА, ВКЛЮЧЕНО, УСТАНОВШЕНО, ВЗВЕДЕНО, TRUE, T, 1, + и другие. Рассмотрим эти операции по отдельности AND – логическое И, эта операции выглядит такA | B | Y |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
A | B | Y |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
A | B | Y |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
A | Y |
0 | 1 |
1 | 0 |
Разряды | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
До | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
После | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
Разряды | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
До | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
После | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Разряды | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
До | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
После | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
Разряды | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
До | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
После | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
Основание |
Значение |
Формула |
2 |
4 |
1*2^2 + 0*2^1 +0*2^0 |
8 |
64 |
1*8^2 + 0*8^1 +0*8^0 |
10 |
100 |
1*10^2 + 0*10^1 + 0*2^0 |
16 |
256 |
1*16^2 + 0*16^1 + 0*2^0 |
Основание |
Значение |
Формула |
2 |
X |
Не допустимая комбинация |
8 |
83 |
1*8^2 + 2*8^1 + 3*8^0 |
10 |
123 |
1*10^2 + 2*10^1 + 3*10^0 |
16 |
291 |
1*16^2 + 2*16^1 + 3*16^0 |
1 shl NВ данном примере единица сдвигается влево на нужное количество разрядов, и в результате получаем двоичное значение, равное 2^N, где в установлен один единственный бит, соответствующий разряду числа. Этот прием может использоваться с переменной для расчета позиции во время выполнения или во время компиляции, во втором случае код генерироваться не будет, а компилятор просто рассчитает значение и подставит его в программу, не генерируя дополнительного кода. Это удобно для указания номера бита, не представляя его в виде десятичной или шестнадцатеричной константы. Но чаще бывает удобнее использовать именованные константы, поскольку они более информативны, примеры этого будут приведены в конце статьи. Установка бита Для установки отдельного бита или группы битов используется операция ИЛИ, использование иллюстрируется ниже приведенным кодом в виде отдельной функции и результатом выполнения в виде таблицы.
function SetBit(Src: Integer; bit: Integer): Integer;Здесь происходит следующее: Сначала мы рассчитываем позицию бита – (1 shl Bit), затем устанавливаем полученный бит и возвращаем результат через предопределенную переменную Result. Пример использования:
begin
Result := Src or (1 shl Bit);
end;
DummyValue := SetBit(DummyValue, 2);
Разряды | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
До (1) | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
После | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
До (2) | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
После | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
function ResetBit(Src: Integer; bit: Integer): Integer;Здесь происходит следующее: Сначала мы рассчитываем позицию бита – (1 shl Bit), затем с помощью операции NOT инвертируем полученную маску, устанавливая, не затрагиваемые биты маски в единицу, а затрагиваемый бит в ноль, затем сбрасываем этот бит, а результат возвращаем результат через предопределенную переменную Result. Пример использования:
begin
Result := Src and not (1 shl Bit);
end;
DummyValue := ResetBit(DummyValue, 2);
Разряды | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
До (1) | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
После | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
До (2) | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
После | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
function InvertBit(Src: Integer; bit: Integer): Integer;Здесь происходит следующее: Сначала мы рассчитываем позицию бита – (1 shl Bit), затем с помощью операции XOR переключаем бит, а результат возвращаем результат через предопределенную переменную Result. Пример использования:
begin
Result := Src xor (1 shl Bit);
end;
DummyValue := InvertBit(DummyValue, 2);
Разряды | B7 | B6 | B5 | B4 | B3 | B2 | B1 | B0 |
До (1) | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
После | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
До (2) | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
После | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
if Value and (1 shl N) <> 0 then ... установленчаще всего это используется в другой форме, вместо расчета позиции используется именованная константа, например
if Value and (1 shl N) = 0 then ... не установлен
constЭто более наглядно, особенно если константе дано более значимое имя, чем B2, например, для проверки готовности передатчика мы можем определить константу с именем TxReady, тогда это будет выглядеть очень красиво.
B2 = 4 // B2 (1 shl 2)
Begin
if Value and B2 = B2 then ... установлен
if Value and B2 = 0 then ... не установлен
end;
const
TxReady = 4
Begin
if Value and TxReady then begin
... обработка готовности передатчика
end;
end;
Ну, вот с базисом мы покончили и пора приступить к более полезным и практическим примерам. В качестве примера выберем поиск папок и файлов. Пример был разработан для FAQ конференции fido7.ru.delphi, в дальнейшем был немного модернизирован по замечаниям от Юрия Зотова.
procedure ScanDir(StartDir: string; Mask:string; List:TStrings);Рассмотрим ключевые моменты, относящиеся к данной статье.
var
SearchRec : TSearchRec;
begin
if Mask = '' then Mask := '*.*';
if StartDir[Length(StartDir)] <> '\' then StartDir := StartDir + '\';
if FindFirst(StartDir + Mask, faAnyFile, SearchRec) = 0 then
begin
repeat
Application.ProcessMessages;
if (SearchRec.Attr and faDirectory) <> faDirectory
then
List.Add(StartDir + SearchRec.Name)
else if (SearchRec.Name <> '..') and (SearchRec.Name <> '.')
then
begin
List.Add(StartDir + SearchRec.Name + '\');
ScanDir(StartDir + SearchRec.Name + '\', Mask, List);
end;
until FindNext(SearchRec) <> 0;
FindClose(SearchRec);
end;
end;
if FindFirst(StartDir + Mask, faAnyFile, SearchRec) = 0 thenЗдесь является битовой маской, описанной в модуле SysUtils, ее значение равно $3F, она предназначена для включения в поиск специальных файлов и одновременно для изоляции лишних бит из структуры TsearchRec, отдельные биты данной маски описаны как именованные константы.
Нименование | Значение | Описание | |
FaReadOnly | $00000001 | Read-only files | Файлы с защитой от записи |
faHidden | $00000002 | Hidden files | Невидимые файлы |
faSysFile | $00000004 | System files | Системные файлы |
faVolumeID | $00000008 | Volume ID files | Метка тома |
faDirectory | $00000010 | Directory files | Папки |
faArchive | $00000020 | Archive files | Архивные файлы (для системы архивации) |
faAnyFile | $0000003F | Any file | Все файлы – комбинация выше указанных флагов |
if (SearchRec.Attr and faDirectory) <> faDirectoryздесь мы видим проверку флага faDirectory, работает это следующим образом, сначала изолируются не нужные биты, затем проводится проверка на неравенство нулю, поскольку все остальные биты изолированы, то возможны только два значения, ноль, если флаг не установлен и не ноль установлен, в зависимости от результата выполняется, или часть THEN, или часть ELSE. Других вещей касаемо нашей статьи в примере нет и поэтому рассматривать больше нечего. Прочие логические операции работают с булевыми, а не с битовыми значения. В заключение статьи можно еще привести примеры использования масок для изоляции битов и выполнения операций над оставшимися битами, возьмем для примера какую ни будь абстрактную комбинацию бит и выполним, что ни будь с ними. Например, у нас есть такая структура некоторого устройства, и при поступлении данных происходит прерывание, обработка которого поступает в наш обработчик и в другие вместе с кодом состояния, если мы обработали сообщение, то мы должны возвратить значение TRUE, если то FALSE и тогда управление будет передано следующему в цепочке обработчику. Бит TxReady проверять не надо, управление будет поступать, только тогда когда он установлен. abcccddd – где a – бит готовности b – бит разрешения прерывания ccc – тип операции ddd – счетчик
function MyHandler(Code: byte): Boolean;Ошибки при работе с битами Например, для сложения бит мы можем использовать два варианта или операцию + или операцию OR. Первый вариант является ошибочным. AnyValue + 2, если бит два установлен, то в результате этой операции произойдет перенос в следующий разряд, а сам бит окажется сброшенным вместо его установки, так можно поступать если только если есть уверенность в результате, то если заранее известно начальное значение. А вот в случае использования варианта AnyValue or 2, такой ошибки не произойдет. Тоже относится к операции вычитания для сброса бита. faAnyFiles – faDirectory ошибки не даст, а вот AnyFlags – AnyBit может, дать правильный вариант, а может нет. Зато AnyFlags and not AnyBit всегда даст то что замали, использования этой техники будет правильнее и для работы с аттрибутами файлов - faAnyFiles and not faDirectory. В качестве домашнего задания попробуйте выполнить это на бумаге для разных комбинацияй бит. Еще одна распростаненая ошибка, это логическая при выполнении операций над групами бит. Например неверено выполнять операцию сравнения над следующей конструкцией AnyFlags and 5 <> 0, если истина должна быть при установке обеих бит, надо писать так AnyFlags and 5 = 5, зато если устраивает истина при установке любого из бит, выражение AnyFlags and 5 <> 0 будет верныи. На этом статья закончена и вы смогли получить начальные сведения по выполнению логических операций с битами, в заключении приведу и таблицу весовых коэффициентов, чтобы было легче рассчитывать константы. Приложения Таблица весовых множителей для 32 битного числа
const
TxReady = $80;
IntBit = $40;
TypeMask = $38;
CounterMask = $07;
var
I: Integer;
TypeBits: Byte;
begin
if (Code and Intbit) = Intbit
then
begin
// изллируем биты типа и смещаем вправо для дальнейшей обработки
TypeBits := (Code and TypeMask) shr 3;
Case TypeBits of
0: begin
for I := 1 to (Code and CounterMask) do
begin
считываем N данных, количесво указано в битах CounterMask,
которые мы изолировали и использовали в качестве значения
для окончания цикла.
end;
Result := TRUE; // обрабатали, пусть больше никто не трогает
end;
1: begin
команда 1, что то делаем
Result := TRUE; // обрабатали, пусть больше никто не трогает
end;
2: begin
команда 2, что то делаем
Result := TRUE; // обрабатали, пусть больше никто не трогает
end;
else Result := FALSE; // другие команды не наше дело
end;
end
else
begin
Result := FALSE; // пусть другой обрабатывает
end;
end;
Бит | Dec | Hex | Бит | Dec | Hex | Бит | Dec | Hex | Бит | Dec | Hex |
0 | 1 | 1 | 8 | 256 | 100 | 16 | 65536 | 10000 | 24 | 16777216 | 1000000 |
1 | 2 | 2 | 9 | 512 | 200 | 17 | 131072 | 20000 | 25 | 33554432 | 2000000 |
2 | 4 | 4 | 10 | 1024 | 400 | 18 | 262144 | 40000 | 26 | 67108864 | 4000000 |
3 | 8 | 8 | 11 | 2048 | 800 | 19 | 524288 | 80000 | 27 | 134217728 | 8000000 |
4 | 16 | 10 | 12 | 4096 | 1000 | 20 | 1048576 | 100000 | 28 | 268435456 | 10000000 |
5 | 32 | 20 | 13 | 8192 | 2000 | 21 | 2097152 | 200000 | 29 | 536870912 | 20000000 |
6 | 64 | 40 | 14 | 16384 | 4000 | 22 | 4194304 | 400000 | 30 | 1073741824 | 40000000 |
7 | 128 | 80 | 15 | 32768 | 8000 | 23 | 8388608 | 800000 | 31 | 2147483648 | 80000000 |