On 04/10/2010 05:33 PM, Andrei Alexandrescu wrote:
[snip]
One more interesting detail. I simplified the routine to:
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;
}
Among other things I remove the test whether maxa >= maxb at the
beginning of the function. I now obtain:
total=100000000; equal=14585400 (14.5854%)
so this function is better than all others so far. But I don't
understand why it beats this one:
uint maxOR(uint maxa, uint maxb) {
if (maxa < maxb) return maxOR(maxb, maxa); // added
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;
}
Andrei
