value range propagation for _bitwise_ OR

["Jérôme M. Berger"]

Don wrote:
> 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.

	Actually, most times I'm creating a number with all 1s until the
highest bit, which is sometimes set and sometimes not (twice of each
for minOr, always unset for maxOr)... Your floor2 could be used for
maxOr, but only for two out of four cases in minOr.

		Jerome
-- 
mailto:jeberger at free.fr
http://jeberger.free.fr
Jabber: jeberger at jabber.fr

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100419/89dc58f5/attachment.pgp>