Another (stupid) question: "find first set" (or "find first zero")

[Martin Simmons]

>>>>> On Tue, 2 Feb 2021 14:00:08 +0100, Pascal Bourguignon said:
> 
> Note: if we have access to the implementation of bignum (eg. if we patch 
> the implementation to provide ffs "natively"), we can optimize even more 
> by merging the two solutions.
> 
> (- x) would process the whole bignum, as would (logand x (- x)), but 
> after this operation, we have only 0s on the left of the bignum.
> 
> Instead, we can process the bignum word by word (starting with the least 
> significant word), computing:
> (+ (lognot (bignum-word-ref bignum i)) carry) -> i+1, new-carry
> and (logand (bignum-word-ref bignum i)
>              (+ (lognot (bignum-word-ref bignum i)) carry))
> while we get 0.
> Once we get a value ≠ 0, it has a single bit set which we can identify 
> with integer-length or looping etc (we process a single word here),
> and stop processing now, because all the other words will give 0 as result.

Even better, we can just do logbitp ≠ 0 in word-sized chunks.  I.e. scan from
the least significant word until (bignum-word-ref bignum i) is non-zero and
then, as you say, process that non-zero word in some way to find the first 1.

-- 
Martin Simmons
LispWorks Ltd
http://www.lispworks.com/