Re: 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