12.7. Logical Operations on Numbers

Common Lisp the Language, 2nd Edition

Next: Byte Manipulation Functions<br>Up: Numbers<br>Previous: Type Conversions and

12.7. Logical Operations on Numbers

The logical operations in this section require integers<br>as arguments; it is an error to supply a non-integer as an argument.<br>The functions all treat integers as if<br>they were represented in two's-complement notation.

Implementation note: Internally, of course, an implementation of<br>Common Lisp may or may not use a two's-complement representation.<br>All that is necessary is that the logical operations<br>perform calculations so as to give this appearance to the user.

The logical operations provide a convenient way to represent<br>an infinite vector of bits. Let such a conceptual vector be<br>indexed by the non-negative integers. Then bit j is assigned<br>a ``weight'' .<br>Assume that only a finite number of bits are 1's<br>or only a finite number of bits are 0's.<br>A vector with only a finite number of one-bits is represented<br>as the sum of the weights of the one-bits, a positive integer.<br>A vector with only a finite number of zero-bits is represented<br>as -1 minus the sum of the weights of the zero-bits, a negative integer.

This method of using integers to represent bit-vectors can in turn<br>be used to represent sets. Suppose that some (possibly countably<br>infinite) universe of discourse<br>for sets is mapped into the non-negative integers.<br>Then a set can be represented as a bit vector; an element is in the<br>set if the bit whose index corresponds to that element is a one-bit.<br>In this way all finite sets can be represented (by positive<br>integers), as well as all sets whose complements are finite<br>(by negative integers). The functions logior, logand,<br>and logxor defined below then compute the union,<br>intersection, and symmetric difference operations on sets<br>represented in this way.

[Function]

logior &rest integersThis returns the bit-wise logical inclusive or of its arguments.<br>If no argument is given, then the result is zero,<br>which is an identity for this operation.

[Function]

logxor &rest integersThis returns the bit-wise logical exclusive or of its arguments.<br>If no argument is given, then the result is zero,<br>which is an identity for this operation.

[Function]

logand &rest integersThis returns the bit-wise logical and of its arguments.<br>If no argument is given, then the result is -1,<br>which is an identity for this operation.

[Function]

logeqv &rest integersThis returns the bit-wise logical equivalence (also known as exclusive nor)<br>of its arguments.<br>If no argument is given, then the result is -1,<br>which is an identity for this operation.

[Function]

lognand integer1 integer2<br>lognor integer1 integer2<br>logandc1 integer1 integer2<br>logandc2 integer1 integer2<br>logorc1 integer1 integer2<br>logorc2 integer1 integer2These are the other six non-trivial bit-wise logical operations<br>on two arguments. Because they are not associative,<br>they take exactly two arguments rather than any non-negative number<br>of arguments.

(lognand n1 n2) == (lognot (logand n1 n2))<br>(lognor n1 n2) == (lognot (logior n1 n2))<br>(logandc1 n1 n2) == (logand (lognot n1) n2)<br>(logandc2 n1 n2) == (logand n1 (lognot n2))<br>(logorc1 n1 n2) == (logior (lognot n1) n2)<br>(logorc2 n1 n2) == (logior n1 (lognot n2))

The ten bit-wise logical operations on two integers are summarized<br>in the following table:

integer1 0 0 1 1<br>integer2 0 1 0 1 Operation Name<br>logand 0 0 0 1 and<br>logior 0 1 1 1 inclusive or<br>logxor 0 1 1 0 exclusive or<br>logeqv 1 0 0 1 equivalence (exclusive nor)<br>lognand 1 1 1 0 not-and<br>lognor 1 0 0 0 not-or<br>logandc1 0 1 0 0 and complement of integer1 with integer2<br>logandc2 0 0 1 0 and integer1 with complement of integer2<br>logorc1 1 1 0 1 or complement of integer1 with integer2<br>logorc2 1 0 1 1 or integer1 with complement of integer2

[Function]

boole op integer1 integer2

[Constant]

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-orc2The function boole takes an operation op and two integers,<br>and returns an integer produced by performing the logical operation<br>specified by op on the two integers. The precise values of<br>the sixteen constants are implementation-dependent, but they are<br>suitable for use as the first argument to boole:

integer1 0 0 1 1<br>integer2 0 1 0 1 Operation Performed<br>boole-clr 0 0 0 0 always 0<br>boole-set 1 1 1 1 always 1<br>boole-1 0 0 1 1 integer1<br>boole-2 0 1 0 1 integer2<br>boole-c1 1 1 0 0 complement of integer1<br>boole-c2 1 0 1 0 complement of integer2<br>boole-and 0 0 0 1 and<br>boole-ior 0 1 1 1 inclusive or<br>boole-xor 0 1 1 0 exclusive or<br>boole-eqv 1 0 0 1 equivalence (exclusive nor)<br>boole-nand 1 1 1 0 not-and<br>boole-nor 1 0 0 0 not-or<br>boole-andc1 0 1 0 0 and complement of integer1 with integer2<br>boole-andc2 0 0 1 0 and integer1 with complement of integer2<br>boole-orc1 1 1 0 1 or complement of integer1 with integer2<br>boole-orc2 1 0 1 1 or integer1 with complement of integer2

boole...