(Previous discussion continued) Re: another operation Aubrey Jaffer 09 Jan 2005 05:44 UTC

Re: another operation Aubrey Jaffer 09 Jan 2005 05:44 UTC

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

```