value range propagation for _bitwise_ OR

[Don]

Steven Schveighoffer wrote:
> 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

Awesome stuff, guys.
I think that's worthy of inclusion as an exercise in Knuth's Volume 4, 
fascile 1. Suggest it to someone at ACCU?
(Knuth has highbit(x) but calls it lambda(x). He notes the result that 
highbit(x)==highbit(y) iff x^y <= x&y).