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