another operation

[sebastian.egner@xxxxxxxxxxx]

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: sebastian.egner@xxxxxxxxxxx