[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*: Fri, 7 Jan 2005 22:48:02 -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. | | Note that FOO can be terribly slow when implemented | representation-agnostic, while being lightning fast if the implementor | has access to the actual machine words. That it is faster with "access to the actual machine words" surprises me. What is this faster algorithm? Is it asymptotically better than O(n) [n being number of bits]?

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

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