Jeff King <peff@xxxxxxxx> writes:
>> > - the ewah code used gcc's __builtin_ctzll, but did not provide a
>> > suitable fallback. We now provide a fallback in C.
>>
>> I was messing around with several implementations (including the use of
>> msvc compiler intrinsics) with the intention of doing some timing tests
>> etc. [I suspected my C fallback function (a different implementation to
>> yours) would be slightly faster.]
>
> Yeah, I looked around for several implementations, and ultimately wrote
> one that was the most readable to me. The one I found shortest and most
> inscrutable was:
>
> return popcount((x & -x) - 1);
In two's complement, -x = ~x + 1 [1]. If you have a bunch of 0s at the
end, as in (binary; a=~A etc)
x = abcdef1000
then
~x = ABCDEF0111
~x + 1 = -x = ABCDEF1000
(x&-x) = 0000001000
(x&-x) - 1 = 0000000111
popcount() of that is the number of trailing zeroes you started with.
Please don't ask me to work out what happens in border cases; my head
hurts already.
[1] because x + ~x is all one bits. +1 makes it overflow to 0, so that
x + -x = 0 as it should.
--
Thomas Rast
tr@xxxxxxxxxxxxx
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html