Здравствуй, Хабр. И сразу к делу. Задача: _Есть два целых числа: **L** и **R**. Нужно найти максимальное значение **A** [xor][1] **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) = n. А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд. Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье. ![image][2] [Читать дальше →][3]

[1]: http://en.wikipedia.org/wiki/Exclusive_or
[2]: http://habrastorage.org/files/8c1/1c9/dde/8c11c9dde9b94df598c4ddd300a34ca7.png
[3]: http://habrahabr.ru/post/245801/#habracut