Now it's time to look at things having to do with boolean (true and false) logic. We'll learn about common logical functions, and conditional evaluation. If you're a bit twiddler, this chapter should warm your heart: we'll introduce bit manipulation functions, bit vectors, and generalized byte manipulation.
AND and OR are macros in Common Lisp.
This means that they have control over when (and if) their
arguments get evaluated. AND and OR take
advantage of this ability: they stop evaluating their arguments as
soon as they determine an answer.
Consider AND: it evaluates its arguments, starting
with the leftmost, only as long as each argument evaluates to a true
(i.e. not NIL) value. As soon as AND
evaluates the leftmost false (NIL) argument, its work
is done -- the result will be NIL no matter how many
more true arguments it evaluates, so AND just returns
NIL without evaluating any more of its arguments. (Think
of this as a "one strike and you're out" policy.) AND returns
true only if all of its arguments evaluate to a true value.
In fact, AND returns either NIL (if one of
its arguments evaluates to NIL) or the non-NIL
value of its rightmost argument. Some Lisp programmers take advantage of
this to treat AND as a simple conditional.
? (defun safe-elt (sequence index)
(and (< -1 index (length sequence)) ; guard condition
(values (elt sequence index) t)))
SAFE-ELT
? (safe-elt #(1 2 3) 3)
NIL
? (elt #(1 2 3) 3)
Error: index out of bounds
? (safe-elt #(1 2 3) 2)
3
T
OR also evaluates only enough arguments to determine
its result: it evaluates arguments, starting with the leftmost, so
long as they evaluate to NIL. The first
non-NIL result is returned as OR's value;
arguments further to the right are not evaluated.
One caution is in order about AND and OR.
Because they are macros, and not functions, they can not be used for
mapping (see Chapter 12). Use the predicate
mapping functions (SOME, EVERY, etc.) instead.
Machine languages and low-level programming languages always provide the ability to perform bitwise boolean operations: groups of bits are logically combined on a bit-by-bit basis; adjacent bits have no effect on their neighbors in determining the result. The same languages also let you treat adjacent groupings of bits as a unit; this is commonly called a byte or a bit field. Usually bitwise and bit field operations are constrained by the size of hardware registers.
Lisp makes these same facilities available, but removes the constraints that might otherwise be imposed by the underlying hardware.
Sixteen bitwise boolean operations are available in Lisp through
the BOOLE function. BOOLE is a
three-argument functions expecting an operation designator plus two
integer arguments and producing an integer result. Remember that
Lisp has infinite precision integers (bignums), so these bitwise
boolean operations are exempt from machine limitations (except for
available memory).
The operation designator is a constant value having a name from the following list. The actual values of these constants is specific to the Lisp implementation.
BOOLE-1 ; returns arg1
BOOLE-2 ; returns arg2
BOOLE-ANDC1 ; and complement of arg1 with arg2
BOOLE-ANDC2 ; and arg1 with complement of arg2
BOOLE-AND ; and arg1 with arg2
BOOLE-C1 ; complement of arg1
BOOLE-C2 ; complement of arg2
BOOLE-CLR ; always all zeroes
BOOLE-EQV ; exclusive-nor of arg1 with arg2 (equivalence)
BOOLE-IOR ; inclusive-or of arg1 with arg2
BOOLE-NAND ; not-and of arg1 with arg2
BOOLE-NOR ; not-or of arg1 with arg2
BOOLE-ORC1 ; or complement of arg1 with arg2
BOOLE-ORC2 ; or arg1 with complement of arg2
BOOLE-SET ; always all ones
BOOLE-XOR ; exclusive-or of arg1 with arg2
? (boole boole-and 15 7) 7 ? (boole boole-ior 2 3) 3 ? (boole boole-set 99 55) -1 ? (boole boole-andc2 7 4) 3
There are also eleven bitwise logical functions; these
are similiar to the BOOLE operations, except that the constant
and identity operations are not present in this group, and the complement
function takes only one argument. (Except for LOGNOT, all of
the following functions expect two arguments.)
LOGAND
LOGANDC1
LOGANDC2
LOGEQV
LOGIOR
LOGNAND
LOGNOR
LOGNOT
LOGORC1
LOGORC2
LOGXOR
LOGTEST returns true if any of the corresponding bits in its
two arguments are both ones.
? (logtest 7 16) NIL ? (logtest 15 5) T
LOGBITP tests one bit in the two's complement representation
of an integer, returning T if the bit is 1 and NIL
if the bit is 0. The least significant (rightmost) bit is bit 0.
? (logbitp 0 16) NIL ? (logbitp 4 16) T ? (logbitp 0 -2) NIL ? (logbitp 77 -2) T
LOGCOUNT counts 1 bits in the binary representation
of a positive integer, and 0 bits in the two's complement binary
representation of a negative number.
? (logcount 35) 3 ? (logcount -2) 1
A vector composed of only 1s and 0s has a compact representation
as a bit vector, a special representation for printing and
reading, and a set of logical operations. Like all vectors (and
arrays) in Common Lisp, the size of a bit vector is limited by the
constant ARRAY-TOTAL-SIZE-LIMIT; this can be as small
as 1,024, but is typically large enough that the size of memory sets
a practical limit on the size of bit-vectors.
The printed representation of a bit vector begins with the
#* reader macro, followed by 1s and 0s. The bit
vector's length is determined by the 1s and 0s that make up its
elements. (The printed representation of an empty bit vector is
#*.)
? #*0010101 #*0010101 ? (length #*0010101) 7
There are eleven bitwise logical operations available for bit vectors.
With the exception of BIT-NOT, these are all functions of
two arguments. Unlike the corresponding bitwise logical operations on
integers, the bit vector logical operations expect their arguments to
be of the same size.
BIT-AND
BIT-ANDC1
BIT-ANDC2
BIT-EQV
BIT-IOR
BIT-NAND
BIT-NOR
BIT-NOT
BIT-ORC1
BIT-ORC2
BIT-XOR
These functions will destructively update a result bit vector if
you provide an optional third (second in the case of
BIT-NOT) argument. If the optional argument is
T, then the first argument will be updated with the
result bits. If the optional argument is a bit vector, it will be
updated with the result bits and the input arguments will be
unchanged. (This in-place update is not available for bitwise
operations on integers; destructive bit vector operations
may be more efficient once the number of bits exceeds the size of a
fixnum.)
? (bit-and #*00110100 #*10101010) #*00100000 ? (bit-ior #*00110100 #*10101010) #*10111110 ? (bit-not #*00110100) #*11001011
You can access an individual element of a bit vector using
BIT. This is a vector accessor, and not a boolean test,
so it returns 0 or 1. BIT can also be used in a
SETF form to alter an element of a bit vector.
? (bit #*01001 1)
1
? (let ((bv (copy-seq #*00000)))
(setf (bit bv 3) 1)
bv)
#*00010
Getting back to integer manipulation as we wrap up this chapter, we'll see how to manipulate fields of adjacent bits within an integer value.
The first thing we need when manipulating a field of bits (called a
byte in Common Lisp) is a way of specifying its bounds.
The BYTE function constructs a byte specifier from a
size (number of bits) and a position (the number of the rightmost bit
of the byte within the containing integer, where the LSB is bit 0).
The representation of a byte specifier depends upon the Lisp implementation.
The functions BYTE-SIZE and BYTE-POSITION
extract the size and position values from a byte specifier.
? (setq bs (byte 5 3)) ; 5 bits, rightmost has weight 2^3 in source
248 ; implementation-dependent
? (byte-size bs)
5
? (byte-position bs)
3
You can extract and replace bytes from an integer using the functions
LDB (load byte) and DPB (deposit byte).
? (ldb (byte 8 8) 258) 1 ? (ldb (byte 8 0) 258) 2 ? (dpb 3 (byte 8 8) 0) 768 ? (dpb 1 (byte 1 5) 1) 33
LDB-TEST returns true if any of the bits are 1 in a
specified byte.
? (ldb-test (byte 3 2) 3) NIL ? (ldb-test (byte 3 2) 9) T ? (ldb-test (byte 3 2) 34) NIL
INTEGER-LENGTH tells you how many bits are necessary
to represent an integer in two's complement form. A positive integer
will always have an unsigned representation using the number of bits
determined by INTEGER-LENGTH. A negative integer has a
signed binary representation that requires one bit more than the
number of bits determined by INTEGER-LENGTH.
? (integer-length 69) ; 1000101 7 ? (integer-length 4) ; 100 3 ? (integer-length -1) ; 1 0 ? (integer-length 0) 0 ? (integer-length -5) ; 1011 3
You can shift the bits in an integer using the ASH function.
This is an arithmetic shift; it treats the integer as a two's
complement binary number and preserves the sign (leftmost) bit as the rest
of the bits are shifted. A left shift shifts bits to the left, replacing
them with zeroes (and preserving the sign bit). A right shift shifts bits
to the right, replacing them with zeroes (and preserving the sign bit).
ASH expects two arguments, an integer to be shifted,
and a shift count. A shift count of 0 returns the integer unchanged.
A positive count shifts bits to the left by the specified number of
positions. A negative count shifts bits to the right.
? (ash 75 0) 75 ? (ash 31 1) 62 ? (ash -7 1) -14 ? (ash 32 8) 8192 ? (ash -1 8) -256 ? (ash 16 -1) 8 ? (ash 11 -1) 5 ? (ash 32 -8) 0 ; all one bits shifted out ? (ash -99 -2) -25