Максимальное XOR

Среда, 17 Декабря 2014 г. 17:42 + в цитатник

Здравствуй, Хабр. И сразу к делу.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L <= A <= B <= R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.

Развернуть

public int BruteForce(int one, int two)
{
   int maxXor = 0;
   while (one < two)
   {
      int oneTemp = one + 1;
      while (oneTemp <= two)
      {
         int curXor = one ^ oneTemp;
         if (maxXor < curXor) maxXor = curXor;
         oneTemp++;
      }
      one++;
   }

   return maxXor;
}

Сложность этого решения O(n²).
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.