value range propagation for _bitwise_ OR

[Andrei Alexandrescu]

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.


Andrei