Алгоритм единственного числа

Использование побитового оператора XOR

Поиск единственного числа в массиве - обычная задача в алгоритмах. Давайте посмотрим, как это сделать.

Для непустого массива целых чисел каждый элемент появляется дважды, кроме одного. Найдите ту единственную.

Пример:

Input: [2,2,1]
Output: 1

Решение:

const singleNumber = function(nums) {
return nums.reduce((accumulator, value)=>accumulator^value)
}

Почему и как?

Разберем предлагаемое решение.

Мы используем функцию уменьшения и возвращаем аккумулятор по сравнению с каждым элементом в массиве.

По сравнению?… Верно, этот маленький знак ^ известен как побитовый оператор «Исключающее ИЛИ».

Итак, поговорим о «побитовых операторах».

Таким же образом в логических операторах сравниваются примитивные значения, побитовые операторы используются для сравнения, но по-другому.

По документации:

Поразрядные операторы обрабатывают свои операнды как последовательность из 32 бит (нулей и единиц), а не как десятичную, шестнадцатеричную или восьмеричную numbers.

Это означает, что каждый операнд преобразуется в 32-битное целое число, которое выражается как последовательность битов. Вы ведь помните двоичную систему?

Позвольте мне показать вам пример:

decimal system: 2 
32 bits system : 00000000 00000000 00000000 00000010

Теперь, когда мы используем побитовые операторы, каждый операнд сопряжен с соответствующим битом другого операнда. Таким образом, сравнение выполняется бит с битом.

Помимо логических операторов, наиболее распространенными побитовыми операторами являются И (&) ИЛИ (|) ИСКЛЮЧАЮЩЕЕ ИЛИ (^). Верно только один & или | или ^ Конечно, у каждого побитового оператора есть своя собственная таблица истинности.

Побитовое И a & b Возвращает 1 в каждой битовой позиции, для которой соответствующие биты обоих операндов равны 1.

                       ╔═══╦═══╦═════════╗
                       ║ a ║ b ║ a AND b ║
                       ╠═══╬═══╬═════════╣
                       ║ 0 ║ 0 ║    0    ║
                       ║ 1 ║ 0 ║    0    ║
                       ║ 0 ║ 1 ║    0    ║
                       ║ 1 ║ 1 ║    1    ║
                       ╚═══╩═══╩═════════╝

Пример:

>> 1 & 2
1 -> 0001
2 -> 0010
R -> 0000
Decimal: 0

Побитовое ИЛИ a | b Возвращает 1 в каждой битовой позиции, для которой соответствующие биты одного или обоих операндов равны 1s.

                       ╔═══╦═══╦═════════╗
                       ║ a ║ b ║ a OR b  ║
                       ╠═══╬═══╬═════════╣
                       ║ 0 ║ 0 ║    0    ║
                       ║ 1 ║ 0 ║    1    ║
                       ║ 0 ║ 1 ║    1    ║
                       ║ 1 ║ 1 ║    1    ║
                       ╚═══╩═══╩═════════╝

Пример:

>> 1 | 2
1 -> 0001
2 -> 0010
R -> 0011
Decimal -> 3

Побитовое исключающее ИЛИ a ^ b Возвращает 1 в каждой битовой позиции, для которой соответствующие биты одного, но не обоих операндов равны 1s.

                       ╔═══╦═══╦═════════╗
                       ║ a ║ b ║ a XOR b ║
                       ╠═══╬═══╬═════════╣
                       ║ 0 ║ 0 ║    0    ║
                       ║ 1 ║ 0 ║    1    ║
                       ║ 0 ║ 1 ║    1    ║
                       ║ 1 ║ 1 ║    0    ║
                       ╚═══╩═══╩═════════╝

Пример

>> 1 ^ 2
1 -> 0001
2 -> 0010
R -> 0011
Decimal -> 3

Как видите, побитовые операторы выполняют свои операции в двоичном представлении, но возвращают стандартные числовые значения JavaScript.

А теперь вернемся к нашей проблеме. Используя оператор XOR, мы можем исключить те значения, которые равны.

Input: [2,2,1]
First time: 2 XOR 2 
2 -> 0010
2 -> 0010
R -> 0000
Now our accumulator has 0 as value.
Second time: 0 XOR 1
0 -> 0000
1 -> 0001
R -> 0001 
Now our accumulator has 1 and return that value

Хорошо, это было легко, давай попробуем другой случай.

Input: [4,1,2,1,2]
First time 4 XOR 1
4 -> 0100
1 -> 0001
R -> 0101   ----->  Now our accumulator has 5 as value.
Second time: 5 XOR 2
5 -> 0101
2 -> 0010
R -> 0111  ----->  Now our accumulator has 7 as value.
Third time: 7 XOR 1 
7 -> 0111
1 -> 0001
R -> 0110  ----->  Now our accumulator has 6 as value.
Fourth time: 6 XOR 2
6 -> 0110
2 -> 0010
R -> 0100  ----->  Now our accumulator has 4 as value.

Return 4

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

Продолжайте кодировать!