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.
|
| 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]?