LOS
10 MEJORES ALGORITMOS DE MANIPULACIÓN DE BITS
|
7.- Contar el total de bits
fijos en todos los números del 1 al n |
&&&&&&&&&&
&&&&&&&
&&&
&
1.- Encontrar el máximo subconjunto XOR en una matriz dada
Dada
una matriz de números enteros, encuentra el máximo valor de submatriz
XOR en la matriz dada. Complejidad de tiempo esperada O(n).
Ejemplo:
Entrada: arr[]
= {1, 2, 3, 4} Salida: 7 La submatriz {3,
4} es el máximo valor XOR
Entrada: arr[]
= {8, 1, 2, 12, 7, 6} Salida: 15 La submatriz {1,
2, 12} es el máximo valor XOR
Entrada: arr[]
= {4, 6} Output: 6 La submatriz {6}
es el máximo valor XOR
Una
solución sencilla es usar dos bucles para encontrar el XOR de todos los submatrices y devolver el máximo.
En lenguaje C++:
#include<bits/stdc++.h>
using
namespace std;
int
maxSubarrayXOR(int arr[], int n)
{
int
ans = INT_MIN;
// Inicializa
// Elegir los puntos
de partida de los subconjuntos
for
(int i=0; i<n; i++)
{ int curr_xor = 0;
// Elija los
puntos finales de los subconjuntos que empiezan con “i”
for
(int j=i; j<n; j++)
{ curr_xor = curr_xor ^ arr[j];
ans = max(ans,
curr_xor);
}
}
return
ans;
}
// Programa principal
int
main()
{ int arr[]
= {8, 1, 2, 12};
int n = sizeof(arr)/sizeof(arr[0]);
cout <<
"Máxima submatriz XOR es " << maxSubarrayXOR(arr, n);
return 0;
}
Salida: 15
La complejidad de la solución es O(n2)
Una
solución eficiente puede resolver el problema anterior en tiempo O(n) bajo el
supuesto de que los números enteros toman un número fijo de bits para
almacenar. La idea es utilizar la estructura de datos adecuada. A continuación
se muestra el algoritmo:
1)
Crear una estructura vacía. Cada nodo de
va a
contener dos hijos, por 0 y 1 valor de bits.
2)
Inicializar pre_xor = 0 e insertar en la estructura.
3)
Inicializar resultado = menos infinito
4)
Atravesar la matriz dada y hacer el seguimiento de cada
elemento de la matriz arr[i].
a) pre_xor = pre_xor ^ arr[i]
pre_xor
ahora contiene xor de elementos de
arr[0] a arr[i].
b) Consultar el valor máximo de xor que termina con arr[i]
c) Actualizar el resultado si el valor
obtenido en el paso
4.b es más que el valor actual del
resultado.
¿Cómo
funciona 4.b)?
Podemos
observar desde el algoritmo de arriba que construimos una estructura que
contiene XOR de todos los prefijos de la matriz dada. Para encontrar el máximo subarreglo XOR que termina con arr[i],
puede haber dos casos.
i)
El prefijo en sí mismo tiene el máximo valor XOR que termina con arr[i]. Por ejemplo, si i=2 en {8, 2, 1, 12}, entonces el
máximo subconjunto XOR que termina con arr[2] es el
prefijo completo.
ii)
Necesitamos eliminar algún prefijo (que termine en índice de 0 a i-1). Por
ejemplo, si i=3 en {8, 2, 1, 12}, entonces el máximo subconjunto xor que termina con arr[3]
comienza con arr[1] y necesitamos eliminar arr[0].
Para
encontrar el prefijo que hay que eliminar, encontramos la entrada que tiene el
máximo valor XOR con el prefijo actual. Si hacemos XOR de dicho prefijo previo
con el prefijo actual, obtenemos el valor XOR máximo que termina con arr[i].
Si
no hay ningún prefijo a eliminar (caso i), entonces devolvemos 0 (por eso
insertamos 0 en Trie).
A
continuación se muestra la implementación de la idea anterior, en lenguaje C++
:
|
#include<bits/stdc++.h> using namespace std;
#define INT_SIZE 32 //Estructura de nodos struct TrieNode { int value; TrieNode *arr[2]; }; // Creación de nodo TrieNode *newNode() { TrieNode
*temp = new TrieNode; temp->value = 0; temp->arr[0] = temp->arr[1] = NULL; return
temp; } // Inserción por XOR void insert(TrieNode
*root, int pre_xor) { TrieNode
*temp = root; for
(int i=INT_SIZE-1; i>=0; i--) { bool val = pre_xor &
(1<<i); //
Nuevo nodo if (temp->arr[val] == NULL) temp->arr[val] =newNode(); temp = temp->arr[val]; } temp->value = pre_xor; } int query(TrieNode
*root, int pre_xor) { TrieNode
*temp = root; for
(int i=INT_SIZE-1; i>=0; i--) { bool val = pre_xor &
(1<<i); if (temp->arr[1-val]!=NULL) temp = temp->arr[1-val]; else if (temp->arr[val] != NULL) temp = temp->arr[val]; } return
pre_xor^(temp->value); } // Devuelve el valor máximo XOR de la submatriz //arr[0..n-1] int maxSubarrayXOR(int
arr[], int n) { TrieNode
*root = newNode(); insert(root, 0); int
result = INT_MIN, pre_xor
=0; for
(int i=0; i<n; i++) { pre_xor = pre_xor^arr[i]; insert(root, pre_xor); result = max(result, query(root, pre_xor)); } return
result; } // Programa principal int main() { int arr[] = {8, 1, 2, 12}; int
n = sizeof(arr)/sizeof(arr[0]); cout
<< "Max subarray XOR is
" << maxSubarrayXOR(arr,
n); return
0; } |
Salida: 15
2.- Encuentra el enésimo número mágico
Un
número mágico se define como un número que puede ser expresado como una
potencia de 5 o la suma de potencias únicas de 5. Los primeros números mágicos
son 5, 25, 30(5 + 25), 125, 130(125 + 5), ....
Escriba
una función para encontrar el enésimo número mágico.
Ejemplo:
Entrada=2, Salida=25
Si
nos fijamos bien, los números mágicos pueden ser representados como 001, 010,
011, 100, 101, 110 etc., donde 001 es 0*pow(5,3) + 0*pow(5,2) + 1*pow(5,1). Así que
básicamente necesitamos añadir potencias de 5 para cada bit establecido en un n
entero dado.
A
continuación se muestra la implementación basada en esta idea, en lenguaje C++
#include <bits/stdc++.h>
using namespace
std;
int nthMagicNo(int n)
{
int pow
= 1, answer = 0;
while (n)
{
pow = pow*5;
if (n
& 1)
answer
+= pow;
n >>= 1; // or n = n/2
}
return answer;
}
// Programa principal
int main()
{
int n = 5;
cout << "nth magic number
is " << nthMagicNo(n)
<< endl;
return 0;
}
Entrada: 5, Salida: 130
3.-
Suma de las diferencias de bits entre todos los pares
Dada
una matriz entera de n números enteros, encuentre la suma de las diferencias de
bits en todos los pares que pueden formarse a partir de los elementos de la
matriz. La diferencia de bits de un par (x, y) es el recuento de diferentes
bits en las mismas posiciones en las representaciones binarias de x e y.
Por
ejemplo, la diferencia de bits para 2 y 7 es 2. La representación binaria de 2
es 010 y 7 es 111 (el primer y el último bits difieren en dos números).
Ejemplo:
Entrada:
arr[] = {1, 2}
Salida: 4
Las
parejas son (1, 1), (1, 2),(2, 1), (2, 2)
Sumando
las diferencias de bits = 0 + 2 +2 + 0= 4
Una
solución sencilla es ejecutar dos bucles para considerar todos los pares uno
por uno. Para cada par, contar las diferencias de bits. Finalmente devuelve la
suma de los recuentos. La complejidad temporal de esta solución es O(n2).
Una
Solución Eficiente puede resolver este problema en tiempo O(n) usando el hecho
de que todos los números se representan usando 32 bits (o algún número fijo de
bits). La idea es contar las diferencias en las posiciones de los bits
individuales. Recorreremos de 0 a 31 y contaremos los números con el juego de
bits i'th. Dejemos que este conteo sea
"contar". Habría números "n-cuento" con el bit i'th no fijado. Así que el recuento de diferencias en i'th bit sería "cuenta * (n-cuenta) * 2", la
razón de esta fórmula es que cada par que tiene un elemento que ha fijado el
bit en la posición i'th y el segundo elemento que
tiene el bit no fijado en la posición i'th contribuye
exactamente 1 a la suma, por lo tanto el recuento total de permutación será
cuenta*(n-cuenta) y multiplicar por 2 es debido a una repetición más de todo
este tipo de par según la condición dada para hacer el par 1<=i,j<=N.
#include <bits/stdc++.h>
using namespace
std;
int sumBitDifferences(int arr[], int
n)
{
int ans
= 0;
for (int
i = 0; i < 32; i++)
{
int
count = 0;
for
(int j = 0; j < n; j++)
if ( (arr[j] & (1 <<
i)) )
count++;
ans += (count * (n - count) * 2);
}
return ans;
}
//Programa principal
int main()
{
int arr[]
= {1, 3, 5};
int n = sizeof arr / sizeof
arr[0];
cout << sumBitDifferences(arr, n)
<< endl;
return 0;
}
Salida: 8
4.-
Intercambiar todos los bits pares e impares
Dado
un entero sin signo, intercambie todos las partes impares por partes pares. Por
ejemplo, si el número dado es 23 (00010111), debe
convertirse en 43 (00101011). Cada bit de posición par se intercambia con el
bit adyacente en el lado derecho (los bits de posición pares se subrayan en la
representación binaria de 23), y cada bit de posición impar se intercambia con
el adyacente en el lado izquierdo.
Si
miramos más de cerca el ejemplo, podemos observar que básicamente necesitamos
desplazar a la derecha (>>) todos los bits pares (En el ejemplo anterior,
los bits pares de 23 están resaltados) en 1 para que se conviertan en bits
impares (resaltados en 43), y desplazar a la izquierda (<<) todos los
bits impares en 1 para que se conviertan en bits pares. La siguiente solución
se basa en esta observación. La solución supone que el número de entrada se
almacena utilizando 32 bits.
Que
el número de entrada sea x
1)
Busca todos los bits pares de x haciendo bitwise y de
x con 0xAAAAAAA. El número 0xAAAAAAA es un número de 32 bits con todos los bits
pares puestos como 1 y todos los bits impares como 0.
2)
Busca todos los bits impares de x haciendo bitwise y
de x con 0x55555555. El número 0x55555555 es un número de 32 bits con todos los
bits impares puestos como 1 y todos los bits pares como 0.
3)
Desplazamiento a la derecha todos los bits pares.
4)
Desplazamiento a la izquierda todos los bits impares.
5)
Combinar los nuevos bits pares e impares y regresar.
En
lenguaje C++:
#include <bits/stdc++.h>
using namespace
std;
unsigned int
swapBits(unsigned int x)
{
unsigned int even_bits = x &
0xAAAAAAAA;
unsigned int odd_bits = x &
0x55555555;
even_bits >>=
1; odd_bits <<=
1;
return (even_bits | odd_bits); }
// Programa principal
int main()
{
unsigned int x = 23; // 00010111
cout<<swapBits(x);
return 0;
}
Salida: 43
5.-
Encuentra el elemento que aparece una vez
Dado
un conjunto en el que cada elemento ocurre tres veces, excepto un elemento que
ocurre sólo una vez. Encuentra el elemento que ocurre una vez. La complejidad
temporal esperada es O(n) y O(1) espacio extra.
Ejemplos
:
Entrada:
arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Salida: 2
En
la matriz dada, todos los elementos aparecen tres veces, excepto dos que
aparecen una vez.
Podemos
usar la clasificación para hacerlo en tiempo de O(nLogn).
También podemos usar hashing, tiene la peor
complejidad de tiempo O(n), pero requiere espacio extra.
La
idea es usar operadores de bits para una solución que es O(n) tiempo y usa O(1)
espacio extra. La solución no es fácil como otras soluciones basadas en XOR,
porque todos los elementos aparecen un número impar de veces aquí. La idea es
la siguiente:
Ejecuta
un bucle para todos los elementos de la matriz. Al final de cada iteración,
mantenga los siguientes dos valores.
unos:
Los bits que han aparecido la primera vez o la cuarta o la séptima vez... etc.
dos:
Los bits que han aparecido la segunda vez o la quinta vez o la octava vez...
etc.
Finalmente,
devolvemos el valor de "unos
¿Cómo
mantener los valores de "unos" y "dos"?
"unos"
y "dos" se inicializan como 0. Para cada nuevo elemento de la matriz,
averigua los bits comunes del nuevo elemento y el valor anterior de
"unos". Estos bits de conjunto comunes son en realidad los bits que
deben ser añadidos a "dos". Así que haz el "O" de los bits
de conjunto comunes con "dos". "dos" también obtiene
algunos bits extra que aparecen a la tercera vez. Estos bits adicionales se
eliminan más tarde.
Actualizar
"unos" haciendo XOR del nuevo elemento con el valor anterior de
"unos". Puede haber algunos bits que aparecen a la tercera vez. Estos
bits extra también se eliminan más tarde.
Tanto
"unos" como "dos" contienen esos bits extra que aparecen a
la tercera vez. Elimina estos bits extra encontrando los bits comunes en
"unos" y "dos".
En
lenguaje C++:
#include <bits/stdc++.h>
using namespace
std;
int getSingle(int arr[], int
n)
{
int ones
= 0, twos = 0;
int common_bit_mask;
for (int
i = 0; i < n; i++) {
/* La expresión "one & arr[i]" da los
bits que son
en ambos "unos" y
el nuevo elemento de arr[]. Nosotros
añadir estos bits a 'dos'
usando bitwise O
El valor de "dos"
se fijará en 0, 3, 3 y 1 después del primero,
2ª, 3ª y 4ª iteraciones
respectivamente */
twos
= twos | (ones & arr[i]);
/* XOR los nuevos bits con
los anteriores para obtener todos los bits
apareciendo un número impar
de veces
El valor de "unos"
se fijará en 3, 0, 2 y 3 después del primero,
2ª, 3ª y 4ª iteraciones
respectivamente
*/
ones
= ones ^ arr[i];
/* Los bits comunes son
aquellos bits que aparecen a la tercera vez
Así que estos trozos no
deberían estar ahí tanto en "unos" como en "dos".
La máscara_de_bits_comunes
contiene todos estos bits como 0, de modo que los bits pueden
se eliminarán de
"unos" y "dos
El valor de "common_bit_mask" se fijará en 00, 00, 01 y 10
después de la 1ª, 2ª, 3ª y 4ª
iteraciones respectivamente
*/
common_bit_mask
= ~(ones & twos);
/* Quitar los bits comunes
(los bits que aparecen a la tercera vez) de "unos
El valor de "unos" se fijará
en 3, 0, 0 y 2 después del primero,
2ª, 3ª y 4ª iteraciones
respectivamente
*/
ones
&= common_bit_mask;
/* Quitar los bits comunes
(los bits que aparecen a la tercera vez) de los "dos".
El valor de "dos"
se fijará en 0, 3, 1 y 0 después del primero,
2ª, 3ª y 4ª itearaciones respectivamente
*/
twos
&= common_bit_mask;
}
return ones;
}
// Programa principal
int main()
{
int arr[]
= { 3, 3, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "
El elemento con una sola ocurrencia es " << getSingle(arr, n);
return 0;
}
Salida: El
elemento con una sola ocurrencia es 2
Complejidad: O(n)
6.-
Representación binaria de un número determinado
Escribir
un programa para imprimir la representación binaria de un número dado.
Método
1: Iterativo
Para
cualquier número, podemos comprobar si su 'i'th bit
es 0(OFF) o 1(ON), con un bit de AND con "2^i" (2 subir a i).
1)
Tomemos el número 'NUM' y comprobemos si su bit 0 está ON o
OFF
bit = 2 ^ 0 (0th bit)
si NUM y bit == 1 significa que el 0º bit
está ON o el 0º bit está OFF
2)
Del mismo modo, si queremos comprobar si el 5º bit está ON u OFF
bit = 2 ^ 5 (5º bit)
si NUM y bit == 1 significa que su 5º bit
está ON o el 5º bit está OFF.
Tomemos
un entero sin signo (32 bits), que consiste en 0-31 bits. Para imprimir la
representación binaria de un entero sin signo, comience desde el 31º bit, compruebe
si el 31º bit está ON u OFF, si está ON imprima "1", si no imprima
"0". Ahora comprueba si el 30º bit está ON u OFF, si está ON imprime
"1", si no imprime "0", haz esto para todos los bits de 31
a 0, finalmente obtendremos la representación binaria del número.
void bin(unsigned n)
{
unsigned i;
for (i = 1 << 31; i
> 0; i = i / 2)
(n & i)? printf("1"): printf("0");
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
Método
2: Recursivo
A
continuación se muestra el método recursivo para imprimir la representación
binaria de 'NUM'.
paso
1) si NUM > 1
a) empujar NUM en la pila
b) función de llamada recursiva con
"NUM / 2
paso
2)
a)
Sacar
el NUM de la pila, dividirlo por 2 e imprimir el resto.
b)
#include<bits/stdc++.h>
using namespace
std;
void bin(unsigned n)
{
/* Paso 1 */
if (n > 1)
bin(n/2);
/* Paso 2 */
cout << n % 2;
}
int main(void)
{
bin(7);
cout << endl;
bin(4);
}
Salida: 111 100
7.-
Contar el total de bits fijos en todos los números del 1 al n
Dado
un número entero positivo n, cuente el número total de bits fijos en
representación binaria de todos los números de 1 a n.
Ejemplos:
Entrada:
n = 3
Salida: 4
Método
1 (Sencillo)
Una
solución simple es ejecutar un bucle de 1 a n y sumar la cuenta de bits fijos
en todos los números de 1 a n.
#include <stdio.h>
unsigned int
countSetBitsUtil(unsigned int x);
unsigned int
countSetBits(unsigned int n)
{
int bitCount
= 0;
for (int
i = 1; i <= n; i++) bitCount
+= countSetBitsUtil(i);
return bitCount;
}
unsigned int
countSetBitsUtil(unsigned int x)
{
if (x <= 0)
return
0;
return (x % 2 == 0 ? 0 :
1) + countSetBitsUtil(x / 2);
}
// Principal
int main()
{
int n = 4;
printf("El total del
conjunto de bits es de ", countSetBits(n));
return 0;
}
El total del conjunto de bits es de 5
Complejidad temporal: O(nLogn)
Método
2 (Más sencillo y eficiente que el Método 1)
Si
observamos los bits desde el lado derecho a la distancia i, entonces los bits
se invierten después de la posición 2^i en secuencia vertical.
por
ejemplo n = 5;
0
= 0000
1
= 0001
2
= 0010
3
= 0011
4
= 0100
5
= 0101
Observe
el bit más derecho (i = 0) los bits se voltean después (2^0 = 1)
Observe
el 3er bit más a la derecha (i = 2) los bits se voltean después (2^2 = 4)
Así
que podemos contar los bits en forma vertical de tal manera que a la derecha la
mayoría de los bits se voltearán después de la iteración de 2^i;
|
#include <bits/stdc++.h>
using namespace
std; int countSetBits(int n) { int i = 0; int ans = 0; while ((1
<< i) <= n) { bool
k = 0; int
change = 1 << i; for
(int j = 0; j <= n; j++)
{ ans += k; if (change == 1) { k
= !k; // When change = 1 flip the bit change = 1 << i; // again
set change to 2^i }
else { change--; }
} i++; } return ans; } // Principal int main()
{ int n = 17; cout << countSetBits(n) << endl; return 0; } Salida: 35 Complejidad temporal: O(k*n) |
8.- Rotar los bits de un número
Rotación
de bits: Una rotación (o desplazamiento circular) es una operación similar al
desplazamiento, excepto que los bits que se caen en un extremo se vuelven a
poner en el otro extremo.
En
la rotación a la izquierda, los trozos que se caen en el extremo izquierdo se
vuelven a colocar en el extremo derecho.
En
la rotación derecha, los trozos que se caen en el extremo derecho se vuelven a
colocar en el extremo izquierdo.
Ejemplo:
Que
n se almacene usando 8 bits. La rotación a la izquierda de n = 11100101 por 3
hace que n = 00101111 (La izquierda se desplaza por 3 y los primeros 3 bits se
vuelven a poner en último lugar). Si n se almacena usando 16 o 32 bits entonces
la rotación izquierda de n (000...11100101) se convierte en 00..0011100101000.
La
rotación derecha de n = 11100101 por 3 hace que n = 10111100 (La derecha se
desplaza por 3 y los 3 últimos bits se vuelven a poner en primer lugar) si n se
almacena usando 8 bits. Si n se almacena usando 16 o 32 bits entonces la rotación
derecha de n (000...11100101) por 3 se convierte en 101000..0011100.
#include<iostream>
using namespace
std;
#define INT_BITS 32
class gfg
{
public:
int leftRotate(int n, unsigned int d)
{
return (n
<< d)|(n >> (INT_BITS - d));
}
int rightRotate(int n, unsigned int d)
{
/* In n>>d, first d
bits are 0.
To put
last 3 bits of at
first, do bitwise or of n>>d
with n <<(INT_BITS
- d) */
return (n >> d)|(n
<< (INT_BITS - d));
}
};
//Principal
int main()
{
gfg g;
int n = 16;
int d = 2;
cout << " La
rotación izquierda de " << n <<
"
by " << d << " is ";
cout << g.leftRotate(n, d);
cout << " La
rotación derecha de " << n <<
"
by " << d << " is ";
cout << g.rightRotate(n, d);
getchar();
}
Salida:
La rotación izquierda de 16 por
2 es de 64
La rotación derecha de 16 por 2
es de 4
9.-
Contar el número de bits a variar para convertir A en B
Dados
dos números "a" y "b". Escriba un programa para contar el
número de bits necesarios para convertir 'a' en 'b'.
Ejemplo:
Entrada
: a = 10, b = 20
Salida:
4
La
representación binaria de a es 00001010
La
representación binaria de b es 00010100
Tenemos
que dar la vuelta a los cuatro bits resaltados en un
para
hacerla b.
1.
Calcular XOR de A y B.
a_xor_b = A ^
B
2. Cuente los bits del conjunto en lo
anterior
calculó el resultado de XOR.
countSetBits(a_xor_b)
El
XOR de dos números tendrá bits fijos sólo en aquellos lugares donde A difiere
de B.
#include <iostream>
using namespace
std;
int countSetBits(int n)
{
int count
= 0;
while (n > 0)
{
count++;
n &= (n-1);
}
return count;
}
int FlippedCount(int a, int b)
{
return countSetBits(a^b);
}
// Principal
int main()
{
int a = 10;
int b = 20;
cout << FlippedCount(a, b)<<endl;
return 0;
}
Salida: 4
10.-
Encuentra el siguiente número disperso
Un
número es disperso si no hay dos 1s adyacentes en su representación binaria.
Por ejemplo 5 (representación binaria: 101) es disperso, pero 6 (representación
binaria: 110) no es disperso.
Dado
un número x, encuentra el menor número disperso que sea mayor o igual a x.
Ejemplos:
Entrada:
x = 6
Salida:
El siguiente número es el 8
1)
Escribir una función de utilidad esSparse(x) que toma
un número
y devuelve verdadero si x es disperso, si
no, falso. Esta función
puede escribirse fácilmente atravesando los
bits del número de entrada.
2)
Empiece desde x y haga lo siguiente
mientras que(1)
{
si (isSparse(x))
Devuelva la X;
más
x++
}
La
complejidad temporal de isSparse() es O(Log x). La
complejidad temporal de esta solución es O(x Log x). El siguiente número escaso
puede estar a lo sumo a una distancia de O(x).
Una
Solución Eficiente puede resolver este problema sin tener que comprobar todos
los números de uno en uno. A continuación se presentan los pasos.
1)
Encontrar el binario del número dado y almacenarlo en un
una matriz booleana.
2)
Inicializar la posición del último bit_finalizado
como 0.
2)
Comenzar a recorrer el binario desde el bit menos significativo.
a) Si
obtenemos dos 1's adyacentes de tal manera que el siguiente (o el tercero)
bit no es 1, entonces
(i) Hacer que todos los bits después
de este 1 a la última finalización
bit (incluyendo el último
finalizado) como 0.
ii) Actualizar el último bit
finalizado como el siguiente bit.
Por
ejemplo, dejemos que la representación binaria sea 01010001011101, la cambiamos
a 01010001100000 (todos los bits después del 11 resaltado se ponen a 0). De
nuevo dos 1 son adyacentes, así que cambiamos la representación binaria a
01010010000000. Esta es nuestra respuesta final.
A
continuación se muestra la implementación de la solución anterior.
#include<bits/stdc++.h>
using namespace
std;
int nextSparse(int x)
{
vector<bool> bin;
while (x != 0)
{
bin.push_back(x&1);
x >>= 1;
}
bin.push_back(0);
int n = bin.size();
int last_final
= 0;
for (int
i=1; i<n-1; i++)
{
if (bin[i] == 1 && bin[i-1]
== 1 && bin[i+1] != 1)
{
// Make the next
bit 1
bin[i+1] = 1;
for (int j=i; j>=last_final; j--)
bin[j] = 0;
last_final = i+1;
}
}
int ans
= 0;
for (int
i =0; i<n; i++)
ans
+= bin[i]*(1<<i);
return ans;
}
// Principal
int main()
{
int x = 38;
cout << "
Nuevo número disperso es " << nextSparse(x);
return 0;
}
Salida: Nuevo número disperso es 40
Complejidad temporal: O(Log x)
&&&&&&&&&&&&&
&&&&&&&&
&&&
&