к строкам 2 и 3 применим операцию побитового и, затем, согласно формуле (1), к получившемуся слову применим операцию побитового или со строкой 1, после чего к полученному результату и маске (строка 4) применим операцию побитового и. В полученном таким образом слове все биты, кроме второго, будут нулевыми. Выполним подобные вычисления для получения остальных битов результата и объединим все 32 слова с помощью операции или. В итоге получим искомую функцию.

Такое построение не дает эффективной программы вычисления значений функции, всего лишь показывая, что искомая функция может быть выражена с использованием команд из базового списка.

Используя эту теорему, можно сразу же увидеть, что не существует такой последовательности команд, которая обнуляла бы в слове крайний слева единичный бит, так как для этого необходимо просмотреть бить1, находящиеся слева от него (чтобы точно знать, что это действительно крайний слева единичный бит). Аналогично, не существует такой последовательности операций, которая бы давала сдвиг вгфаво, циклический сдвиг или сдвиг влево на переменную величину, а также могла подсчитать количество завершающих нулевых битов в слове (при подсчете завершающих нулевых битов младший бит результата должен быть равен 1, если это количество нечетно, и О, если четно; так что необходимо просмотреть биты слева от младшего, чтобы выяснить его значение).

Одним из применений рассмотренной сортировки битов является задача поиска следующего числа, которое больше заданного, но имеет такое же количество единичных битов. Зачем это может понадобиться? Эта задача возникает при использовании битовых строк для представления подмножеств. Возможные члены множества перечислены в одномерном массиве, а подмножество представляет собой слово или последовательность слов, в которых бит I установлен равным 1, если i-й элемент принадлежит этому подмножеству. Тогда объединение множеств вычисляется с помощью побитовой операции или над битовыми строками, пересечение - с помощью операции и и т.д.

Иногда требуется выполнить определенные действия над всеми подмножествами заданной длины, что легко сделать с помощью функции, отображающей представленное числом заданное подмножество в следующее большее число, содержащее такое же количество единичных битов, что и исходное (строка подмножества интерпретируется как целое число).

Компактный алгоритм для этой задачи составлен Р.У. Госпером (R.W. Gosper) [25, item 175]. Пусть имеется некоторое слово х, представляющее собой подмножество. Идея в том, чтобы сначала найти в х крайнюю справа группу смежных единичных битов, следующую за нулевыми битами, а затем увеличить представленную этой группой величину таким образом, чтобы количество единичных битов осталось неизменным. Например, строка хххОППОООО, где ххх- произвольные биты, преобразуется в строку ххх1(ХХЮ0111. Алгоритм работает следующим образом. Сначала в х определяется самый младший единичный бит, т.е. вычисляется s = x&.-x (в результате получаем (КХЮОООКХХЮ). Затем эта строка складывается с х, давая г=ххх 100000000, в которой

Вариант этого алгоритма имеется в [32], разд.7.6.7. 2.1. МАНИПУЛЯЦШ С МЛАДШИМИ БИТАМИ 27

получен первый единичный бит результата. Чтобы получить остальные биты, установим и-1 младших битов слова равными 1, где и - размер крайней правой группы единичных битов в исходном слове х. Для этого над тх выполняется операция исключающего или, что в нашем примере дает строку 000111110000.

В полученной строке содержится больше единичных битов, чем в исходной, поэтому выполним еще одно преобразование. Поделим искомое число на s, что эквивалентно его сдвигу вправо (S - степень 2), сдвинем его вправо еще на два разряда, что отфосит еще два нежелательных бита, и выполним операцию побитового или над полученным числом и г.

В записи компьютерной алгебры результату получается следующим образом.

у<-г (жФг)з>2

В листинге 2.1 представлена законченная процедура на языке С, выполняющая семь базовых RISC-команд, одной из которых является команда деления. (Данная процедура неприменима для х=0, так как в этом случае получается деление на 0.)

Листинг 2.1. Вычисление следующего большего числа с тем же количеством единичных битов

unsigned snoob(unsigned х) {

Если деление выполняется медленно, но у вас есть быстрый способ вычисления количества завершающих нулевых битов ntz{x), количества ведущих нулевых битов пЩх) или функции степени заполнения рор(х) (количество единичных битов в х), то последнюю строку в (2) можно заменить одной из приведенных ниже.

у«-г

\[{x®r){2 + ntL{x))

у«-г({д;Фг)»(33-п1г(*)) уг((1<к(рор(жФг)-2))-1)

2.2. Сложение и логические операции

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

а) б)

-Х = -цС + 1

= 4-1)

-X = -х~\

г) -X = x+l

д) -Х = Х-1

е) х+у = X-у-1

ж) = (хФ у) + 2{х&у)

з) = (х\у) + {х&у)

и) = 2{х\у)-(хФу) к) х-у = Х+-У + 1

л) = {хФу)-2{-&у)

м) = (х&-у)-{-л&у)

н) = 2(д;&у)-(д;Фу)

о) хФу = (дгу)-(ж&у)

п) х&-,у = {х\у)-у

Р) = х-{х&у)

с) -.(дг-у) = y-JC-l

т) = + >

у) Jc = y = {х&у)-(х\у)-\

Ф) . = {х&у)+{х\у)

X) дгу = (дг&у) + у

ц) jc&y = ( ау)--а

Равенство (г) можно повторно применял, к самому себе, например: -.-х = х + 2 итд. Аналогично, после повторного использования равенства (д) получаем: -i-x = x-2. Таким образом, чтобы добавить к х или вычесть из него некоторую константу, можно воспользоваться только этими выражениями дополнения.

Равенство (е) дуально равенству (к), которое представляет собой известное отношение, позволяющее получить вычитающее устройство из сумматора.

Равенства (ж) и (з) взяты из [25, item 23]. В равенстве (ж) суммах иу вычисляется следующим образом: сначалах иу суммируются без учета переносов (ж Фу), а затем к

полученному результату добавляются переносы. Равенство (з) изменяет операнды перед сложением так, что в любом разряде все комбинащ1и типа 0+1 заменяются на 1+0.

Можно показать, что при обычном сложении двоичных чисел с независимыми битами вероятность возникновения переноса в любом разряде равна 0.5. Однако, если при создании сумматора используется предварительная подготовка входных данных, как при сложении по формуле (ж), вероятность появления переноса становится равной 0.25. При разработке сумматора вероятность переноса значения не имеет; самой важной характеристикой при этом является максимальное количество логических схем, через которые может потребоваться пройти переносу, а использование равенства (ж) позволяет свести это количество всего лишь к одной схеме.

Равенства (л) и (м) дуальны равенствам (ж) и (з) для вычитания. В (л) сначала выполняется вычитание без заемов (ж Фу), а затем из полученного результата вычитаются за-емы. Аналогично, равенство (м) изменяет операнды перед вычитанием таким образом, что все комбинации типа 1 -1 заменяются на 0-0.

2.2. СЛОЖЕНИЕ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ 29