OK, I found a solution that is optimal in over 99% of the cases (99.195% to be precise), while still being fast (because it avoids looping over the bits):
==============================8<------------------------------
uint32_t maxOr (uint32_t minA, uint32_t minB,
uint32_t maxA, uint32_t maxB)
{
if (maxA == 0) return maxB;
if (maxB == 0) return maxA;
uint32_t a = maxA ^ minA;
if (a != 0)
a = ((1 << highbit (a)) - 1);
uint32_t b = maxB ^ minB;
if (b != 0)
b = ((1 << highbit (b)) - 1);
uint32_t t = maxA & maxB;
if (t != 0)
t = ((1 << highbit (t)) - 1);
return min (maxA|maxB|a|b, maxA|maxB|t);
}
------------------------------>8==============================
Mostly it's black magic ;) and it's **much** simpler than the first
version that reached those performances. The explanation is in the
rest of the message.
I will only talk about the ``a`` side of the problem here (i.e
assume ``maxB==minB``). The ``b`` side is symmetrical.
The idea is to build a value that is between minA and maxA and will
set as many bits as possible when or'ed with maxB:
- The first thing we do is to notice that minA and maxA have the
following structure (in binary): ``minA=A0x`` and ``maxA=A1y``
where the ``A`` part is identical. Any number between minA and
maxA will therefore be of the form ``a=Az``. A very conservative
estimate tells us that if we set ``z`` to all ones, then
``maxB|maxA|z`` will be greater than ``maxB|a`` for all ``a``.
This is computed by ``(1 << highbit (maxA ^ minA)) - 1``;
- Another way to look at the problem is to say that a ``0`` bit in
maxA cannot be set unless some higher ``1`` bit is unset. For
example if maxA is ``0b10`` then if we want to set bit 0, we need
to unset bit 1 (which will give us ``0b01``). So by doing this we
get a lower value for ``a|maxB`` unless this bit was already set
in maxB. The expression ``maxA & maxB`` gives us the bits that we
can unset. Therefore only bits that are less significant than the
high bit of ``maxA & maxB`` may be set. This is stored into the
variable ``t``;
- Either method works, but neither is perfect. By taking the
minimum of the two results, we get the best of both worlds
(although still isn't perfect).
Jerome
--
mailto:jeber...@free.fr
http://jeberger.free.fr
Jabber: jeber...@jabber.fr
signature.asc
Description: OpenPGP digital signature
