[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: another operation

This page is part of the web mail archives of SRFI 60 from before July 7th, 2015. The new archives for SRFI 60 contain all messages, not just those from before July 7th, 2015.



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