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