value range propagation for _bitwise_ OR

[Steven Schveighoffer]

On Mon, 12 Apr 2010 22:37:00 -0400, Steven Schveighoffer  
<schveiguy at yahoo.com> wrote:

> Jérôme M. Berger Wrote:
>
>> Steven Schveighoffer wrote:
>> > Fails for test case:
>> >
>> > minA = 4, maxA = 4, minB = 4, maxB = 6 (outputs 7, accurate result is  
>> 6).
>> >
>> 	Nope, outputs 6. Note that I've run an exhaustive search for all
>> combinations in the [0, 63] range, so if there are mistakes they
>> have to be outside that range...
>>
>
> I'll have to double check, I thought I copied your code verbatim (I did  
> switch around the arguments to be minA, maxA, minB, maxB to fit my test  
> harness, and I changed the uint_32_t to uint).  I'll check tomorrow at  
> work where the computer I used to test is.

I confirm, with the updated highbit, your solution works.

Also, inspired by your solution (and using your highbit function, which is  
very neat BTW) I came up with a one-liner.  Enjoy :)

uint maxor(uint mina, uint maxa, uint minb, uint maxb)
{
     return maxa | maxb | ((1 << highbit(((1 << (max(highbit(mina ^ maxa),  
highbit(minb ^ maxb)) + 1)) - 1) & maxa & maxb)) - 1);
}

Anyone want to do the equivalent minor?  I've spent way too much time on  
this :)

-Steve