value range propagation for _bitwise_ OR

[Andrei Alexandrescu]

On 04/10/2010 04:50 PM, "Jérôme M. Berger" wrote:
> Andrei Alexandrescu wrote:
>> On 04/10/2010 01:55 PM, Rainer Deyke wrote:
>>> On 4/10/2010 11:52, Andrei Alexandrescu wrote:
>>>> I think this would work:
>>>>
>>>> uint maxOR(uint maxa, uint maxb) {
>>>>       if (maxa<   maxb) return maxOR(maxb, maxa);
>>>>       uint candidate = 0;
>>>>       foreach (i, bit; byBitDescending(maxa)) {
>>>>           if (bit) continue;
>>>>           auto t = candidate | (1<<   (31 - i));
>>>>           if (t<= maxb) candidate = t;
>>>>       }
>>>>       return maxa | candidate;
>>>> }
>>>
>>> This looks wrong.  Your function, if I understand it correctly, flips
>>> all the bits in 'maxb' (excluding the leading zeros).
>>
>> It tries to set all bits in which maxa is zero starting and keeps them
>> set if the resulting number is less than maxb.
>>
> 	In other words: maxa | ((1<<  highbit (maxb))-1) where:
>
> int highbit (uint n) {
>     auto result = 0;
>     if (n&  0xFFFF0000) {
>        result += 16;
>        n = n>>  16;
>     }
>     if (n&  0xFF00) {
>        result += 8;
>        n = n>>  8;
>     }
>     if (n&  0xF0) {
>        result += 4;
>        n = n>>  4;
>     }
>     if (n&  0xC) {
>        result += 2;
>        n = n>>  2;
>     }
>     if (n&  0x2) {
>        result += 1;
>        n = n>>  1;
>     }
>     if (n&  0x1) {
>        result += 1;
>     }
>     return result;
> }
>
> 		Jerome

Interesting. I don't get how your version is equivalent to mine, and I 
don't get how it actually works, but it seems to. Could you please explain?

The program below compiles, runs, and prints

total=100000000; equal=3850865 (3.85087%)

Here it is:

import std.contracts, std.stdio;

uint maxOR(uint maxa, uint maxb) {
     return maxa | ((1 << highbit (maxb))-1);
}

uint highbit(uint n) {
    auto result = 0;
    if (n & 0xFFFF0000) {
       result += 16;
       n = n >> 16;
    }
    if (n & 0xFF00) {
       result += 8;
       n = n >> 8;
    }
    if (n & 0xF0) {
       result += 4;
       n = n >> 4;
    }
    if (n & 0xC) {
       result += 2;
       n = n >> 2;
    }
    if (n & 0x2) {
       result += 1;
       n = n >> 1;
    }
    if (n & 0x1) {
       result += 1;
    }
    return result;
}

void main() {
     ulong total, equal;
     uint N = 10000;
     foreach (a; 0 .. N) {
         foreach (b; 0 .. N) {
             auto c = maxOR(a, b);
             enforce((a|b) <= c);
             if ((a|b) == c) equal++;
             total++;
         }
     }
     writeln("total=", total, "; equal=", equal,
             " (", equal * 100. / total, "%)");
}

However, your method is not the tightest; seems like mine is tighter. 
When I replaced maxOR with this:

uint maxOR2(uint maxa, uint maxb) {
     if (maxa < maxb) return maxOR(maxb, maxa);
     uint candidate = 0;
     uint mask = 1u << 31;
     for (uint i = 0; i < 32; ++i, mask >>= 1) {
         if (maxa & mask) continue;
         auto t = candidate | (1 << (31 - i));
         if (t <= maxb) candidate = t;
     }
     return maxa | candidate;
}

I got:

total=100000000; equal=9822516 (9.82252%)

Besides, I verified that my method returns numbers <= yours.


Andrei