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.)


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