Невозможно понять логику `XOR` при поиске пропущенного значения в массиве - PullRequest
Новая
       34

Невозможно понять логику `XOR` при поиске пропущенного значения в массиве

0 голосов
/ 11 мая 2018

Вот пример кода, который я получил от здесь . 

public class Snippet {
    private static final int[] ARRAY = {1, 4, 3, 18, 2, 8, 9, 6, 5, 10,
            11, 12, 13, 14, 15, 16, 17, 19, 0, 20};

    //{1,2,4,5,6,8,7,9,3}
    private int getMissingElem() {
        int XOR = 0;
        for (int i = 0; i < 20; i++) {
            if (ARRAY[i] != 0) {
                XOR ^= ARRAY[i];
            }
            XOR ^= (i + 1);
        }
        return XOR;
    }

    public static void main(String[] args) {
        Snippet s = new Snippet();
        System.out.println(s.getMissingElem());
    }
}

Я только что узнал о том, как XOR имеют значения отсутствующих элементов массива.

1 Ответ

0 голосов

XOR равно по битам . Это означает, что, учитывая два целочисленных значения a, b, a ^ b имеет бит 1 в этой позиции тогда и только тогда, когда либо эта позиция a, либо b равна 1, но не оба.

Значение 15 будет побитовым (здесь для простоты 8 битов) представлено как 00001111, тогда как значение 60 будет побитовым представлением как 00111100. Обратите внимание, что 15 ^ 60 будет равно 00110011, поскольку биты 2-3 равны 1 только для 15, а биты 6-7 равны 0 только для 60.

На ваш вопрос, касающийся поиска отсутствующего элемента массива , он работает только в том случае, если массив иначе содержит целые числа от 1 до ARRAY.length, за исключением того, что одно целое число равно 0 (предварительное условие).

  • Обратите внимание, что XOR коммутативен и ассоциативен. Это означает, a ^ b == b ^ a и (a ^ b) ^ c == a ^ (b ^ c) == a ^ b ^ c)
  • для всех a, b, c. Кроме того, если вы XOR один и тот же номер дважды, он отменяет out, и результатом становится 0. Дано любое число n, n ^ n == 0, а также a ^ n ^ n == a.
  • Для всех a, a ^ 0 == a, поскольку, если этот бит a равен 1, ровно один бит в этой позиции равен 1.

Логика, лежащая в основе вашего решения на основе XOR, заключается в том, что для всех чисел, включенных в этот массив, вы выполняли XOR для того же числа дважды, что отменяет. Единственным исключением является пропущенное число n, так как 0 ^ n равно n.

Предположим, ARRAY - это массив, который удовлетворяет условию:

  • Случай 1: число m появляется в массиве. Условие (*) для выполнения этого XOR - это когда петля находится в i -ом положении, таком как ARRAY[i] == m, или в m - 1 -ом положении. У нас есть XOR ^ m, когда условие выполняется в первый раз. По мере выполнения цикла снова выполняется то же условие, поэтому мы имеем XOR ^ m ^ k ^ m == XOR ^ (m ^ m) ^ k == XOR ^ k, где k - результат XORing числа между первым и вторым индексами, где выполняется условие.

  • Случай 2: число n отсутствует в массиве. Обратите внимание, что предыдущее условие (*) выполняется только один раз, пока вы выполняете цикл. Поэтому у нас есть XOR ^ n.

  • Поскольку XOR является коммутативным и ассоциативным, мы в конечном итоге получаем окончательный результат XOR == a^a^b^b^...^n...^x^x^y^y. Обратите внимание, что все числа за исключением того, что n дважды XORed по окончании цикла, у нас есть (a^a)^(b^b)^...^n^(x^x)^(y^y) == 0^0^...^n^...0^0, следовательно, мы получили n, как нужно.

...