Несколько дней назад я решил KATA (проблема программирования) на веб -сайте Codewar, когда я закончил, я проверил другие найденные решения. Я увидел решение, которое привлекло мое внимание, это решение использует операцию XOR. Вы можете легко понять логику оператора XOR (таблица истины), но цель состоит в том, чтобы понять, почему XOR решает проблему. Поэтому я провел некоторое исследование и постараюсь объяснить вам мое понимание.
Ката проблема
Итак, проблема программирования была:
Учитывая массив, найдите Int, который появляется нечетное количество раз.
Всегда будет только одно целое число, которое появляется нечетное количество раз.
Так что, если у вас есть список, например: [2, 3, 2, 4, 4] 3 – хороший ответ. 2 и 4 повторяются 2 раза (даже) и 3 всего 1> (нечетно)
Постарайтесь решить эту проблему, если хотите. Я сделал это с JavaScript и петлей Foreach. Я оставлю вам свое решение в конце этого поста. Решение, данное другими пользователями,:
const findOdd = (xs) => xs.reduce((a, b) => a ^ b); // this is arrow function
Они используют функцию уменьшения для итерации в списке «XS» и ^ (оператор XOR в JavaScript).
Понять
Итак, прежде всего, вам нужно понять 3 вещи:
^ Операция XOR
1. Таблица истины
0 ^ 0 ^ 1 ^ 1 ^
(Это полезно для понимания свойств ниже)
2. Характеристики:
Заглавные буквы как или B или X являются результатом операции XOR.
A ^ A ^
[A] может быть случайным числом, например, 10 ^ или 3 ^
(PS: Нам не нужны другие свойства, чтобы понять следующие части)
3. Ассоциативность:
a ^ b ^ ^ c ^ b или даже a ^ b ^ c ^ ^ c ^ d ^ b
Таким образом, это означает, что приоритетный порядок операций может быть изменен.
Это не обязательно начинать с операции ^ B, мы можем начать с ^ C, если вы хотите.
Подать заявление
Хорошо, теперь посмотрим, как применить XOR в этом случае.
Возьмите этот список в качестве примера
const array = [10, 3, 20, 10, 3, 20, 10]
Здесь 10 – это число, которое повторяется нечетное время (3). Это хороший ответ. Уменьшение – это особая функция для JavaScript. По сути, эта функция отражает каждый элемент списка слева направо и возвращает результат данной операции между предыдущим и текущим элементом итерации.
Таким образом, в нашей проблеме/примере элемент списка – это число, а данная операция – операция XOR a ^ беременный A будет предыдущим результатом, а B – количество текущей итерации.
Это решение будет повторять так:
10 ^ (результат 9, но нам не нужно знать реальные результаты, поэтому мы называем это а) A ^ это то же самое, что 10 ^ 3 ^ 20 так ^ 3 ^ 20 .. и так на
10 ^ 3 ^ 20 ^ 10. В этот момент мы можем использовать ассоциативность,
Чтобы изменить порядок операций PRIO. Итак, мы можем написать 10 ^ 10 ^ 3 ^ 20, теперь используйте свойства (a ^) Итак, 10 ^ … тогда 0 ^ 3 ^ 20. Снова используйте свойство (A ^) .. так 0 ^ 3 ^ ^ 20. 3 ^ 20 ^ 3 .. Снова используйте ассоциативность и свойства, результат
Вот 20 20 ^, затем последняя итерация
0 ^! ПОТРЯСАЮЩИЕ !
Вывод
Как видите, поведение заключается в том, что, если в то время мы встречаемся/встречаем число, которое уже было в предыдущих операциях XOR .. например: [a] ^ b ^ c ^ [A] Повторное число [A] каким -то образом отменяется или удалено. Пошаговый номер дубликата будет снят шаг за шагом, поэтому в конце число/результат будет номером, который появился только один раз)
Вот почему операция XOR может решить такую проблему.
Спасибо за чтение 😌!
Ниже я оставляю вам свое решение (черновик), я знаю, я не уважаю чистый код здесь 🤷 ♂ ️
function findOdd(A) {
const occurencesTable = [];
A.forEach(number => {
const exist = occurencesTable.find(occurence => {
return occurence[0] === number;
});
if (!exist) {
occurencesTable.push([number, 1]);
} else {
exist[1] = exist[1] + 1;
}
});
const odd = occurencesTable.find(occurence => {
return (occurence[1] % 2 !== 0)
});
return odd[0];
}
Оригинал: “https://dev.to/bladesensei/xor-operator-in-programming-use-case-34ng”