value range propagation for _bitwise_ OR

[Don]

Jérôme M. Berger wrote:
> Andrei Alexandrescu wrote:
>> On 04/16/2010 11:43 PM, Steven Schveighoffer wrote:
>>> Andrei Alexandrescu Wrote:
>>>
>>>> Looks great, thanks Jerome!
>>>>
>>>> Now, how about that case in which some or all of the ranges
>>>> involved include negative values?
>>> I solved already signed values in terms of any valid unsigned
>>> solution, see here:
>>> http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108869
>>>
>>>
>>>  The maxor with all the unsigned casts is the call to the unsigned
>>> maxor.  Ditto for minor.
>>>
>>> Also, see my one liner for unsigned maxor:
>>>
>>> http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108916
>>>
>>>
>>>  All that is left is to find a quick (possibly one liner?) minor for
>>> unsigned.  Maybe there's a quicker signed solution, but the
>>> complexity is already O(1) * complexity of unsigned.
>>>
>>> Also, someone pointed out that Jerome's highbit is equivalent to the
>>> x86 bsr instruction (std.instrinsic.bsr).
>> That looks good. I'm thinking of expressing minOR for unsigned in terms
>> of maxOR for one's complement.
>>
>> We have min_a <= a <= max_a. This implies ~max_a <= ~a <= ~min_a.
>>
>> Wavehanding follows.
>>
>> We're looking for the numbers a and b that minimize the number of bits
>> in a|b. Those choices for a and b would then maximize the number of bits
>> in ~a|~b. So:
>>
>> minOR == maxOR(~max_a, ~min_a, ~max_b, ~min_b)
>>
>> Works?
>>
> 	Assuming you meant:
> 
> minOR == ~maxOR(~max_a, ~min_a, ~max_b, ~min_b)
> 
> 	Then that was my first idea too but it is *very* conservative. In
> my tests it only gave the best result for 0.1% of the time. So we'll
> have to do it the hard way:
> 
> ==============================8<------------------------------
> uint32_t minOr (uint32_t minA, uint32_t minB,
>                 uint32_t maxA, uint32_t maxB)
> {
>    assert (minA <= maxA);
>    assert (minB <= maxB);
> 
>    if (minA == 0) return minB;
>    if (minB == 0) return minA;
> 
>    uint32_t a = maxA ^ minA;
>    if (a != 0) {
>       a = ((1 << (highbit (a)+1)) - 1) & ~minA & minB;
>       if (a != 0)
>          a = (1 << highbit (a)) - 1;
>    }
>    a = minA & ~a;
> 
>    uint32_t b = maxB ^ minB;
>    if (b != 0) {
>       b = ((1 << (highbit (b)+1)) - 1) & ~minB & minA;
>       if (b != 0)
>          b = (1 << highbit (b)) - 1;
>    }
>    b = minB & ~b;
> 
>    return min (minA|b, a|minB);
> }
> ------------------------------>8==============================
> 
> 	The one-liner is left as an exercise to the readers (since it has
> the same performance anyway).
> 
> 		Jerome

I think your code looks a lot simpler if you define:

/// return the largest power of 2 such that floor2(x) <= x.
uint floor2(uint x)
{
     return x==0 ? x : (1 << bsr(x));
}

since what you're doing is stripping away all bits except the highest one.