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
