value range propagation for _bitwise_ OR

["Jérôme M. Berger"]

	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:jeberger at free.fr
http://jeberger.free.fr
Jabber: jeberger at jabber.fr

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100411/b879f580/attachment.pgp>