Почему результаты битового XOR (^) в данном примере отличаются? Что такое лог c? JS - PullRequest
Новая
       47

Почему результаты битового XOR (^) в данном примере отличаются? Что такое лог c? JS

2 голосов
/ 22 апреля 2020

Дан непустой массив A, состоящий из N целых чисел. Массив содержит нечетное количество элементов, и каждый элемент массива может быть связан с другим элементом, имеющим такое же значение, за исключением одного элемента, который остается непарным.

Например, в массиве A такой, что : 

A[0] = 9  A[1] = 3  A[2] = 9
A[3] = 3  A[4] = 9  A[5] = 7
A[6] = 9

элементы в индексах 0 и 2 имеют значение 9, элементы в индексах 1 и 3 имеют значение 3, элементы в индексах 4 и 6 имеют значение 9, элемент в индексах 5 имеет значение 7 и непарный. Напишите функцию: 

function solution(A);

, которая, учитывая массив A, состоящий из N целых чисел, удовлетворяющих вышеуказанным условиям, возвращает значение непарного элемента.

Например, данный массив A такой, что : 

 A[0] = 9  A[1] = 3  A[2] = 9
 A[3] = 3  A[4] = 9  A[5] = 7
 A[6] = 9

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

function different(a) {
  let result = 0;

    for (let element of a) {
        result ^= element
    }

  return result;
}

const arr = [9, 3, 9, 3, 9, 7, 9];

Я нашел это решение, которое довольно хорошо работает с требуемым условием. Я не понимал, как использовать Bitwise XOR (^)

Я также тестировал разные массивы; 

 arr = [9, 3, 9, 3, 9, 7, 9];  //returns 7 
 arr = [9];                    //returns 9
 arr = [9, 3];                 //returns 10
 arr = [9, 3, 9, 3];           //returns 0
 arr = [9, 3, 9, 9 ];          //returns 10
 arr = [9, 3, 9, 2 ];          //returns 2

Может кто-нибудь объяснить мне, как это работает? Что за логика c за этим стоит? Почему он отлично работает только с необходимым условием?

Ответы [ 2 ]

1 голос
/ 22 апреля 2020

Этот код работает, потому что когда вы XOR номер с 0, вы получите номер, а когда вы XOR номер с самим собой, вы получите 0. Для указанных вами c условий массива только с одним непарным числом ([9, 3, 9, 3, 9, 7, 9]) вы можете развернуть свой l oop, чтобы он выглядел как 

result = 0 ^ 9 ^ 3 ^ 9 ^ 3 ^ 9 ^ 7 ^ 9

и, поскольку 

a ^ b = b ^ a

это можно переписать как 

result = 0 ^ 9 ^ 9 ^ 3 ^ 3 ^ 7 ^ 9 ^ 9
       = 0 ^ 0 ^ 0 ^ 7 ^ 0
       = 7

Причина, по которой это не работает, когда имеется более одного несопоставленного значения, заключается в том, что в результате вы получите XOR всех несопоставленных значений. Например, для [9, 3, 9, 9] вы получите 

result = 9 ^ 3 ^ 9 ^ 9
       = 9 ^ 3 ^ 0
       = 10
0 голосов
/ 22 апреля 2020

Прежде чем ответить на главный вопрос, вы должны знать, как работает XOR. Для четного числа одинаковых битов бит xor равен 0, а для нечетного количества битов бит xor равен 1. Таблица истинности XOR-AB XOR 0 0 0 0 1 1 1 0 1 1 1 0

Теперь к вашим рассуждениям:

Допустим, вы хотите XOR, обратите внимание, что промежуточными состояниями являются двоичные представления

  • 2 ^ 2 = 10 ^ 10 = 00 = 0 (в базе 10 )
  • 2 ^ 2 ^ 3 = 10 ^ 10 ^ 11 = 11 = 3 (в базе 10)

  • 1 ^ 2 ^ 3 = 01 ^ 10 ^ 11 = 00 = 0 (в базе 10)

    Заметили ложный результат? Я надеюсь, теперь вы знаете, как работает XOR. Таким образом, он будет работать только в том случае, если число соединено в массиве и правильно обнаружит только один непарный номер.

...