value range propagation for _bitwise_ OR

Steven Schveighoffer schveiguy at yahoo.com
Mon Apr 19 11:34:01 PDT 2010


On Sat, 17 Apr 2010 01:55:26 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> 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?

No, I think you want to maximize the value of ~a & ~b (you have to swap  
the operation too!).

But I think there is a shortcut.  In maxor, I basically searched for the  
highest bit that is set in both maxes, and unset in one or both mins.   
When you find this bit, then the max in which that bit is optional is set  
to 0, and the rest of the value can be 1s.

I think a similar strategy can be used in min.  Essentially, you want to  
find the highest bit for which one of the values *must* have it set (that  
is (min ^ max) & bit == 0 and max & bit != 0), and for which the other  
value has it as optional.  In that case, you set the optional bit to a 1,  
and the rest can be all 0s.  Then you or in the min of the other value.

In my original solution, the loop searched for that first bit, and once it  
was found, it returned immediately with the shortcut.

I think a one-liner is more difficult for minor because you can't just  
'or' both mins together assuming it will not hurt as you can in the max  
version (The minimum max value is maxa | maxb, but the minimum min value  
is not mina | minb).  The strategy for finding the target bit can be done  
in one line.

It might be 2 one-liners in which you just take the min of the results.

-Steve



More information about the Digitalmars-d mailing list