12.7 Логические операции над числами

Логические операции в данном разделе в качестве аргументов требуют целых чисел. Передача числа любого другого формата является ошибкой. Функции обрабатывают целые числа, как если бы они были представлены в двух системах счисления. FIXME _____________________________________________

Заметка для реализации: Внутренне, конечно, реализация Common Lisp’а может использовать и может и нет представление числа с дополнительным кодом. Все, что необходимо это чтобы логические операции выполняли вычисление так, как описано в разделе.

___________________________________________________________________________________________________________

Логические операции предоставляют удобный способ для представления бесконечного вектора битов. Пусть такой концептуальный вектор будет индексироваться с помощью неотрицательного целого. Тогда биту j присваивается «вес (weight)» 2j. Предположим, что лишь конечное число битов являются 1 или только конечное число битов являются 0. Вектор, у которого конечное число битов 1, представлен как сумма всех весов этих битов, и является положительным числом. Вектор, у которого конечное число битов 0, представлен как -1 минус сумма всех весов этих битов, и является отрицательным числом. FIXME

Данный метод использования целых чисел для представления битовых векторов может в свою очередь использоваться для представления множеств. Предположим, что некоторая (возможно бесконечная) совокупность рассуждений для множеств отображается в неотрицательные целые числа. FIXME Тогда множество может быть представлено как битовый вектор. Элемент принадлежит множеству, если бит, индекс которого соответствует элементу, является 1. Таким образом все конечные множества могут быть представлены с помощью положительных целых, и множества, дополнения которых конечны, с помощью отрицательных чисел. Функции logior, logand и logxor, определённые ниже, вычисляют объединение, пересечение и симметричную разность для таких множеств.

[Функция] logior &rest integers

Функция возвращает побитовое логическое или для аргументов. Если не задан ни один аргумент, возвращается ноль.


[Функция] logxor &rest integers

Функция возвращает побитовое логическое исключающее или для аргументов. Если не задан ни один аргумент, возвращается ноль.


[Функция] logand &rest integers

Функция возвращает побитовое логическое и для аргументов. Если ни один аргумент не задан, возвращается ноль.


[Функция] logeqv &rest integers

Функция возвращает побитовую логическую эквивалентность (также известную как исключающее отрицающее или для аргументов. Если не задан ни один аргумент, возвращается ноль.


[Функция] lognand integer1 integer2
[Функция] lognor integer1 integer2
[Функция] logandc1 integer1 integer2
[Функция] logandc2 integer1 integer2
[Функция] logorc1 integer1 integer2
[Функция] logorc2 integer1 integer2

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

(lognand n1 n2)  (lognot (logand n1 n2))
(lognor n1 n2)  (lognot (logior n1 n2))
(logandc1 n1 n2)  (logand (lognot n1) n2)
(logandc2 n1 n2)  (logand n1 (lognot n2))
(logorc1 n1 n2)  (logior (lognot n1) n2)
(logorc2 n1 n2)  (logior n1 (lognot n2))


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

integer10011
integer20101Имя операции
logand  0001и
logior  0111или
logxor  0110исключающее или
logeqv  1001эквивалентность (исключающее отрицающее или)
lognand 1110не и
lognor  1000не или
logandc10100не integer1 и integer2
logandc20010integer1 и не integer2
logorc1 1101не integer1 или integer2
logorc2 1011integer1 или не integer2






[Функция] boole op integer1 integer2
[Константа] boole-clr
[Константа] boole-set
[Константа] boole-1
[Константа] boole-2
[Константа] boole-c1
[Константа] boole-c2
[Константа] boole-and
[Константа] boole-ior
[Константа] boole-xor
[Константа] boole-eqv
[Константа] boole-nand
[Константа] boole-nor
[Константа] boole-andc1
[Константа] boole-andc2
[Константа] boole-orc1
[Константа] boole-orc2

Функция boole принимает операцию op и два целых числа, и возвращает целое число полученное применением операции op к этим двум числам. Точные значения шестнадцати констант зависят от реализации, но они подходят для использования в качестве первого аргумента для boole:

integer10011
integer20101Выполняемая операция
boole-clr  0000всегда 0
boole-set  1111всегда 1
boole-1    0011integer1
boole-2    0101integer2
boole-c1   1100дополнение integer1
boole-c2   1010дополнение integer2
boole-and  0001и
boole-ior   0 1 1 1 или
boole-xor  0110исключающее или
boole-eqv  1001эквивалентность (исключительное отрицающее или)
boole-nand 1110не и
boole-nor   1 0 0 0 не или
boole-andc10100не integer1 и integer2
boole-andc20010integer1 и не integer2
boole-orc1 1101не integer1 или integer2
boole-orc2 1011integer1 или не integer2






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

(boole boole-and x y)  (logand x y)

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


[Функция] lognot integer

Функция возвращает битовое логическое отрицание аргумента. Каждый бит результата является дополнение соответствующего исходного бита аргумента.

(logbitp j (lognot x))  (not (logbitp j x))


[Функция] logtest integer1 integer2

logtest является предикатом, который истинен, если любой бит определённый как 1 в integer1 также является соответствующим битом 1 в integer2.

(logtest x y)  (not (zerop (logand x y)))


[Функция] logbitp index integer

Предикат logbitp является истиной, если бит в позиции index в целом числе integer (то есть, его вес 2index), является 1, иначе предикат ложен. Например:

(logbitp 2 6) is true
(logbitp 0 6) is false
(logbitp k n)  (ldb-test (byte 1 k) n)

index должен быть неотрицательным целым числом.


[Функция] ash integer count

Если count положительное число, данная функция арифметически сдвигает число integer влево на количество бит count. Если count отрицательное число, функция сдвигает число integer вправо. Знак результата всегда такое же как и исходного числа integer.

Говоря математически, эта операция выполняет вычисления floor(integer ⋅ 2count).

Логически, функция перемещает все биты числа integer влево, добавляя нулевые биты в конец, или вправо отбрасывая биты в конце числа. (В этом контексте вопрос о том, что сдвигается налево, не относится к делу. Целые числа, рассматриваемые как строки битов, являются «полубесконечными», то есть концептуально расширяются бесконечно влево FIXME.) Например:

(logbitp j (ash n k))  (and (>= j k) (logbitp (- j k) n))


[Функция] logcount integer

Функция возвращает количество бит в числе integer. Если integer положительное число, тогда подсчитаны будут биты 1. Если число integer отрицательно, то в два раза дополненной (two’s-complement) бинарной форме будут подсчитаны биты 0. FIXME Результатом всегда является неотрицательное целое число. Например:

(logcount 13)  3      ;Бинарное представление ...0001101
(logcount -13)  2     ;Бинарное представление ...1110011
(logcount 30)  4      ;Бинарное представление ...0011110
(logcount -30)  4     ;Бинарное представление ...1100010

Следующее тождество всегда верно:

(logcount x)  (logcount (- (+ x 1)))
              (logcount (lognot x))


[Функция] integer-length integer

Данная функция выполняет следующие вычисления

ceiling(log 2(if integer < 0 then −integer else integer + 1))

Эта функция полезна в двух случаях. Первое, если целое число integer не отрицательно, тогда его значение может быть представлено в беззнаковой бинарной форме в поле, ширина которого в битах не меньше чем (integer-length integer). Второе, независимо от знака числа integer, его значение может быть представлено как знаковая бинарная два раза дополненная (two’s-complement) форма в поле, ширина которого в битах не меньше чем (+ (integer-length integer) 1). FIXME Например:
(integer-length 0)  0
(integer-length 1)  1
(integer-length 3)  2
(integer-length 4)  3
(integer-length 7)  3
(integer-length -1)  0
(integer-length -4)  2
(integer-length -7)  3
(integer-length -8)  3