Jérôme M. Berger wrote:
> OK, I found a solution that is optimal in over 99% of the cases
> (99.195% to be precise), while still being fast (because it avoids
> looping over the bits):
>
I've run my function and Andrei's on all possible min, max pairs in
0..299 without checking, just for the timing. On my computer (Athlon
X2 64 @2GHz), my function took 50s and Andrei's took 266s. The
difference should be even bigger for larger numbers.
Jerome
--
mailto:[email protected]
http://jeberger.free.fr
Jabber: [email protected]
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define N 300
// Comment the following line to get Andrei's implementation
#define MINE
// Comment the following line for exhaustive checking (slow! don't
// forget to reduce N)
#define BENCH
int highbit (uint32_t n)
{
assert (n != 0);
int result = 0;
if (n & 0xFFFF0000) {
result += 16;
n >>= 16;
}
if (n & 0xFF00) {
result += 8;
n >>= 8;
}
if (n & 0xF0) {
result += 4;
n >>= 4;
}
if (n & 0xC) {
result += 2;
n >>= 2;
}
if (n & 0x2) {
result += 1;
n >>= 1;
}
return result;
}
inline uint32_t min (uint32_t a, uint32_t b)
{
return (a<b) ? a : b;
}
#ifdef MINE
uint32_t maxOr (uint32_t minA, uint32_t minB,
uint32_t maxA, uint32_t maxB)
{
assert (minA <= maxA);
assert (minB <= maxB);
if (maxA == 0) return maxB;
if (maxB == 0) return maxA;
uint32_t a = maxA ^ minA;
if (a != 0)
a = ((1 << highbit (a)) - 1);
uint32_t b = maxB ^ minB;
if (b != 0)
b = ((1 << highbit (b)) - 1);
uint32_t t = maxA & maxB;
if (t != 0)
t = ((1 << highbit (t)) - 1);
return min (maxA|maxB|a|b, maxA|maxB|t);
}
#else // Andrei's
uint32_t maxOr (uint32_t, uint32_t, uint32_t maxa, uint32_t maxb)
{
uint32_t candidate = 0;
uint32_t mask = 1u << 31;
for (; mask; mask >>= 1) {
if (maxa & mask) continue;
uint32_t t = candidate | mask;
if (t <= maxb) candidate = t;
}
return maxa | candidate;
}
#endif
int main (int, char**)
{
int count = 0;
int countTight = 0;
for (uint32_t minA = 0; minA < N; ++minA)
for (uint32_t maxA = minA; maxA < N; ++maxA)
for (uint32_t minB = 0; minB < N; ++minB)
for (uint32_t maxB = minB; maxB < N; ++maxB)
{
bool reached = false;
uint32_t max = maxOr (minA, minB, maxA, maxB);
#ifdef BENCH
count += max;
#else // Check
for (uint32_t a = minA; a <= maxA; ++a)
for (uint32_t b = minB; b <= maxB; ++b) {
if ((a|b) > max) {
printf ("minA=%x\n"
"maxA=%x\n"
"minB=%x\n"
"maxB=%x\n"
"a=%x\n"
"b=%x\n"
"a|b=%x\n"
"maxOr=%x\n",
minA, maxA, minB, maxB,
a, b, a|b, max);
exit (1);
}
if ((a|b) == max) reached = true;
}
if (reached)
++countTight;
++count;
#endif
}
#ifdef BENCH
printf ("Result: %d (this number doesn't mean anything, it is only here\n"
"to make sure the compiler doesn't optimize everything away...\n",
count);
#else
printf ("Total: %d\n", count);
printf ("Tight: %d (%g%%)\n",
countTight, countTight * 100. / count);
printf ("Loose: %d (%g%%)\n",
(count - countTight),
(count - countTight) * 100. / count);
#endif
return 0;
}
signature.asc
Description: OpenPGP digital signature
