Jeff King <p...@peff.net> 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
t...@thomasrast.ch
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to