value range propagation for _bitwise_ OR

[Andrei Alexandrescu]

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?


Andrei