#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;
}