Logical Operations on Numbers

[Robert A. Cassels <Cassels@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Thu, 12 Jan 89 15:31 EST
    From: ELIOT@cs.umass.EDU

    Section 12.7 (pp 220-225) describes CL operations for manipulating
    finite sets using integers.  Unfortunately there does not seem to
    be any predicate to determine if one set is a subset of another
    using this representation.  'logtest' serves as an intersection test,
    'logbitp' serves as a member test but to determine subset relations
    seems to require computing the set difference (with logandc2) and
    comparing the result with zero.  If the sets are moderately large
    (say several hundred elements) this involves expensive bignum operations
    that I would like to avoid.

One can imagine a compiler noticing the pattern (LOGTEST .. (LOGNOT ..))
and compiling a call to a special routine which didn't do the explicit
LOGNOT computation.  I don't know of any compiler which does this,
though.

    I have also thought of using bitvectors, but the operations on bitvectors
    (p 294) only operate on bitvectors of the same length.

For vectors, it's not too hard to imagine that the shorter one should be
treated as if it were extended with zeros (presumably at the higher
index end).  It's a little harder to decide what to do in the
multidimensional case.

							    Furthermore,
    the bitvector functions only include bitwise operations, but no subset
    test here either.

    Isn't SUBSET considered an important set manipulation primitive?

    Chris Eliot
    University of Massashusetts at Amherst

Symbolics Common Lisp defines:

  SCL:BIT-VECTOR-SUBSET-P - Function (BIT-VECTOR-1 BIT-VECTOR-2 &key (:START1 0) :END1 (:START2 0) :END2)
   ;; BIT-VECTOR-1 is a subset of BIT-VECTOR-2
  SCL:BIT-VECTOR-POSITION - Function (BIT BIT-VECTOR &key (:START 0) :END)
   ;; equivalent to (POSITION BIT BIT-VECTOR :START START :END END)
  SCL:BIT-VECTOR-ZERO-P - Function (BIT-VECTOR &key (:START 0) :END)
  SCL:BIT-VECTOR-EQUAL - Function (BIT-VECTOR-1 BIT-VECTOR-2 &key (:START1 0) :END1 (:START2 0) :END2)
   ;; equivalent to (EQUAL (SUBSEQ BIT-VECTOR-1 :START START1 :END END1)
   ;;                      (SUBSEQ BIT-VECTOR-2 :START START2 :END END2))
  SCL:BIT-VECTOR-DISJOINT-P - Function (BIT-VECTOR-1 BIT-VECTOR-2 &key (:START1 0) :END1 (:START2 0) :END2)
  SCL:BIT-VECTOR-CARDINALITY - Function (BIT-VECTOR &key (:START 0) :END)
   ;; counts the "1" bits

At the present time, -SUBSET-P, -EQUAL, and -DISJOINT-P all return NIL
if the vectors have different lengths.

A more CL-consistent way of doing cardinality is probably by analogy
with the COUNT function:
  BIT-VECTOR-COUNT - Function (BIT BIT-VECTOR &key (:START 0) :END)
   ;; equivalent to (COUNT BIT BIT-VECTOR :START START :END END)