Максимальное 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(n2).
    А что, если в интервале будет 1000000 чисел. Возьмем L = 1, а R = 1000001. Сколько времени понадобится cреднестатистическому компьютеру для того, чтобы посчитать максимальное значение 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-дерево, добавив все числа из заданного промежутка.

    Update: Как верно первым подметил freopen,
    достаточно найти самый первый бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами
    Итак, найдем самый первый бит, который различается, для этого будем двигаться от корня по ссылкам, пока не встретим узел, у которого существуют обе ссылки. Затем все биты ниже сделаем единицами. В итоге получим результат.
    public bool[] GetMaxXor()
    {
    	bool[] result = new bool[Trie.MaxLengthOfBits];
        Node cur = _root;
        //find index the most significant bit, which is different
        int index;
        for (index = 0; index < Trie.MaxLengthOfBits; index++)
        {
    		//are bits differ?
            if (cur.next[0] != null && cur.next[1] != null)
            {   //the most significant bit, which is different
    			result[index] = true;
                break;
            }
            //descent down the tree
            cur = cur.next[0] ?? cur.next[1];
        }
        //all the bits below do 1
        while (index < Trie.MaxLengthOfBits)
        {
    		result[index] = true;
            index++;
        }
    
        return result;
    }
    

    Существенное упрощение кода, но сложность остается прежней! Архив с обновленным солюшеном проекта можно скачать здесь.

    Старая версия

    Переходим к самому главному. Для поиска максимального значения 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 node or 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(nlogn).

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

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 38

      +2
      > Есть два целых числа
      > в как можно старшем бите этого числа получить единицу

      Сразу неправильно, если смотреть формально на задание ;)
        +3
        Хорошо бы пару примеров, где это можно использовать. А то какой-то балласт знаний получается, если дополнительно не разбираться в проблеме. На SO есть кучка решений и идей, но нет полноценного сравнения и ремарки по поводу применения.
          +2
          Сама задача взята отсюда. Было свободное время, хотелось поломать голову и познакомится с чем-нибудь новым. Так появился этот код и статья )
            0
            хотелось поломать голову и познакомится с чем-нибудь новым

            Заходите на http://codeforces.ru/problemset, там есть задачки интереснее и сложнее.
          +25
          Ээм… А чего так сложно?

          Берем L и R, находим у них самый старший бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами, т.к. если у нас L вида xy...z0..., а R вида xy...z1..., то очевидно, что в промежутке есть числа xy...z011...1 и xy...z100...0.
            +6
            «Паттернов начитался»
              –4
              получается, можно хранить в trie старший бит, который различается и обновлять его при вставке очередного целого числа, а затем делать все биты ниже единицами. Правда сложность все равно будет O(n) = nlogn, но гораздо проще ).
                +5
                Шта???

                Давайте я код напишу, чтобы было понятно: ideone.com/Po4JgL. У того, что я описал сложность — O(log n).

                O(n) не равно nlogn
                  +1
                  O(n) = nlogn

                  Видимо автор всего лишь таким образом записывает фразу «Сложность алгоритма равна nlogn»
                    0
                    Да, вы абсолютно правильно поняли смысл моей записи. Теперь буду писать правильно )
                    0
                    Определенно ваше решение проще, да вдобавок еще и быстрее.
                      +2
                      Циклы явно лишние ideone.com/qKUwEk
                        0
                        Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)
                          0
                          А чем его заменить? scanf? Это шило на мыло получится. А __builtin_clz на некоторых (x86) платформах разворачивается в одну инструкцию, что магическим образом превращает O(log(n)) в O(1);
                            0
                            Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
                            getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.
                            digital-madness.in/blog/2013/fast-io-in-c/
                              0
                              Мы же число вводим, а не символ. Нам строку потом переводить в число придётся.
                                0
                                Дело в том, что высокоуровневые cin и scanf очень медленные по сравнению с getchar_unlocked. Для преобразования входного потока в число можно использовать функцию:

                                inline int read_int() 
                                {
                                    register int c = getchar_unlocked();
                                    int x = 0;
                                    int neg = 0;
                                
                                    if(c=='-') 
                                    {
                                        neg = 1;
                                        c = getchar_unlocked();
                                    }
                                
                                    for(; '0'<=c && c<='9' ; c = getchar_unlocked()) {
                                        x = (x<<1) + (x<<3) + c - '0';
                                    }
                                
                                    return neg ? -x : x;
                                }
                                
                                  +1
                                  Всё это я видел на stackoverflow, хоть источник бы указывали. Но код должен быть не только производительным, но и выразительным (иногда это даже важнее). Зачем писать по 10 утилитарных функций, зачем в цикле считать биты? Язык предоставляет для всего этого удобные, безопасные инструменты, и не стоит игнорировать их. Я там ещё и bitset использую для красивого вывода в cout. Если всё это писать самому, то решение задачки в 1 строчку превратится в очередной фреймворк. Ведь код я не усложнял, я его значительно упростил. 5 — 6 битовых операций это не так сложно.
                                    –1
                                    Источник указан в комментарии выше, читайте внимательней.
                                    • Про выразительность: выразительность это несомненно важно, но в угоду выразительности жертвовать производительность там, где важна производительность все же не стоит. Речь шла именно о производительности
                                      Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin

                                    • Про циклы:
                                      зачем в цикле считать биты
                                      Любое число — совокупность бит. В угоду производительности, там где это оправданно, а в этом случае это оправданно — можно и биты посчитать. К тому же решение весьма простое и абстракция в виде функции несомненно проста в использовании и потому эффективна.
                                    • и не стоит игнорировать их
                                      Тезис верный, но не стоит принимать его за аксиому. Всему свое место и там где уместно использование готовых функций конечно же не стоит городить велосипеды.
                                    • 5 — 6 битовых операций это не так сложно
                                      не понимаю тогда чем решение, предложенное мной, сложно.
                    0
                    Я бы сказал — ксорим максимальное возможное число с нулем и получаем искомое.
                      0
                      A должно быть больше или равно L.
                        +2
                        L не равно нулю в общем случае. Но даже для L=0 это неверно. Пусть R=4, тогда оптимальные a и b — это 3 и 4: 3^4 = 7.
                          +1
                          Xor с нулём бессмысленен. Вы получаете тоже самое число.
                            0
                            да затупил. спасибо всем.
                        –2
                        И я тут подумал — а на что он декартово всунул, когда это декартово можно хранить неявно.

                        Итак, моё решение. i-й бит перекрывает все биты от 0 до i−1. Потому если удастся i-й бит сделать единицей, его СТОИТ делать единицей, чхая на то, что все низшие будут нулями.

                        результат := 0
                        текБит := максБит()
                        пока текБит ≠ 0
                          новРез := результат + текБит
                          если новРез <= Б
                            то результат := новРез
                          текБит >>= 1
                        


                        Скорость — кол-во битов в слове.
                          +2
                          Все-таки стоило прочитать статью перед написанием этого комментария…
                            0
                            Да, верно, я решил не ту задачу. Не сразу заметил и переписал.
                            0
                            Пардон, ошибся, решив не ту задачу.

                            результатА := 0
                            текБит := максБит()
                            пока текБит ≠ 0
                              новРезБ := результатА + текБит
                              новРезА := результатА + текБит − 1
                              если новРезБ > R то 
                                ничего не делать
                              иначе если новРезА < L то
                                результатА := новРезБ
                              иначе
                                результатА := новРезА
                                результатБ := новРезБ
                                стоп
                              текБит >>= 1
                            результатБ := результатА // перестраховка
                            
                            +1
                            int maxxor(int a,int b){
                            	int c=a^b;
                            	if(c<0) c=max(~a,b);
                            	while(c&(c+1)) c|=c>>1;
                            	return c;
                            }
                            


                            Проверил для a,b между -30 и 30 — совпадает с переборным решением.

                            Или я чего-то не понял в задаче?
                              +2
                              если на то пошло, то вот
                              unsigned int maxxor(unsigned int L, unsigned int R) {
                                  unsigned int c = L^R;
                                  c |= c >> 1;
                                  c |= c >> 2;
                                  c |= c >> 4;
                                  c |= c >> 8;
                                  c |= c >> 16;
                                  return c;
                              }
                              

                              11 операций для 32-битных L и R.
                                0
                                Добавьте небольшое пояснение вашего подхода.
                                  +1
                                  Пусть с(i) — i-й бит числа с
                                  тогда, если с(i)=1, то после операции: c = c | (c >> 1)
                                  c(i) = c(i-1) = 1
                                  теперь можно смело сдвинуть с еще на 2 бита вправо: c = c | (c >> 2)
                                  c(i) = c(i-1) = c(i-2) = c(i-3) = 1
                                  и т.д.

                                  например:
                                  001000000100 =>
                                  001100000110 =>
                                  001111000111 =>
                                  001111111111
                                    0
                                    Спасибо за разбор.
                                  +1
                                  Я так писать не стал, потому что, во-первых, используется конкретная разрядность, а во-вторых — 7 строчек вместо трёх.

                                      for(k=1;c&(c+1);k<<=1) c|=c>>k;
                                  
                                    +1
                                    Тогда для знаковых 32-битных L и R, L <= R так:
                                    int maxxor(int L,int R){
                                        int c=L^R;
                                        int d=~L|R;
                                        c=(c|(c>>31))&(d|(d>>31));
                                        c|=c>>1;
                                        c|=c>>2;
                                        c|=c>>4;
                                        c|=c>>8;
                                        return c|(c>>16);
                                    }
                                    

                                    18 операций, не считая копирований.
                                  0
                                  Вот мое решение:

                                  int maxXor(int l, int r) {
                                      unsigned q = l ^ r;
                                      int t = 0;
                                      while(q >> 1) {
                                          t++;
                                          q>>=1;
                                      }
                                      // заполняем все единичками. 2^(t-1) - 1
                                      return (1u<<(t+1)) - 1;
                                  }
                                  


                                  Находим самый старший бит который различается. Начиная с него и до самого младшего бита всегда можно сделать единички после xor.

                                    0
                                    И что она сделает при l = -2, r = 2? Зациклится?
                                    0
                                    Интереснее задача найти максимум и минимум для A&B, где L1 <= A <= R1, L2 <= B <= R2.

                                    Only users with full accounts can post comments. Log in, please.