value range propagation for _bitwise_ OR

[Steven Schveighoffer]

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.

Simple counter case:

a's range is 4 to 5
b's range is 4 to 4

The max value of a | b is 5.

However, I think your function will return 15.

Also, you may to use the max of the smaller number.  For example:

a's range is 3 to 5
b's range is 4 to 4
The max number here is 7, but only when a is 3 and b is 4.  With your method, you automatically assume the number with the highest max value should be at its max value.

I think this is going to need a recursive solution, but I haven't yet wrapped my brain around how it needs to work.  I think you should start by assuming for a given range, mina to maxa, you know that the top 1-bits from ~(mina ^ maxa) will always be in the result, same with b.  If you eliminate those bits, the problem gets narrower.  I feel like a good solution first eliminates those, then decides how to set the next bit, and recurses.  I'm sure there's some sort of method to decide how to set the bit in order to avoid brute force, but I haven't thought about it enough.

-Steve