Максимальное XOR
6 мин
Здравствуй, Хабр. И сразу к делу.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L ≤ A ≤ B ≤ R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.
Задача:
Есть два целых числа: L и R. Нужно найти максимальное значение A xor B на промежутке [L; R], где L ≤ A ≤ B ≤ R.
Казалось бы ничего сложного. Сразу напрашивается решение простым перебором.
Развернуть
Сложность этого решения O(n2).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;
}
А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение xor на этом интервале? Моему ноутбуку потребовалось 1699914 миллисекунд.
Существует решение, которое работает значительно быстрее, именно о нем и пойдет речь в этой статье.
Привет всем. Я уже однажды писал про Distance Field и приводил реализацию «эвристическим» кодом, дающую неплохую скорость: 
Сказка ложь, да в ней намек…