Двоичная математика

=== Двоичная математика ===
==== Введение ====
Наряду с обычными логическими операция над логическими типами 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
Выражение истинно, когда истинны оба бита. Присказка «И там И там»
OR - (включающие) логическое ИЛИ, эта операции выглядит так
A	B	Y
0	0	0
0	1	1
1	0	1
1	1	1
Выражение истинно, когда истинен хотя бы один бит. Присказка «ИЛИ там ИЛИ там, включая и там и там»
XOR - (исключающие) логическое ИЛИ, эта операции выглядит так
A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0
Выражение истинно, когда истинен только один бит. Присказка «ИЛИ там ИЛИ там, исключая и там и там»
NOT - отрицание или инверсия бита, эта операции применяется только к одному биту, действие простое текущее значение бита изменяется на противоположное
A	Y
0	1
1	0
SHL - логический сдвиг влево, операции применяется только к группе битов, одного из целочисленных типов Паскаля, например к байту, слову и т.д.
 
Сдвиг байта влево на один разряд.
Разряды	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
Байт смещается влево на один или более разрядов, позиции справа замещаются нулями, позиции слева теряются.
SHR - логический сдвиг вправо, операции применяется только к группе битов, одного из целочисленных типов Паскаля, например к байту, слову и т.д.
 
Сдвиг байта вправо на один разряд.
Разряды	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
Байт смещается вправо на один или более разрядов, позиции слева замещаются нулями, позиции справа теряются.
На этом описание операций заканчивается, и переходим к практическим примерам. Но вначале немного слов о нотации
==== Применяемая нотация при отображении чисел в литературе ====
Числа в символьной форме принято отображать, так что бы младшие разряды были справа, а строки слева, при этом если используется выравнивание, то оно тоже подчиняется этим правилам.
Нумерация разрядов начинается с нуля в соответствии со степень разряда и описывается формулой K*M^N, где K это коэффициент в диапазоне от 0 до M-1, M это основание числа, а N это степень. Число в степени 0 для всех оснований равно 1.
Посмотрим на примере следующей таблицы для четырех основных оснований.
Для числа 100
Основание	Значение	Формула
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
Для числа 123
Основание	Значение	Формула
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;
begin
 Result := Src or (1 shl Bit);
end;
Здесь происходит следующее:
Сначала мы рассчитываем позицию бита - (1 shl Bit), затем устанавливаем полученный бит и возвращаем результат через предопределенную переменную Result.
Пример использования:
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;
begin
 Result := Src and not (1 shl Bit);
end;
Здесь происходит следующее:
Сначала мы рассчитываем позицию бита - (1 shl Bit), затем с помощью операции NOT инвертируем полученную маску, устанавливая, не затрагиваемые биты маски в единицу, а затрагиваемый бит в ноль, затем сбрасываем этот бит, а результат возвращаем результат через предопределенную переменную Result.
Пример использования:
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;
begin
 Result := Src xor (1 shl Bit);
end;
Здесь происходит следующее:
Сначала мы рассчитываем позицию бита - (1 shl Bit), затем с помощью операции XOR переключаем бит, а результат возвращаем результат через предопределенную переменную Result.
Пример использования:
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
Как видим, состояние бита B2 изменяется на противоположное.
===== Проверка бита =====
Для проверки бита используется операция AND и анализ результата на равенство нулю.
if Value and (1 shl N) <> 0 then //... установлен
if Value and (1 shl N) = 0 then //... не установлен
чаще всего это используется в другой форме, вместо расчета позиции используется именованная константа, например
const
 B2 = 4 // B2 (1 shl 2)
begin
 if Value and B2 = B2 then //... установлен
 if Value and B2 = 0 then //... не установлен
end;
Это более наглядно, особенно если константе дано более значимое имя, чем B2, например, для проверки готовности передатчика мы можем определить константу с именем TxReady, тогда это будет выглядеть очень красиво.
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, отдельные биты данной маски описаны как именованные константы.
Наименование	Значение 	Description 	Описание
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;
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;
==== Ошибки при работе с битами ====
Например, для сложения бит мы можем использовать два варианта или операцию + или операцию 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 битного числа
Бит	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
С уважением, Анатолий Подгорецкий (6 сентября 2003 года)
Author: Анатолий Подгорецкий
Source: http://www.podgoretsky.com
ID: 00232
Category:Статьи