СИСТЕМЫ СЧИСЛЕНИЯ И ПРЕДСТАВЛЕНИЕ ЧИСЕЛ Хотя внутримашинное представление данных основано на их двоичном представлении, при программировании задач на языках высокого уровня это практически незаметно, поскольку средства этих языков в первую очередь заботятся об удобном представлении данных. При программировании же на машинном языке, да и при обращении напря- мую к аппаратным средствам из программ на языках высокого уров- ня, требуется определенное понимание свойств чисел в различных системах счисления, и особенно в двоичной системе, которая, яв- ляясь минимально возможной позиционной системой, обладает рядом уникальных свойств, широко используемых во многих приложениях, в том числе в электронике и программировании. Количество цифр, используемых в системе счисления, называется ее основанием. В программировании обычно применяются системы с ос- нованием 2, 8, 10 и 16. В системах с основанием, большим 10, для обозначения цифр за девяткой используются другие символы; обычно это буквы A, B, C и т.д. Например, в шестнадцатеричной системе используются буквы A..F. Правило счета во всех системах одинаково; его удобно представ- лять на примере обычного механического счетчика километража в автомобиле или расхода электроэнергии на силовом щите. Каждое колесо счетчика представляет один разряд числа; по периметру ко- леса нанесены цифры нужной системы счисления, начиная с нуля. Количество колес называется разрядностью счетчика, а окошки, че- рез которые видны цифры - разрядной сеткой. Начальное значение счетчика - все нули. Прибавление единицы к числу производится поворотом колеса младшего (правого) разряда на одну цифру вперед - при этом цифра в младшем разряде замещается следующей по по- рядку. Когда при очередном повороте из окошка "уходит" последняя цифра системы счисления - она замещается нулем и происходит пе- ренос в следующий (расположенный левее) разряд путем прибавления единицы к нему, то есть процесс повторяется рекурсивно. Анало- гично производится счет назад; в этом случае при переходе от ну- ля к последней цифре системы счисления возникает заем из следу- ющего разряда счетчика. Легко заметить, что величина числа, представленного счетчиком (количество поворотов-шагов от нулевого состояния) не зависит от системы счисления, то есть число по отношению к системе счисле- ния инвариантно. Меняется лишь форма его представления по причи- не различной информационной емкости набора цифр. Информационная емкость счетчика (количество различных чисел, ко- торые он может представлять) равна основанию системы счисления в степени, равной количеству разрядов счетчика. Отсюда следует, что, например, 4-разрядный восьмеричный счетчик и 3-разрядный шестнадцатеричный имеют одинаковую информационную емкость. Когда все разряды счетчика содержат максимальные цифры системы счисления, следующее прибавление единицы переводит все разряды в нулевое состояние, а возникающий из старшего разряда перенос те- ряется. Такая ситуация называется переполнением разрядной сетки. Если за этим не следить, то получится так называемый счет по мо- дулю: число, видимое на счетчике, будет равно остатку от деления реального результата на информационную емкость счетчика, которая в этом случае называется модулем счета. Можно заметить, что сдвиг числа на счетчике на один разряд влево (при условии, что старший разряд числа нулевой) равносилен его умножению на основание системы счисления. Если же старший разряд ненулевой, число не может быть умножено в данной сетке - возни- кает переполнение. Сдвиг числа на разряд вправо равносилен его делению на основание системы; выдвигаемый наружу разряд содержит остаток. Двоичный счетчик будет предельным случаем N-ичного счетчика; вместо колес в нем могут использоваться плоские пластины, а про- цесс вращения вырождается в их опрокидывание. При этом опрокиды- вание разряда вперед из 0 в 1 или назад из 1 в 0 не влияет на соседний левый разряд, а вперед из 1 в 0 или назад из 0 в 1 - - вызывает перенос (опрокидывание следующего слева разряда). На 8-разрядном двоичном счетчике (или 8-разрядным двоичным чис- лом) можно представить 256 различных чисел в диапазоне 0..255. Если необходимы отрицательные числа, для них выделяется половина всех двоичных комбинаций, а для представления используется тот факт, что отрицательное число образуется при вычитании такого же положительного числа из нуля. Применяя это правило к числу -1 (вычитая из нулевого счетчика единицу), получаем результат 11111111 - это и есть представление отрицательной единицы. Про- должая процесс, получаем -2 = 11111110, -3 = 11111101 и т.д. При этом, как и при счете вперед, на одну половину значений прихо- дится нулевое значение старшего разряда, а на другую - единич- ное; первому соответствуют положительные числа, а второму - от- рицательные, то есть старший разряд числа кодирует его знак. С учетом всех этих соглашений, на 8-разрядной двоичной сетке можно представить либо 256 неотрицательных чисел, либо набор из 128 отрицательных, нуля и 127 положительных. Соответствие между ними получается следующим: Двоичное Десятичное Десятичное представление беззнаковое знаковое 00000000 0 0 00000001 1 1 01111110 126 126 01111111 127 127 10000000 128 -128 10000001 129 -127 11111110 254 -2 11111111 255 -1 Такое представление знаковых чисел именуется дополнительным ко- дом. Оно замечательно тем, что двоичная форма числа не несет в себе информации о своем знаке: число 10000001 можно рассматри- вать и как 129, и как -127, в зависимости от соглашений по коди- рованию. Это избавляет процессор от дополнительных расходов, связанных с различиями в операциях над положительными и отрица- тельными числами. Взамен этого в процессор вводится логика кон- троля результата операции, сравнивающая перенос в старший разряд с переносом из него. При операциях со знаковыми числами неравен- ство этих переносов сообщает о переполнении; при операциях с беззнаковыми числами перенос в старший разряд игнорируется. Инверсия всех разрядов числа и прибавление к результату единицы меняет знак числа на противоположный. При этом числа 0 и -128, как не имеющие обратных, отображаются сами на себя. Соответствующим образом кодируются знаковые числа любой разряд- ности. Для преобразования знаковых чисел из одной разрядной сет- ки в другую применяется так называемое расширение и сокращение знака. Расширение знака состоит в добавлении к числу слева необ- ходимого количества цифр, равных состоянию его знакового разря- да: к неотрицательным числам добавляются нули, к отрицательным - единицы. В результате образуется такое же по величине число большей разрядности. Сокращение знака состоит в отбрасывании нескольких старших цифр числа при условии, что все они одиниковы и совпадают со старшим разрядом результата; в противном случае число не может быть представлено требуемым количеством разрядов. Например, число -7 в пятиразрядном представлении (11001) может быть преобразовано в 8-разрядное (11111001) и в 4-разрядное (1001); преобразовать его в 3-разрядное число невозможно - теря- ется знаковый разряд. Для беззнаковых чисел расширение и сокра- щение производится простым добавлением и сокращением незначащих нулей. Преобразования беззнаковых чисел между системами счисления про- изводятся, исходя из того, что число в любой системе может быть представлено суммой, каждое слагаемое которой равно произведению N-ной цифры числа (нумерация с нуля справа налево) на основание системы в степени N. Например, число 981 в десятичной системе может быть записано как 9*100+8*10+1*1. При делении числа на ос- нование системы младшая цифра выпадает в остаток, а у остальных показатель степени основания уменьшается на единицу; тем самым младшая цифра отделяется от числа. Следующая цифра получаются применением того же приема к частному и т.д. Процесс завершается при получении нулевого частного; а так как при нулевом частном остаток равен делимому, то последнее деление можно не выполнять, когда делимое меньше основания системы. Поскольку само число не зависит от системы счисления, его можно делить и на основание "чужой" системы, получая верные цифры и заменяя при необходимос- ти остатки 10, 11, ... на цифры A, B и т.д. Такой способ приме- ним для получения цифр числа в "чужой" системе счисления путем проведения вычислений в "своей" системе. Например, то же число 981 при последовательном делении на 8 дает цифры 5, 2, 7, 1; за- писывая их, начиная со старшей, получаем 1725. Для преобразования числа, записанного в "чужой" системе, в пред- ставление "своей" системы, применяется обратная операция: цифры числа "чужой" системы записываются в виде многочлена с множите- лями, равными соответствующим степеням основания "чужой" систе- мы. Для восьмеричного числа 1725 многочлен (опять-таки в восьме- ричной системе) имеет вид 1*1000+7*100+2*10+5*1. Переписанный в десятичной системе, он примет вид 1*512+7*64+2*8+5*1, что равно 981. Преобразование отрицательных чисел машинным способом выполняется точно так же; вручную же это удобнее делать с соответствующим положительным числом, изменяя впоследствии знак результата или кодируя его в соответствии с принятыми соглашениями. Дробные числа обычно представляются в экспоненциальной форме в виде целых чисел, умножаемых на 2 в некоторой степени; в этом представлении целое число именуется мантиссой, а степень двойки - порядком. Естественно, такая форма является приближенной, даже если исходное десятичное число задано точно. БУЛЕВА АЛГЕБРА ...Женская логика построена на четырех основных операциях: - И да, и нет; - Ни да, ни нет; - Три раза нет; - Нет и не проси! (из разговора в университетской курилке) Булева алгебра (двоичная логика) оперирует с величинами, могущи- ми принимать два значения. Изначально алгебра была создана для проверки логических высказываний, а ее величины могли принимать значения "Истина" и "Ложь". Впоследствии алгебра была успешно применена во многих областях науки, в том числе в электронике и информатике. Соответственно, интерпретация значений величин мо- жет быть любой - Да/Нет, Есть/Нет, Истина/Ложь, Включено/Выклю- чено, Разрешено/Запрещено и т.п. В числовой интерпретации это выражается цифрами 0 и 1, образующими двоичную систему счисле- ния. Одним из основных свойств двоичной логики является "принцип ис- ключенного третьего": если значение A не равно нулю, то оно рав- но единице и наоборот. Иначе говоря, ОТРИЦАНИЕ того, что величи- на имеет одно конкретное значение, одновременно является УТВЕР- ЖДЕНИЕМ того, что она имеет другое, опять же конкретное, значе- ние. Это свойство широко используется во многих применениях. Основными операциями в булевой алгебре являются унарная операция "НЕ" (отрицание, инверсия) и две бинарные операции: "И" (логи- ческое умножение, конъюнкция), и "ИЛИ" (логическое сложение, дизъюнкция). Операция НЕ определяется просто: ее результат противоположен значению операнда. В многозначных логиках операция НЕ определя- ется как результат арифметического вычитания операнда из старшей цифры системы счисления логики; это справедливо и для двоичной - НЕ X = 1-X. Операции И/ИЛИ могут быть определены несколькими способами. Один из них - прямой - таблица значений операций: A B A И B A ИЛИ B 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1 Другой способ - косвенный, использующий принцип исключенного третьего: операция И дает единицу, если оба операнда - единицы; операция ИЛИ дает нуль, если оба операнда - нули. Можно и наобо- рот: операция И дает нуль, если хотя бы один из операндов - нуль; операция ИЛИ дает единицу, если хотя бы один из операндов - единица. Это очень похоже на операции сложения/умножения в арифметике, применительно к величинам типа "нуль"/"не нуль". Сравнив определения операций И/ИЛИ, можно заметить, что они до- полняют друг друга: НЕ (A ИЛИ B) = (НЕ A) И (НЕ B) НЕ (A И B) = (НЕ A) ИЛИ (НЕ B) Эти равенства носят название правила Де Моргана. Третий способ - последовательный: результатом операции A И B бу- дет нуль, если A равно нулю, в противном случае результат равен B; результатом операции A ИЛИ B будет единица, если A равно еди- нице, иначе результат равен B. В силу коммутативности операций И/ИЛИ A и B в этом определении можно поменять местами. Способ наглядно показывает, что в ряде случаев результат операции может быть определен только на основе значения одного из операндов, что широко используется компиляторами при вычислении условных выражений (так называемый ShortCut). Кроме операций И/ИЛИ/НЕ, часто используется операция ИСКЛЮЧАЮЩЕЕ ИЛИ: A B A ИСКЛЮЧАЮЩЕЕ ИЛИ B 0 0 0 0 1 1 1 0 1 1 1 0 Косвенное определение операции: результатом будет единица, если операнды не равны; результатом будет нуль, если операнды равны. Обратная ИСКЛЮЧАЮЩЕМУ ИЛИ операция именуется ТОЖДЕСТЕННОСТЬЮ: результатом будет единица, если операнды равны и наоборот; в связи с этим ИСКЛЮЧАЮЩЕЕ ИЛИ иногда именуется операцией нетож- дественности. ИСКЛЮЧАЮЩЕЕ ИЛИ называют еще операцией полусуммирования: ее ре- зультат равен младшему разряду арифметической суммы операндов. Старший разряд может быть получен операцией И. Можно видеть, что ИСКЛЮЧАЮЩЕЕ ИЛИ операнда с нулем возвращает само значение операнда, а с единицей - его инверсию. Двойное применение к операнду ИСКЛЮЧАЮЩЕГО ИЛИ с одним и тем же значени- ем дает исходное значение операнда, что широко используется в криптографии: первое наложение ключа шифрует операнд, второе - расшифровывает его. Одноразрядные двоичные числа в программировании часто называются флагами или семафорами; нуль обозначает сброшенное состояние, единица - установленное. При помощи флагов реализуется двоичная сигнализация: хорошо/плохо, плюс/минус, можно/нельзя и т.п. Для одиночного флага имеет смысл лишь операция инверсии; к двум и более флагам применяются любые булевы операции, выполняемые пос- ледовательно. Операции И и ИЛИ, выполняемые над несколькими операндами, имеют характерное свойство: любой нуль в И или единица в ИЛИ поглощает все остальные операнды, и результат операции не будет зависеть от них. Результат же операции же ИСКЛЮЧАЮЩЕЕ ИЛИ в равной степе- ни зависит от каждого из ее операндов, что часто используется в целях контроля: результат применения операции к последователь- ности слов носит название контрольной суммы, которая передается вместе с исходными данными; несовпадение переданной и вычислен- ной сумм указывает на искажение переданных данных. Булевы операции распространяются и на многоразрядные двоичные числа, называемые еще двоичными словами; операция выполняется поразрядно, отдельно с каждым разрядом (инверсия) или парой раз- рядов (бинарные операции). Двоичные слова, участвующие в бинар- ных операциях, выравниваются по младшим (правым) разрядам и бо- лее короткое дополняется нулями слева. Разряды слов принято ну- меровать справа налево, начиная с нуля. Широкое применение булевой алгебры в программировании обусловле- но ее базированием на двоичной системе счисления, простотой ап- паратной реализации и широким спектром полезных приложений. Ос- новным приложением булевой алгебры в программировании являются операции над множествами. При снятии с математического понятия множества требования беско- нечности оно естественным образом ложится на двоичное представ- ление: множество мощности N может быть описано N-разрядным дво- ичным словом, каждый разряд которого отвечает за определенный элемент множества, показывая наличие его в множестве в данный момент. Например, множество дней недели может быть описано 7-разрядным двоичным словом; нужно лишь условиться о соответ- ствии дней разрядам слова и правилах обозначения присутству- ющих/отсутствующих элементов. Если поставить в соответствие раз- рядам слова 0..6 дни недели с понедельника до воскресения и от- мечать присутствующие в множестве элементы единицами (так назы- ваемое прямое представление, используемое чаще всего), то мно- жество рабочих дней в неделе будет описываться словом 0011111. Инвертируя это слово, получаем дополнение множества - множество элементов, отсутствующих в нем. В данном случае это даст слово 1100000, которое можно интерпретировать как множество выходных дней недели. Иначе говоря, применение операции НЕ к множеству рабочих дней дает множество НЕ-рабочих дней (правило исключенно- го третьего). Количество единиц в прямом представлении множества (или нулей в обратном) равно мощности множества (количеству элементов в нем). Булевы операции естественным образом описывают и другие операции с множествами. Например, операция И дает пересечение множеств, операция ИЛИ - их объединение. Операция ИСКЛЮЧАЮЩЕЕ ИЛИ дает множество несовпадающих элементов. Вспоминая, что операция разности множеств A-B (исключение из A элементов, общих у A и B), определяется, как пересечение A с до- полнением B, можно перенести эту операцию на язык логических операций: представление разности A и B равно логическому умноже- нию представления A на инверсию представления B: A-B = A И НЕ B. Рассматривая процесс детально, можно видеть, что единицы в пред- ставлении множества B, соответствующие присутствующим в нем эле- ментам, при инверсии превращаются в нули, которые в операции И гасят соответствующие им разряды в представлении множества A. Отсутствующие же элементы множества B, обозначенные нулями, при инверсии дают единицы, которые, в соответствии с определением операции И, "пропускают" в результат соответствующие им разряды представления A. Например, вычитая из множества дней понедель- ник..суббота множество рабочих дней, получаем: 0111111 - 0011111 = 0111111 И (НЕ 0011111) = 0111111 И 1100000 = 0100000, то есть субботу. Другая реализация операции вычитания: A-B = (A ИЛИ B) ИСКЛЮЧА- ЮЩЕЕ ИЛИ B. Она замечательна тем, что не требует инверсии второ- го операнда; при программировании на машинном языке при этом экономится одна команда и один промежуточный регистр. Подобная операция применяется и для обратного вычитания: B-A = (A ИСКЛЮ- ЧАЮЩЕЕ ИЛИ B) И B. Результатом вычитания A-B являются элементы A, отсутствующие в B. Это часто используется в программах, обрабатывающих события, например, нажатия кнопок мыши. Драйвер мыши поставляет двоичное значение, в котором единицами отмечены нажатые в данный момент кнопки. Вычитая из этого значения ранее полученное состояние кнопок, можно кратчайшим путем определить множество кнопок, на- жатых со времени последнего опроса мыши. Вычитание множеств может быть интерпретировано и как ответ на вопрос "Все ли элементы множества A имеются в множестве B?". Ближайший пример - проверка полномочий пользователя на выполне- ние некоторых действий. Если A - множество требуемых пользовате- лем действий, а B - множество его полномочий, то A-B описывает требуемые действия, на которые нет полномочий; нулевой результат (пустое множество) означает наличие полномочий на все требуемые действия. Вспоминая, что булева алгебра была создана для проверки логичес- ких высказываний, интересно проследить связь между логической формулой и ее словесной интерпретацией: если A - множество того, что пользователь хочет, B - того, что он может, то A-B - того, чего он A-B = A И НЕ B = хочет И НЕ может (обратная ситуация обычно не рассматривается столь пристально). Операции над множествами неявно используются в программировании при работе с так называемыми битовыми масками. Битовой (двоич- ной) маской называется двоичное слово, один или несколько разря- дов которого отмечают положение элементов множества. Обычно по- ложение элементов отмечается единицами; такая маска называется прямой или положительной, если нулями - обратной (отрицательной или инверсной). Например, для вышеописанного множества дней не- дели маска 0010000 отмечает (или маскИрует) элемент множества "пятница"; обратной маской элемента будет слово 1101111. Маска 1100000 отмечает выходные дни недели, а 0010101 - дни "трехразо- вого питания" (понедельник, среда, пятница). Маски, выделяющие один разряд, обычно называются масками флагов; маски групп смеж- ных разрядов - масками полей. Рассматривая операцию И со словом и прямой маской со стороны последней, можно видеть, что разряды маски подобны вентилям: единица в разряде маски "пропускает" в результат соответствующий разряд второго операнда, а нуль "закрывает путь", принудительно обнуляя разряд результата. Операция ИЛИ со словом и обратной маской действеут наоборот: нуль "пропускает" разряд второго опе- ранда, а единица независимо от него дает единицу в разряде ре- зультата. Описанное свойство используется для выделения из двоичных слов интересующих групп разрядов; кроме того, в процессорах, имеющих аппаратный флаг нулевого результата, почти всегда имеется разно- видность операции И, для которой регистрируется только факт ра- венства нулю результата. Такие операции называются операциями тестирования и позволяют проверять равенство нулю одновременно всех выбранных разрядов двоичного слова. Маски флагов чаще всего применяются для установки/сброса флага в двоичном слове. Например, если в разряде 3 определенного байта памяти находится флаг включения некоторого режима работы прог- раммы, операция ИЛИ с этим байтом и маской 00001000 установит этот флаг (результат операции помещается обратно в байт), а опе- рация И с обратной маской - 11110111 - сбросит его. Операция И с прямой маской позволяет проверить состояние флага: ненулевой ре- зультат сообщает о том, что флаг установлен. Еще одна операция, применяемая к двоичным словам - поразрядный сдвиг. Сдвиг слова влево на N разрядов (с заполнением освобожда- ющихся разрядов нулями) эквивалентен его умножению на 2 в степе- ни N, сдвиг вправо - целочисленному делению на ту же величину (выдвигаемые младшие разряды содержат остаток от деления). Сдви- ги используются для совмещения групп разрядов и их перемещения внутри двоичного слова. Можно видеть, что деление на степень двойки при помощи сдвига вправо корректно работает только для беззнаковых или положитель- ных чисел. Для исключения несоответствия введено понятие знако- вого сдвига, когда значение знакового разряда слова сохраняется. Естественно, такой вид сдвига не подходит для деления беззнако- вых чисел; для каждого типа необходима соответствующая операция сдвига. Сдвиг же влево выполняется для любого типа чисел одина- ково. БИТОВЫЕ ПОЛЯ В ДВОИЧНЫХ СЛОВАХ Группа смежных разрядов в двоичном слове называется битовым по- лем. Количество разрядов поля называется его шириной, номер младшего разряда поля внутри слова называется начальным, или ба- зовым, разрядом поля. При помощи комбинации логических операций со сдвигами реализует- ся упаковка двоичных слов в битовые поля слов большей разряднос- ти и их обратная распаковка. Например, если некоторый объект мо- жет пребывать в пяти состояниях, для кодирования этого множества состояний достаточно трех битов. Выделение для состояния объекта отдельного байта не вызывает проблем, когда их количество не превышает нескольких десятков; если же таких объектов тысячи, это может оказаться разорительным. Используя упаковку, в одном байте можно хранить состояния двух объектов, в 16-разрядном сло- ве - уже пяти. Для работы с упакованными значениями необходимы битовые маски упакованных полей. Наиболее удобны два вида масок: параллельные и приведенные к нулевому разряду. Параллельная маска отмечает разряды поля в тех же позициях, в каких они находятся внутри слова; приведенная маска отмечает разряды поля, сдвинутого в младшие разряды слова. Параллельные маски удобны тем, что с их помощью можно работать с полями прямо на месте, например, обнулять, инвертировать или тестировать их; однако на каждое поле нужна своя параллельная маска. Приведенная маска зависит только от ширины поля и не учи- тывает его положение в слове; для полей одинаковой ширины нужна только одна приведенная маска, однако для работы с полем необхо- дим либо сдвиг маски в позицию поля (преобразование ее в парал- лельную), либо сдвиг поля в младшие разряды слова (приведение поля). Если идет упаковка двух трехбитовых полей в байт, то параллель- ные маски могут иметь значения 00000111 для первого поля и 00111000 для второго. В оставшиеся два разряда байта можно упа- ковать одно двухбитовое поле или два флага. Процедура помещения неупакованного значения в упакованное двоич- ное слово состоит в сдвиге значения в нужную позицию и врезке его в нужное поле слова. Врезка обычно выполняется операцией ИЛИ, которая требует, чтобы разряды поля в двоичном слове были обнулены, так же, как и посторонние разряды во врезаемом значе- нии: Врезаемое значение 0000000XXXXX000000 Двоичное слово XXXXXXX00000XXXXXX Обнуление поля в двоичном слове обычно выполняется операцией И с обратной параллельной маской поля; обнуление посторонних разря- дов врезаемого значения выполняется операцией И либо с приведен- ной маской до сдвига, либо с параллельной маской после сдвига. Распаковка поля из слова выполняется в обратном порядке; выделе- ние разрядов поля из слова можно осуществить при помощи либо па- раллельной маски до сдвига, либо приведенной маски после сдвига. Применяя к упакованному слову операцию И с маской поля, можно судить о том, имеет ли поле нулевое значение, не распаковывая его. Если в поле упаковано знаковое число, таким же образом мож- но определить его знак. СОЧЕТАНИЕ АРИФМЕТИЧЕСКИХ И ЛОГИЧЕСКИХ ОПЕРАЦИЙ Внимательно рассматривая операцию увеличения двоичного числа на 1, называемую еще инкрементом, можно заметить, что она выполняет инверсию разрядов числа, начиная с младшего, и кончая первым ну- левым разрядом. Например, инкремент числа 27 (11011) дает 28 (11100) - инвертируются три младших разряда. Аналогично, умень- шение числа на 1 (декремент), инвертирует разряды до первой еди- ницы. Отсюда следствие: любые два смежных двоичных числа имеют сколько-то совпадающих старших разрядов (возможно нуль), а ос- тальные их разряды взаимно-инверсны. Сочетание инкремента/декремента с логическими операциями дает полезные результаты: X И (X-1) - сбрасывает младший единичный разряд X X ИЛИ (X+1) - устанавливает младший нулевой разряд X X И НЕ (X-1) - выделяет младший единичный разряд X X ИЛИ НЕ (X+1) - выделяет младший нулевой разряд X Первые две комбинации могут использоваться для подсчета количес- тва единиц или нулей в слове. Инкремент числа, представленного N смежными единицами, дает двойку в степени N, представленную единицей в разряде N, и на- оборот: 31+1 = 11111+1 = 100000 = 32 = 2^5 Обнуление N младших разрядов числа реализует округление до бли- жайшего кратного 2^N в меньшую сторону (с недостатком). Округле- ние с избытком реализуется сложением числа с (2^N)-1 и округле- нием результата в меньшую сторону. Обнуление N младших разрядов можно выполнить по формуле: X И НЕ ((2^N)-1) пользуясь предыдущим свойством инкремента/декремента. Например, округление числа до предыдущего четного выполняется сбросом его младшего разряда, а до следующего четного - увеличением на 1 и сбросом младшего разряда результата. Выделение N младших разрядов числа дает остаток от его деления на 2^N; равенство нулю N младших разрядов числа означает, что оно кратно 2^N. Например, нулевой разряд числа служит признаком его четности.