Hello Aubrey,

Recently, I have been using bit-twiddling extensively for representing and manipulating
subsets of finite sets---one of the purposes you mention in the SRFI document.

Two remarks:

1. As it turns out, I frequently need the following operation missing in SRFI-60:

        (FOO x) ==> i         ; this is not my proposal for the procedure's name ;-)

        i >= 0 is the index of the least significant bit set in integer x in case x > 0,
        or in -x-1 if x < 0. If x = 0 then [choose: i = -1 OR (error ...) OR i = #f OR ...]
           In other words, i = max {k >= 0 : 2^k divides x} for x > 0.

Note that FOO can be terribly slow when implemented representation-agnostic,
while being lightning fast if the implementor has access to the actual machine words.

2. When scanning different libraries of bit-twiddling, I had stumbled across an implicit
design decision that is worth mentioning because it might swiftly break portability's neck:

        "What is the value of (LOGAND)?"

In my application I define (LOGAND) := 0 because the subsets my numbers represent
are finite from way back, their parents are finite, they stay finite and vote finite. However,
(LOGAND) := -1 also makes a lot of sense because -1 (= all bits set) is the neutral element
for bitwise AND---and one can even interpret negative numbers as the complements of
finite sets. (A concept that I later abandonned because the saved case distinctions do
not make up for the confusion this creates.)

Sebastian.


P.S. Just for information, here is the specification of the Bitset (BSET) data type I use.
It turned out to be useful, convenient, and complete for its purpose (which is of course
only one of the potential applications of bit-twiddling):

; Bitsets (BSET)
; ==============
;
; A bset s represents a subset S of a fixed set X = {x[0], .., x[n-1]}.
; The set X, called the universe, is implicit in the context and is
; only passed explicitly when bsets are constructed and the subsets
; they represent are accessed.
;
; For convenience, we even identify X with {0..n-1} and delegate the
; bijection between a general finite set of cardinality n and {0..n-1}
; to other data structures, e.g. search trees. A bset s is a non-negative
; integer of which the x-th bit is set if and only if x is an element of
; the set being represented by s.
;
; Naming convention:
;   n        : cardinality of the universe, exact integer, n >= 0
;   s, t, .. : bsets, i.e. exact integers in {0..2^n-1}
;   x, y, .. : elements of {0..n-1}
;
; Procedures:
;
; (bset? obj)               test if obj is exact non-negative integer
; (bset x ...)              smallest set containing the given elements
; (bset-full n)             the set {0..n-1}, n >= 0
; (bset-empty? s)           test if s = {}
; (bset-in? x s)            test if x in s
; (bset-equal? s t)         test if s = t
; (bset-compare s t)        -1 if s < t, 0 if s = t, 1 if s > t
; (bset-subset? s t)        test if s is a subset of t
; (bset-disjoint? s t)      test if s and t are disjoint
; (bset-size s)             number of elements of s
; (bset-min s)              minimal element of s, or #f if s is empty
; (bset-max s)              maximal element of s, or #f if s is empty
; (bset-union s ...)        union of the sets, (bset-union) = 0
; (bset-intersection s ...) intersection of the sets, (bset-intersection) = 0
; (bset-difference s t ...) difference of s and union of the t's
; (bset->list s)            list of elements in s in increasing order
;
; Macros using and extending SRFI-42 'Eager comprehensions':
;
; (bset-ec <qualifier>^* <element>)
;    the bset of the elements obtained by evaluating <element> for
;    each binding in the sequence defined by <qualifier>^*.
;
; (bset-union-ec <qualifier>^* <bset>)
;    the union of the bsets obtained by evaluating <bset> for each
;    binding in the sequence defined by the <qualifier>^*.
;
; (:bset <x> [ (index <i>) ] <bset>)
;    binds <x> in turn to each element in <bset>. The elements
;    of <bset> are enumerated in strictly increasing order.
;
; (:bset-in? <in?> [ (index <x>) ] [ <n> ] <bset>)
;    binds <in?> to #t if x is in <bset> and to #f otherwise.
;    The sequence enumerates all elements x in {0..<n>-1},
;    or in {0..max(<bset>)} if n is not provided, in strictly
;    increasing order.

----
Dr. Sebastian Egner
Senior Scientist
Philips Research Laboratories
Prof. Holstlaan 4 (postbox WY63, kamer WY 6-55)
5656 AA Eindhoven
The Netherlands
tel:       +31 40 27-42069
fax:      +31 40 27-42566
email: xxxxxx@philips.com