From: Thomas Rast <tr@thomasrast.ch>
Date: Sat, 16 Nov 2013 10:28:28 GMT
Subject: Re: [PATCH v3 0/21] pack bitmaps
Message-ID: <87k3g8ljxv.fsf@linux-k42r.v.cablecom.net>
In-Reply-To: <20131114213320.GA16466@sigill.intra.peff.net>

Jeff King <peff@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
tr@thomasrast.ch