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

Здрастуй, Хабр. І відразу до справи.
Завдання:
Є два цілих числа: 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) = n2.
А що, якщо в інтервалі буде 1000000 чисел. Візьмемо L = 1, а R = 1000001. Скільки часу знадобиться середньостатистичному комп'ютера для того, щоб порахувати максимальне значення xor на цьому інтервалі? Моєму ноутбуку знадобилося 1699914 мілісекунд.
Існує рішення, яке працює значно швидше, саме про нього і піде мова в цій статті.
image

Основна ідея.
Щоб результуюче число було найбільшим, необхідно в якомога старшому біті цього числа отримати одиницю від функції xor. І так далі, у напрямку до наймолодшому біту. Іншими словами будемо послідовно працювати з кожним бітом результуючого числа за напрямком від старших до молодших бітів. Для цього дуже зручно використовувати структуру даних, яка називається trie-дерево (мені подобається ця структура даних, описана в книзі Р. Сейджвика «Алгоритми на Java»).

Trie-дерева являють собою структури даних, які складаються з вузлів, що містять посилання або нульові, або посилання на інші вузли. На кожен вузол вказує тільки один інший вузол (на кореневий вузол не вказує ні один вузол). Кожен вузол містить R посилань, де R — розмір алфавіту ( в нашому випадку R = 2, так як алфавіт це 0 та 1). Як правило, trie-дерева містять значну кількість нульових посилань, тому на картинках вони будуть опущені. Кожна посилання відповідає чергового біта числа. Кожне ціле число кодується як шлях від кореня до листка.

Приклад порожнього trie-дерева.
image
Так виглядає trie-дерево після додавання 0, 1, 2, 3, 4, 5, 6, 7.
image
На малюнку виділено шлях, що складається з 3 посилань 0 ->1->1( 011 це двійкове подання числа 3).

Відразу хочу пояснити, що ми будемо працювати тільки з 32-бітними числами, причому старші біти будуть заповнюватися нулями при необхідності. Цим ми добиваємося, що числа будуть зберігатися в масивах з однаковою довжиною. Двійкове подання цілих чисел я вирішив зберігати в масиві типу bool.
image
Кожен вузол зберігає масив посилань на інші вузли дерева ( 2 посилання, по одній для кожного можливого значення біта числа).
image
Взагалі trie-дерево — це структура даних, побудована із символів рядка ключів, яка дозволяє використовувати символи шуканого ключа для управління пошуком. Рядкові ключі можуть бути різної довжини, тому в кожному вузлі дерева додатково зберігають значення, яке може бути нульовим або реальним значенням, пов'язаним з одним з строкових ключів. У нашому ж випадку, нам не обов'язково зберігати значення, так як ключі є цілі 32-бітні числа, що зберігаються у двійковому вигляді в масивах однакової довжини. Отже, trie-дерево:
using System;
namespace MaxXor
{
public class Trie
{
//for integer representation in binary system 2^32
public static readonly int MaxLengthOfBits = 32;
//size of alphabet
public static readonly int N = 2;

class Node
{
public Node[] next = new Node[Trie.N];
}

private Node _root;
}
}


По-перше нам знадобляться функції перекладу чисел з десяткової в двійкову і навпаки. Тут все гранично зрозуміло і просто. Якщо потрібно освіжити пам'ять, то можете підглянути.

ConvertDecimalToBInary
private bool[] ConvertDecimalToBInary(int number)
{
int counter = Trie.MaxLengthOfBits;
bool[] result = new bool[counter];
while (number > 0)
{
result[--counter] = Convert.ToBoolean(number % 2);
number /= 2;
}

return result;
}


ConvertBinaryToDecimal
private int ConvertBinaryToDecimal(bool[] bits)
{
int result = 0;
int base_val = 1;
for (int i = bits.Length - 1; i >= 0; i--)
{
result += Convert.ToInt32(bits[i]) * base_val;
base_val *= 2;
}

return result;
}


По-друге нам знадобиться функція додавання цілого числа у trie-дерево. Тут зупинимося по-докладніше. Для вставки у trie-дерево спочатку потрібно виконати пошук потрібного сайту. Пошук починається з кореня, а потім по посиланню, пов'язаної з нульовим(старшим) бітом числа; від цього вузла проходить за посиланням, пов'язаної з першим бітом числа; звідти — по посиланню, пов'язаної з другим бітом числа; і т. д., тобто потрібно просто переглядати сайти по шляху від кореня до деякого вузла у trie-дереві. Біти числа використовуються для спуску по дереву до досягнення останнього біта або нульовий посилання. Якщо виявлена нульова посилання до вибірки останнього біта числа, тобто у trie-дереві немає вузла, відповідного останнього біта числа, то необхідно створювати сайти для кожного з відсутніх бітів.
public void AddValue(bool[] binaryNumber)
{
_root = AddValue(_root, binaryNumber, 0);
}

private Node AddValue(Node node, bool[] val, int d)
{
if (node == null) node = new Node();

//if least sagnificient bit has been added
//need return
if (d == val.Length)
{ 
return node;
}

// get 0 or 1 index of next array(length 2)
int index = Convert.ToInt32(val[d]); 
node.next[index] = AddValue(node.next[index], val, ++d);
return node;
}

Тепер побудуємо trie-дерево, додавши всі числа з заданого проміжку.
Переходимо до найголовнішого. Для пошуку максимального значення xor, будемо рухатися trie-дереву від кореня за посиланнями, тобто будемо працювати з битами по напрямку від старших до молодших. Причому ми можемо знаходиться в одному вузлі, так і в різних. При кожному проході будемо намагатися отримати одиницю, якщо це можливо, від xor-а чергових бітів числа, і так далі, поки не отримаємо всі 32 біта. Утворені 32 біта — це і є максимальне значення xor на нашому проміжку.
public bool[] GetMaxXor()
{
bool[] result = new bool[Trie.MaxLengthOfBits];
Node oneNode = _root, twoNode = _root;
//for each bit from most significant bit to least significant bit
for (int i = 0; i < Trie.MaxLengthOfBits; i++)
{
//getting current bit
result[i] = GetBit(oneNode, twoNode);
//go to next nodes
UpdateNodes(ref oneNode, ref twoNode);
}

return result;
}
//we need update nodes after each iteration
//we can stay on single or node split on two nodes
private void UpdateNodes(ref Node one, ref Node two)
{
if (one.Equals(two))
{
if (one.next[1] != null && one.next[0] != null)
{
two = one.next[1];
one = one.next[0];
}
else
{
one = two = ((one.next[1] != null) ? one.next[1] : one.next[0]);
}
}
else
{
if (one.next[1] != null && two.next[0] != null)
{
one = one.next[1];
two = two.next[0];
}
else if (one.next[0] != null && one.next[1] == null)
{
one = one.next[0];
two = two.next[1];
}
else
{
one = one.next[1] ?? one.next[0];
two = two.next[1] ?? two.next[0];
}
}
}

//if it's possible, we will try to get one.
private bool GetBit(Node one, Node two)
{
if (one.Equals(two))
{
// 0 xor 1 == 1; 1 xor 0 == 1
if (one.next[0] != null && one.next[1] != null) return true;
// 0 xor 0 == 0; 1 xor 1 == 0
else return false; 
}
else
{
if ((one.next[1] != null && two.next[0] != null)|| // 1 xor 0 == 1
(one.next[0] != null && one.next[1] == null) // 0 xor 1 == 1
{
return true;
}
else
{// 0 xor 0 == 0; 1 xor 1 == 0
return false;
}
}
}

Приклад для 3-бітних чисел
image

Тепер, можна порівняти час роботи кожного з підходів для проміжків різної довжини.

image
Як видно з таблиці обчислення максимального значення xor з допомогою trie-дерева працює значно швидше. Оцінка складності алгоритму O(n) = nlogn.

Архів з солюшеном проекту можна завантажити тут.

P. S. Для вирішення даної задачі, та й взагалі для зберігання цілих чисел в двійковому вигляді можна злегка спростити наше trie-дерево. Так як алфавіт складається всього з 2 символів, можна позбутися від масиву і зберігати просто два посилання, наприклад, Node left Node right, які є представленням 0 і 1 відповідно.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.