Re: [PATCH v3 0/21] pack bitmaps

From: Thomas Rast <tr@thomasrast.ch>
Date: Nov 16, 2013, 10:28 UTC
Message-ID: <87k3g8ljxv.fsf@linux-k42r.v.cablecom.net>
In-Reply-To: <20131114213320.GA16466@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 13 quoted lines

>> >   - 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