Как xor дает различное число в двух массивах? - PullRequest
Новая
       78

Как xor дает различное число в двух массивах?

2 голосов
/ 03 ноября 2019

Я ответил на следующие ката: Потерянный номер в числовой последовательности . Описание:

"Дана упорядоченная последовательность чисел от 1 до N. Возможно, из нее удалено одно число, а остальные числа смешаны. Найдите номер, который был удален.

Пример: 

The starting array sequence is [1,2,3,4,5,6,7,8,9]
The mixed array with one deleted number is [3,2,4,6,7,8,1,9]
Your function should return the int 5.

Если из массива не было удалено ни одного числа и нет разницы с ним, ваша функция должна возвращать int 0.

Обратите внимание, что N может быть 1 или меньше (вВ последнем случае первым массивом будет []). "

Я написал простой ответ: 

import java.util.*;

  public class Kata {
    public static int findDeletedNumber (int[] arr, int[] mixedArr) {  
      Arrays.sort(mixedArr);
      for(int i = 0; i < arr.length; i++){
        try{
          if(arr[i] != mixedArr[i]){
            return arr[i];
          }
        }catch(ArrayIndexOutOfBoundsException e) {
          return arr[i];
        }
      }
      return 0;
    }
}

Я читал ответы других людей и нашел один, который я нахожу оченьтрудно понять глубоко: 

import java.util.Arrays;

public class Kata {
    public static int findDeletedNumber(int[] arr, int[] mixedArr) {
        return Arrays.stream(arr).reduce((a, b) -> a ^ b).orElse(0) ^ Arrays.stream(mixedArr).reduce((a, b) -> a ^ b).orElse(0);
    }
}

Ссылка на ответ: https://www.codewars.com/kata/reviews/595be553429e11365c00006f/groups/59bef3a1eda42eb0bc001612

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

Кроме того, я попытался понять это самостоятельно, прочитав: Что делает оператор ^ в Java? https://www.geeksforgeeks.org/bitwise-operators-in-java/

1 Ответ

4 голосов
/ 03 ноября 2019

Таблица истинности XOR (Exclusive-OR) 

X   Y    result
0   0    0
0   1    1
1   0    1
1   1    0

Что означает X^Y? Давайте посмотрим на пример: 5^6

dec       bin

5     =  101
6     =  110
------------------ xor
3     =  011

XOR - это просто преобразование двух чисел в двоичное и применение правил в таблице истинности.

ПросмотрВ приведенной выше таблице очевидно, что X^X = 0 for any integer X

5     =  101
5     =  101
------------------ xor
0     =  000

и X^0 = X

5     =  101
0     =  000
------------------ xor
5     =  101

Учитывая, что ваши два массива XOR для каждого элемента в обоих массивах и XOR длярезультат означает что-то вроде 

(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9) ^ (3 ^ 2 ^ 4 ^ 6 ^ 7 ^ 8 ^ 1 ^ 9)

и потому что X^Y = Y^X и X^Y^Z = (X^Y)^Z = X^(Y^Z) вы можете изменить вышеприведенное значение на 

(1 ^ 1) ^ ( 2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4)  ^ (5) ^ (6 ^ 6) ^ (7 ^ 7) ^ (8 ^ 8) ^ (9 ^ 9)

, все взаимно компенсируется, кроме пропущенного числа, то есть 5.

...