value range propagation for _bitwise_ OR

[Steven Schveighoffer]

On Sun, 11 Apr 2010 00:30:07 -0400, Steven Schveighoffer  
<schveiguy at yahoo.com> wrote:

> Couldn't help it, this seems like such a fun problem, I had to solve it  
> :)
>
> uint maxor(uint mina, uint maxa, uint minb, uint maxb)
> {
>      uint bt = 1 << 31;
>      uint result = 0;
>      while(bt)
>      {
>          if((bt & maxa) && (bt & mina))
>          {
>              result |= bt;
>              if((bt & minb) ^ (bt & maxb))
>              {
>                  return result | (bt-1);// always can choose all 1s for  
> rest of b
>              }
>          }
>          else if((bt & maxb) && (bt & minb))
>          {
>              result |= bt;
>              if((bt & mina) ^ (bt & maxa))
>              {
>                  return result | (bt-1);// always can choose all 1s for  
> rest of a
>              }
>          }
>          else if(bt & (maxa | maxb))
>          {
>              result |= bt;
>              if(bt & (maxa & maxb))
>              {
>                  // both maxa and maxb have bt set, and both mina and  
> minb have
>                  // bt unset.  This means we can choose this bit to be  
> set on
>                  // either, and it is possible to have all 1s set for  
> the other
>                  // for the rest of the bits.
>                  return result | (bt - 1);
>              }
>              else if(bt & maxa)
>              {
>                  // now that we are using this bit from maxa, we need to  
> raise
>                  // mina so it becomes the smallest value with bt set.   
> However,
>                  // we don't really care about bits above bt, so setting
>                  // it to 0 is fine.
>                  mina = 0;
>              }
>              else
>              {
>                  minb = 0;
>              }
>          }
>          // else, neither maxa or maxb have bt set, continue to next bit.
>          bt >>= 1;
>      }
>      return result;
> }

And the complementary minor:


uint minor(uint mina, uint maxa, uint minb, uint maxb)
{
     uint bt = 1 << 31;
     uint result = 0;
     while(bt)
     {
         if((bt & maxa) && (bt & mina))
         {
             result |= bt;
             if((bt & minb) ^ (bt & maxb))
             {
                 // bt will already be set for a, so set it also for b, this
                 // allows us to have all 0s for the rest of b.  Then we use
                 // mina to get the minimum for the rest of a
                 return result | ((bt-1) & mina);
             }
         }
         else if((bt & maxb) && (bt & minb))
         {
             result |= bt;
             if((bt & mina) ^ (bt & maxa))
             {
                 // ditto for b
                 return result | ((bt-1) & minb);
             }
         }
         else
         {
             if(bt & maxa)
             {
                 // we never want to choose a 1 here, so we want a zero,  
which
                 // makes the max for the rest of the bits all 1s.
                 maxa = ~0;
             }

             if(bt & maxb)
             {
                 // ditto for b
                 maxb = ~0;
             }
         }
         bt >>=1;
     }
     return result;
}

I tried to combine these into one function, but the cases are subtly  
different, so you end up just doing each in sequence.  The only thing you  
save is an extra function call and you can combine both loops into one.

I'll work on signed values tomorrow :)

-Steve