Chapter 18 - Very Logical, Indeed...

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 evaluate only as much as they need

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.

Bits, bytes, and Boole

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.

  1. BOOLE-1 ; returns arg1
  2. BOOLE-2 ; returns arg2
  3. BOOLE-ANDC1 ; and complement of arg1 with arg2
  4. BOOLE-ANDC2 ; and arg1 with complement of arg2
  5. BOOLE-AND ; and arg1 with arg2
  6. BOOLE-C1 ; complement of arg1
  7. BOOLE-C2 ; complement of arg2
  8. BOOLE-CLR ; always all zeroes
  9. BOOLE-EQV ; exclusive-nor of arg1 with arg2 (equivalence)
  10. BOOLE-IOR ; inclusive-or of arg1 with arg2
  11. BOOLE-NAND ; not-and of arg1 with arg2
  12. BOOLE-NOR ; not-or of arg1 with arg2
  13. BOOLE-ORC1 ; or complement of arg1 with arg2
  14. BOOLE-ORC2 ; or arg1 with complement of arg2
  15. BOOLE-SET ; always all ones
  16. 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.)

  1. LOGAND
  2. LOGANDC1
  3. LOGANDC2
  4. LOGEQV
  5. LOGIOR
  6. LOGNAND
  7. LOGNOR
  8. LOGNOT
  9. LOGORC1
  10. LOGORC2
  11. 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

Bit vectors can go on forever

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.

  1. BIT-AND
  2. BIT-ANDC1
  3. BIT-ANDC2
  4. BIT-EQV
  5. BIT-IOR
  6. BIT-NAND
  7. BIT-NOR
  8. BIT-NOT
  9. BIT-ORC1
  10. BIT-ORC2
  11. 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

Chunks of bits make bytes

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

Contents | Cover
Chapter 17 | Chapter 19
Copyright © 1995-1999, 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.