| From: xxxxxx@philips.com
 | Date: Tue, 4 Jan 2005 10:18:14 +0100
 |
 | 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.

I believe the following procedure computes this:

(define (foo n)
  (if (negative? n) (set! n (lognot n)))
  (+ -1 (integer-length (logand n (+ 1 (lognot n))))))

Without the sign test, LEAST-SIGNIFICANT-ONE-INDEX returns what it
says for both positive and negative n:

(define (least-significant-one-index n)
  (+ -1 (integer-length (logand n (+ 1 (lognot n))))))

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

(logand) ==> -1 because (and) ==> #t.

This is also necessitated because logand is associative:

(logand a b) == (logand a (logand b) (logand))