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). If 'maxb' is
exactly 1 less than a power of 2, then 'candidate' will be 0. Now
consider a in [0, 16], b in [0, 15]. Your function will produce 16, but
the real maximum is 31.
For maximum accuracy, you have to consider the minima as well as the
maxima when calculating the new maximum. With 'a' in [16, 16] and 'b'
in [16, 16], the new range can only be [16, 16]. With 'a' in [0, 16]
and 'b' in [0, 16], the correct new range is [0, 31].
It's a very interesting puzzle. There are some pretty complex cases.
Consider (all numbers binary) a in [1010, 1100] and b in [101,101]. The
maximum value is when a=1011, b=101, so max is 1111.
