programa en C ++ para encontrar el número único usando enmascaramiento de bits

Aquí, estamos implementando un programa C ++ para encontrar el número único usando enmascaramiento poco .

Planteamiento del problema: programa C ++ para encontrar número único de una matriz de n números en los que, excepto uno (número único) descansan todos están presentes tres veces.

restricciones: n & lt; 10 ^ 5

Ejemplo:

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

Solución: Excepto 4 resto todos tienen multiplicidad de 3 en array. ejemplo class 4 se representan como 100 en .Starting binario de izquierda más bit es el primer índice de la matriz de la cuenta.

C++ program to find Unique Number using Bit Masking - 4

Problema explicación:

  1. Hacer un recuento array (inicializar todos los elementos a 0) para almacenar los bits de cada número en la matriz de entrada.
  2. En cada acceso iteración el número de entrada y extraer sus bits para almacenar en recuento instancia de matriz For si el número es 6 que es 110 en binario, de modo 110 y 1 almacena 0 en recuento de [0] , turno luego a la derecha el número para obtener el siguiente bit de la izquierda, que es de 11 y 1 almacena 1 en recuento [1] y de manera similar otra vez >> número 1 para obtener de nuevo en recuento [2] .
  3. Después de cada matriz cuenta de iteración se actualiza. Ahora ya que cada elemento excepto uno se produce tres veces en la matriz de entrada, por lo tanto, los bits en cada existen índice en forma de 3n y 3n 1 .
  4. Así que teniendo un módulo de 3 bits de hojas solamente del número único en recuento matriz como residuos. Esto le dará el número binario del número único.
  5. Ahora convertir binario a decimal por Σ multiplican (bit con 2 ^ índice en el índice respectivo).
  6. class el número único en array.

Programa:

#include <iostream>
using namespace std;
int unique(int *arr,int n)
{
//array of size 64 for max 64 bit size
int count[64]={0};
//count array stores bit of every number
for(int k=0;k<n;k++)
{
int i=0;
int num=arr[k];
while(num>0)
{
// extract bit
count[i]+=(num&1);
i++;
// right shift to get next leftmost bit
num=num>>1;
}
}
// starting from first index 2^0=1
int power=1;
int result=0;
for(int j=0;j<64;j++)
{
// take modulus of count array by 3
count[j] %=3;
result+=count[j]*power;
// binary to decimal operation
power=power<<1;
}
// if there is no unique number 0 is returned
return result;
}
int main()
{
int arr[50];
int n;
cout<<"Enter lenght of the array: ";
cin>>n;
cout<<"Enter array elements..."<<endl;
for(int c=0;c<n;c++)
{
cin>>arr[c];
}
cout<<unique(arr,n)<<" is the unique number in array.";
return 0;
}

salida

Enter lenght of the array: 4
Enter array elements...
10 10 10 40
40 is the unique number in array.


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *