value range propagation for _bitwise_ OR

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Sat Apr 10 15:46:15 PDT 2010


On 04/10/2010 05:43 PM, Andrei Alexandrescu wrote:
> On 04/10/2010 05:33 PM, Andrei Alexandrescu wrote:
> [snip]
>
> One more interesting detail.

Never mind that. I mistakenly used maxOR instead of maxOR2.

To summarize: best result is

total=100000000; equal=14585400 (14.5854%)

with the function:

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

Inserting a test and a recursive call at the top keeps the result but 
actually slows down execution a bit.


Andrei



More information about the Digitalmars-d mailing list