programa en C ++ para encontrar dos números únicos de una matriz

programa en C ++ para encontrar dos números únicos de una matriz: Aquí, vamos a aprender a encontrar dos números únicos de una matriz dada usando operadores de bits ?

Descripción:

solución para encontrar los dos números únicos a partir del conjunto de los números que se produjo dos veces aceptar los números únicos

Planteamiento del problema:

Escribir un programa en C ++ que acepte la entrada matriz a partir de usuario y encontrar los dos número único que se ha producido sólo una vez en conjunto .

Ejemplo:

    Input: 
      10
      1 1 2 3 3 4 4 5 6 6        
      Output:
      2 5
  

Explicación:

Este problema puede resolverse utilizando el concepto de XOR bit a bit, AND bit a bit, y el enmascaramiento de bits.

XOR bit a bit:

XOR bit a bit (^) realiza dos patrones de bits de igual longitud. Si ambos bits en la posición comparación de los patrones de bits son 0 o 1, el bit en el patrón de bits resultante es 0, de lo contrario 1.

Ejemplo:

    A = 5 = 0101, B = 3 = 0011
      A ^ B = 0101 ^ 0011 = 0110 = 6
      Special Property of XOR: 
      A^A =0
      A^0 = A
  

AND bit a bit

AND bit a bit (^) toma dos patrones de bits de igual longitud. La salida de AND bit a bit es 1 si los bits correspondientes de dos operandos es 1. Si una de bit de un operando es 0, el resultado de bit correspondiente se evalúa a 0.

Ejemplo:

    A = 5 = 0101, B = 3 = 0011
      A & B = 0101 & 0011 = 0001 = 1
  

class el problema actual:

1. En primer lugar tomamos XOR de todos los elementos de la matriz.
2. supongamos que tenemos: 1,1,2,3,3,4,4,5,6,6
3. Al tomar XOR de todos los elementos, esto eliminará los elementos duplicados como A ^ A = 0
   Entonces conseguimos: 2 ^ 5 del resultado anterior
4. el resultado de 2 ^ 5 sin duda tendrá al menos un conjunto de bits, para encontrar el conjunto más a la derecha bit hacemos res y 1 y hacer un recuento de tomar la comunicación de la posición actual. Si obtenemos un valor distinto de cero res y 1 Esa es la posición que queremos conseguir, For el bucle, de lo contrario el desplazamiento a la derecha res y el incremento del recuento.
5. hacer una máscara usando 1 & lt; & lt; recuento , y tomar y uno por uno con todos los elementos, elementos resultantes un resultado no cero de máscara y arr [i] , tomar XOR de ellos.
6. resultante XOR dará lugar a firstNo .
7. Ahora class SecondNo , tomar XOR de firstNo con res iniciales . es decir, firstNo ^ firstNo ^ secondNo .

Algoritmo:

1. Set res = 0 y encontrar su XOR con todos los demás elementos de la matriz.
2. Ahora res = firstNo ^ secondNo .
3. Obtener posición de bit más a la derecha del conjunto res . usando la función findRightMostBit
4. Set bitPos = posición de bit conjunto más a la derecha.
5. establecer una máscara con una estructura de conjunto de bits en la posición bitPos , utilizando 1 & lt; & lt; bitPos .
6. Conjunto firstNo = 0

For i=0 to size of array
      If mask & arr[i] != 0
          firstNo = firstNo ^ arr[i]
      //End of if
  //End of loop
  

7. Set secondNo = firstNo ^ res .
8. Imprimir firstNo y secondNo .

Programa:

#include<bits/stdc++.h>
  using namespace std;
  int findRightMostBit(int x) {
      int i = 0;
      while (x > 0) {
          if(x&1){
              return i;
          }
          x>>1;
          i++;
      }
      return i;
  }
  void findUnique(int arr[], int size) {
      int res = 0;
      for (int i = 0; i < size; ++i) {
          res = res ^ arr[i];
      }
      int bitPos = findRightMostBit(res);
      int mask = (1 << bitPos);
      int firstNo=0;
      for (int i = 0; i < size; ++i)
      {
          if ((mask & arr[i]) != 0) {
              firstNo = firstNo ^ arr[i];
          }
      }    
      int secondNo = firstNo^ res;
      cout<<"Two Unique Numbers : "<<firstNo<<" , "<<secondNo;
  }
  int main() {
      int n;
      cout<<"Enter size of array : ";
      cin>>n;
      int arr[n];
      cout<<"Enter elements of array : n";
      for (int i = 0; i < n; ++i)
      {
          cin>>arr[i];
      }
      findUnique(arr, n);
      return 0;
  }
  

salida

Enter size of array : 10
  Enter elements of array :
   1 1 2 3 3 4 4 5 6 6
  Two Unique Numbers : 5 , 2