Programa C++ para verificar si dos números son rotaciones de bits entre sí o no

Dados dos números enteros positivos x e y, verifique si un número entero se obtiene rotando bits de otro.
 

Restricción de entrada: 0 < x, y < 2^32 

Rotación de bits: una rotación (o cambio circular) es una operación similar al cambio, excepto que los bits que se caen en un extremo se vuelven a colocar en el otro extremo.
Puede encontrar más información sobre la rotación de bits aquí
Ejemplo 1: 
 

Entrada : a = 8, b = 1

Salida : si

Explicación :

Representación de a = 8 : 0000 0000 0000 0000 0000 0000 0000 1000

Representación de b = 1 : 0000 0000 0000 0000 0000 0000 0000 0001

Si rotamos a 3 unidades hacia la derecha, obtenemos b, por lo tanto, la respuesta es sí.

Ejemplo 2: 

Entrada : a = 122, b = 2147483678

Salida : si
 

Explicación :

Representación de a = 122 : 0000 0000 0000 0000 0000 0000 0111 1010

Representación de b = 2147483678 : 1000 0000 0000 0000 0000 0000 0001 1110

Si rotamos a 2 unidades hacia la derecha, obtenemos b, por lo tanto, la respuesta es sí.
 

Dado que el total de bits en los que se puede representar x o y es 32, ya que x, y > 0 y x, y < 2^32. 
Entonces necesitamos encontrar las 32 rotaciones posibles de x y compararlas con y hasta que x e y no sean iguales. 
Para hacer esto, usamos una variable temporal x64 con 64 bits que es el resultado de la concatenación de x a x, es decir, 
x64 tiene los primeros 32 bits iguales a los bits de x y los últimos 32 bits también son iguales a los bits de x64.
Luego seguimos cambiando x64 por 1 en el lado derecho y comparamos los 32 bits más a la derecha de x64 con y. 
De esta forma podremos obtener todas las combinaciones de bits posibles debido a la rotación.
Aquí está la implementación del algoritmo anterior.
 

// C++ program to check if two numbers are bit rotations
// of each other.
#include <iostream>
using namespace std;
 
// function to check if  two numbers are equal
// after bit rotation
bool isRotation(unsigned int x, unsigned int y)
{
    // x64 has concatenation of x with itself.
    unsigned long long int x64 = x | ((unsigned long long int)x << 32);
 
    while (x64 >= y)
    {
        // comparing only last 32 bits
        if (unsigned(x64) == y)
            return true;
 
        // right shift by 1 unit
        x64 >>= 1;
    }
    return false;
}
 
// driver code to test above function
int main()
{
    unsigned int x = 122;
    unsigned int y = 2147483678;
 
    if (isRotation(x, y))
        cout << "yes" << endl;
    else
        cout << "no" << endl;
 
    return 0;
}

yes

Complejidad de tiempo: O(log ₂ n), donde n es el número dado
Espacio auxiliar: O(1)

¡ Consulte el artículo completo sobre Comprobar si dos números son rotaciones de bits entre sí o no para obtener más detalles!