Compruebe si dos números son rotaciones de bits entre sí o no

Dados dos enteros positivos x e y (0 < x, y < 2^32), comprueba si un entero se obtiene rotando los bits del otro. 

Rotación de bits : una rotación (o cambio circular) es una operación similar a un cambio, excepto que los bits que se caen en un extremo se vuelven a colocar en el otro extremo.

Ejemplos: 

Entrada : a = 8, b = 1
Salida : sí
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 por 3 unidades correctas obtenemos b, por lo tanto, la respuesta es sí.

Input : a = 122, b = 2147483678
Output : yes
Explanation : Representation of a = 122 : 0000 0000 0000 0000 0000 0000 0111 1010,Representation of b = 2147483678 : 1000 0000 0000 0000 0000 0000 0001 1110, If we rotate a by 2 unidades correctas obtenemos b, por lo tanto, la respuesta es sí.

Acercarse:

• 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 ello usamos una variable temporal x64 con 64 bits, que es resultado de la concatenación de x a x ie. 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;
}

// Java program to check if two numbers are bit rotations
// of each other.
class GFG {
 
// function to check if two numbers are equal
// after bit rotation
    static boolean isRotation(long x, long y) {
        // x64 has concatenation of x with itself.
        long x64 = x | (x << 32);
 
        while (x64 >= y) {
            // comparing only last 32 bits
            if (x64 == y) {
                return true;
            }
 
            // right shift by 1 unit
            x64 >>= 1;
        }
        return false;
    }
 
// driver code to test above function
    public static void main(String[] args) {
        long x = 122;
        long y = 2147483678L;
 
        if (isRotation(x, y) == false) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}
 
// This code is contributed by 29AjayKumar

# Python3 program to check if two
# numbers are bit rotations of each other.
 
# function to check if two numbers
# are equal after bit rotation
def isRotation(x, y) :
     
    # x64 has concatenation of x
    # with itself.
    x64 = x | (x << 32)
     
    while (x64 >= y) :
         
        # comparing only last 32 bits
        if ((x64) == y) :
            return True
 
        # right shift by 1 unit
        x64 >>= 1
 
    return False
 
# Driver Code
if __name__ == "__main__" :
 
    x = 122
    y = 2147483678
     
    if (isRotation(x, y) == False) :
        print("yes")
    else :
        print("no")
 
# This code is contributed by Ryuga

// C# program to check if two numbers
// are bit rotations of each other.
using System;
 
class GFG
{
 
// function to check if two numbers
// are equal after bit rotation
static bool isRotation(long x, long y)
{
    // x64 has concatenation of
    // x with itself.
    long x64 = x | (x << 32);
 
    while (x64 >= y)
    {
        // comparing only last 32 bits
        if (x64 == y)
        {
            return true;
        }
 
        // right shift by 1 unit
        x64 >>= 1;
    }
    return false;
}
 
// Driver Code
public static void Main()
{
    long x = 122;
    long y = 2147483678L;
 
    if (isRotation(x, y) == false)
    {
        Console.Write("Yes");
    }
    else
    {
        Console.Write("No");
    }
}
}
 
// This code is contributed
// by 29AjayKumar

<?php
// PHP program to check if two
// numbers are bit rotations of
// each other.
 
// function to check if two
// numbers are equal after
// bit rotation
function isRotation($x, $y)
{
    // x64 has concatenation
    // of x with itself.
    $x64 = $x | ($x << 32);
 
    while ($x64 >= $y)
    {
        // comparing only last 32 bits
        if (($x64) == $y)
            return 1;
 
        // right shift by 1 unit
        $x64 >>= 1;
    }
    return -1;
}
 
// Driver Code
$x = 122;
$y = 2147483678;
 
if (isRotation($x, $y))
    echo "yes" ,"\n";
else
    echo "no" ,"\n";
 
// This code is contributed by aj_36
?>

<script>
 
// javascript program to check if two numbers are bit rotations
// of each other.
 
// function to check if two numbers are equal
// after bit rotation
function isRotation(x, y)
{
 
    // x64 has concatenation of x with itself.
    var x64 = x | (x << 32);
    while (x64 >= y)
    {
     
        // comparing only last 32 bits
        if (x64 == y) {
            return true;
        }
 
        // right shift by 1 unit
        x64 >>= 1;
    }
    return false;
}
 
// driver code to test above function
var x = 122;
var y = 2147483678;
 
if (isRotation(x, y) == false) {
    document.write("Yes");
} else {
    document.write("No");
}
 
// This code is contributed by 29AjayKumar
</script>

yes

Complejidad de tiempo: O(logn)
Espacio auxiliar: O(1)

Este artículo es una contribución de Pratik Chhajer . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.