value range propagation for _bitwise_ OR

[Andrei Alexandrescu]

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)

Andrei