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); 10001017 ? (integer-length 4); 1003 ? (integer-length -1); 10 ? (integer-length 0) 0 ? (integer-length -5); 10113

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

Copyright © 1995-2001, David B. Lamkins

All Rights Reserved Worldwide

This book may not be reproduced without the written consent of its author. Online distribution is restricted to the author's site.