La pregunta es quizás un poco engañosa, pero no sabía cómo preguntarla de otra manera. Hay un problema en hackerrank que va de la siguiente manera:

Considere una matriz de enteros, donde todos menos uno de los enteros ocurren en pares. En otras palabras, cada elemento en aparece exactamente dos veces, excepto un elemento único.

Dada la matriz, encuentre e imprima el elemento único. [2,3,1,3,2] -> el resultado es 1

enter image description here

Resolví el problema así:

private static int lonelyInteger(int[] a) {
        if(a==null)
            return 0;

         if(a.length<2)
             return a.length;

        Set<Integer> set = new HashSet<>();

        for(int i : a){

            if(set.contains(i)){
                set.remove(i);
            }else{
                set.add(i);
            }            
        }

        return (Integer) set.toArray()[0];
    }

Sin embargo, resultó que hay una solución clara para este problema que es:

private static int lonelyInteger(int[] a) {
         int b = a[0];

         for(int i = 1; i < a.length; i++){
             b ^= a[i];
         }
        return b;       
    }

¡El problema es que no sé POR QUÉ FUNCIONA! Entiendo CÓMO funciona pero no entiendo ¿POR QUÉ FUNCIONA? Para comprender que hice un pequeño programa para generar los resultados de cada paso:

public class BitwiseOperator {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        int sum = 0;
        in.nextLine();
        String line = in.nextLine();
        String[] numbers = line.split(" ");
        for (int i = 0; i < numbers.length; i++) {
            a[i] = Integer.valueOf(numbers[i]);
        }

        for (int i = 0; i < a.length; i++) {
            binary(sum, a[i]);
            sum ^= a[i];
            binary(sum);
            System.out.println();
            System.out.println();
            System.out.println();

        }
        System.out.println(sum);
    }


    private static void binary(int sum) {
        System.out.println(String.format("%16s", Integer.toBinaryString(sum)).replace(' ', '0') + " ->" + sum);
    }

    private static void binary(int sum, int i) {
        System.out.println(String.format("%16s", Integer.toBinaryString(sum)).replace(' ', '0') + " ->" + sum);
        System.out.println("XOR");
        System.out.println(String.format("%16s", Integer.toBinaryString(i)).replace(' ', '0') + " ->" + i);
        System.out.println("--------");
    }


}

Si ingresa la siguiente entrada:

5

2 3 2 1 3

La salida es:

0000000000000000 ->0
XOR
0000000000000010 ->2
--------
0000000000000010 ->2



0000000000000010 ->2
XOR
0000000000000011 ->3
--------
0000000000000001 ->1



0000000000000001 ->1
XOR
0000000000000010 ->2
--------
0000000000000011 ->3



0000000000000011 ->3
XOR
0000000000000001 ->1
--------
0000000000000010 ->2



0000000000000010 ->2
XOR
0000000000000011 ->3
--------
0000000000000001 ->1



1

Entonces el programa realmente funciona PERO Realmente necesito entender ¿POR QUÉ?

3
Adelin 28 abr. 2017 a las 10:55

3 respuestas

La mejor respuesta

Una prueba precisa, en mi humilde opinión, implica teoría de grupo (puede construir grupo abeliano basado en xor):

  1. xor es una operación grupal
  2. 0 es un grupo 0
  3. A es un elemento inverso (por lo que cualquier A es inverso a sí mismo).

Por supuesto, tenemos que demostrar que (A xor B) xor C == A xor (B xor C)

Desde A xor B == B xor A tenemos un grupo abeliano y es por eso que podemos reagruparnos artículos en cualquier orden:

  A XOR B XOR C XOR A XOR B ==
 (A XOR A) XOR (B XOR B) XOR C ==
  C

En caso general:

   A xor B xor ... xor Z ==
  (A xor A) xor (B xor B) xor ... xor (distinct Item) ==
   0 xor 0 xor ... xor (distinct Item) ==
   distinct Item
4
Dmitry Bychenko 28 abr. 2017 a las 08:44

Trataré de hacerlo breve y simple.

XOR al mismo número devuelve 0 .

Ejemplo: 23 ^ 23 = 0 -325 ^ -325 = 0

Entonces, mientras ejecuta el ciclo XOR de, los números que aparecen dos veces se cancelarán y finalmente obtendrá el número que es único.

0
Subham Raj 26 sep. 2019 a las 11:10

Considere una matriz de enteros, donde todos menos uno de los enteros ocurren en pares. En otras palabras, cada elemento contiene exactamente dos veces, excepto un elemento único. Ahora imagina que sumas todos esos números.

¿Qué significa si esa suma es par? Significa que el número que aparece una vez debe ser par. ¿Qué significa si esa suma es impar? Significa que el número que aparece una vez debe ser impar. Piensa en esto hasta que lo entiendas.

Ahora imagina que en lugar de sumarlos, simplemente hicimos un seguimiento de si la suma era par o impar. Entonces, si los dos primeros números fueran 3 y 7, la suma sería 10, pero recordemos que es par. Esto todavía funcionaría. La respuesta final sería par si el número que aparece una vez es par e impar si el número que aparece una vez es impar. Piense en esto hasta que lo entienda.

Así es como podríamos hacer que funcione para un poco de los números. Pero también podríamos hacer eso para todos los bits al mismo tiempo, rastreando para cada posición de bit si el total fue impar o par. Cuando termine, tendríamos si el número que apareció una vez fue impar o par para cada posición de bit, y eso es todo lo que necesitamos. Como lo estamos haciendo en binario, el único número impar para esa posición es 1 y el único par es 0. Piensa en esto hasta que lo entiendas.

1
David Schwartz 28 abr. 2017 a las 08:04