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

*To*: sebastian.egner@xxxxxxxxxxx*Subject*: Re: another operation*From*: Aubrey Jaffer <agj@xxxxxxxxxxxx>*Date*: Sun, 9 Jan 2005 00:44:19 -0500 (EST)*Cc*: srfi-60@xxxxxxxxxxxxxxxxx*Delivered-to*: srfi-60@xxxxxxxxxxxxxxxxx*In-reply-to*: <OF0E0D2DB9.8CADA7D1-ONC1256F7F.002CF74B-C1256F7F.00332FFE@xxxxxxxxxxx> (sebastian.egner@xxxxxxxxxxx)*References*: <OF0E0D2DB9.8CADA7D1-ONC1256F7F.002CF74B-C1256F7F.00332FFE@xxxxxxxxxxx>

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

**Follow-Ups**:**Re: another operation***From:*bear

**References**:**another operation***From:*sebastian . egner

- Prev by Date:
**Re: another operation** - Next by Date:
**Re: another operation** - Previous by thread:
**Re: another operation** - Next by thread:
**Re: another operation** - Index(es):