value range propagation for _bitwise_ OR

[Steven Schveighoffer]

On Sat, 10 Apr 2010 22:53:42 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 04/10/2010 09:51 PM, Steven Schveighoffer wrote:
>> Andrei Alexandrescu Wrote:
>>
>>> On 04/10/2010 12:01 PM, Andrei Alexandrescu wrote:
>>>> Consider:
>>>>
>>>> byte c = a | b;
>>>>
>>>> Say you already know min_a, max_a, min_b, and max_b. How do you
>>>> compute min_c and max_c? I thought of it for a bit and it seems
>>>> quite tricky.
>>>>
>>>>
>>>> Thanks,
>>>>
>>>> Andrei
>>>
>>> I think this would work:
>>>
>>> uint maxOR(uint maxa, uint maxb) { if (maxa<  maxb) return
>>> maxOR(maxb, maxa); uint candidate = 0; foreach (i, bit;
>>> byBitDescending(maxa)) { if (bit) continue; auto t = candidate |
>>> (1<<  (31 - i)); if (t<= maxb) candidate = t; } return maxa |
>>> candidate; }
>>>
>>> The idea is to find the candidate that would fill as many zeros in
>>> maxa as possible.
>>>
>>> But this is inefficient. I'm wondering whether a simple bitwise
>>> manipulation expression could do the trick.
>>
>> Don't you need to take into account the minimum of b also?  That is,
>> the candidate needs to be greater than minb.  Because filling in more
>> holes doesn't necessarily mean biggest number, I don't think it
>> works.
>
> Ha! Good point. I'd forgotten the initial requirement and considered  
> both values to start at 0. They don't! Adam? :o)

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

This only solves unsigned (tested all ranges against a brute force  
solution up to max values of 64, given the nature of binary, I don't think  
there can be any weird cases that wouldn't have problems at lower ranges.   
Note that in my solution, maxa and maxb are inclusive.

Signed is probably trickier, suppose one is always negative and one is  
always positive!  I'm satisfied solving the unsigned for now, maybe  
someone else can modify this solution to work with signed integers also :)

-Steve