Макс XOR двух элементов в массиве

Question

Я искал какой-нибудь эффективный алгоритм для вычисления максимального значения xor, которое вы можете получить, ксероксируя любые два значения массива.например, если i и j являются индексами массива, чем вы должны максимизировать (Ai xor Aj) ... Я нашел два эффективных подхода, один из которых использует попытки и один алгоритм, который я нашел на LeetCode, который обещает результаты в O (nlog (U)) U - количество бит в элементах массива.Этот алгоритм работает правильно. Однако у меня возникают проблемы с пониманием того, почему и как он работает.

Вот фрагмент кода

int findMaximumXOR(vector<int>& nums) {
    int mask = 0;
    int test_max = 0;
    int max = 0;
    unordered_set<int> s;
    for(long long i = 30; i >= 0; --i){
        mask |= 1ll << i;

        printf("\n"BYTE_TO_BINARY_PATTERN, BYTE_TO_BINARY(mask));

        for(int num : nums){
            s.insert(num & mask);
        }

        test_max = max | 1 << i;
        for(int s_val : s){
            if(s.find(s_val ^ test_max) != s.end()){
                max = test_max;
                break;
            }
        }
        s.clear();
    }
    return max;
}

** Уже существует вопрос о переполнении стека.с тем же названием, но они обсуждали только попытки

Answer 1

Функция вычисляет максимальное число, представленное XOR (a, b).Чтобы вычислить это, он идет от старшего к младшему.На первой итерации проверяется, есть ли числа, которые отличаются по старшему значащему биту.После каждой итерации он сохраняет максимальное XOR префикса между двумя числами и затем проверяет, есть ли два числа, которые имеют это расстояние и также отличаются следующим битом.s - это набор префиксов чисел, test_max - это максимальный XOR префиксов.этот раздел:

test_max = max | 1 << i;
for(int s_val : s){
    if(s.find(s_val ^ test_max) != s.end()){
        max = test_max;
        break;
    }
}

пытается увеличить префикс на один бит, проверяя, есть ли два числа, которые сохраняют максимальный префикс XOR и также отличаются на следующий бит.РЕДАКТИРОВАТЬ: Как я понимаю из кода, максимальный XOR составляет максимум (int)(a[i]^a[j]).