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:
- En primer lugar tomamos XOR de todos los elementos de la matriz.
- supongamos que tenemos: 1,1,2,3,3,4,4,5,6,6
- Al tomar XOR de todos los elementos, esto eliminará los elementos duplicados como A ^ A = 0
Entonces conseguimos: 2 ^ 5 del resultado anterior - 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.
- 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.
- resultante XOR dará lugar a firstNo .
- Ahora class SecondNo , tomar XOR de firstNo con res iniciales . es decir, firstNo ^ firstNo ^ secondNo .
Algoritmo:
- Set res = 0 y encontrar su XOR con todos los demás elementos de la matriz.
- Ahora res = firstNo ^ secondNo .
- Obtener posición de bit más a la derecha del conjunto res . usando la función findRightMostBit
- Set bitPos = posición de bit conjunto más a la derecha.
- establecer una máscara con una estructura de conjunto de bits en la posición bitPos , utilizando 1 & lt; & lt; bitPos .
- Conjunto firstNo = 0
- Set secondNo = firstNo ^ res .
- Imprimir firstNo y secondNo .
For i=0 to size of array
If mask & arr[i] != 0
firstNo = firstNo ^ arr[i]
//End of if
//End of loop
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