Escribir un programa en C eficiente para invertir los bits de un número

Dado un entero sin signo, invierta todos sus bits y devuelva el número con los bits invertidos.

Entrada: n = 1
Salida: 2147483648  
Explicación: en una máquina con un tamaño de bit sin signo de 32. El reverso de 0….001 es 100….0.

Entrada: n = 2147483648
Salida: 1                            

Método 1: simple: recorrer todos los bits de un número entero. Si se establece un bit en la i-ésima posición en el i/p no. luego establezca el bit en (NO_OF_BITS – 1) – i en o/p. Donde NO_OF_BITS es el número de bits presentes en el número dado.  

A continuación se muestra la implementación del enfoque anterior:

// C code to implement the approach
#include <stdio.h>
 
// Function to reverse bits of num
unsigned int reverseBits(unsigned int num)
{
    unsigned int NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0;
    int i;
    for (i = 0; i < NO_OF_BITS; i++) {
        if ((num & (1 << i)))
            reverse_num |= 1 << ((NO_OF_BITS - 1) - i);
    }
    return reverse_num;
}
 
// Driver code
int main()
{
    unsigned int x = 2;
    printf("%u", reverseBits(x));
    getchar();
}

1073741824

Complejidad temporal: O(Log n). La complejidad del tiempo sería Log (num) ya que hay bits de log (num) en un número binario «num» y estamos recorriendo todos los bits.
Espacio auxiliar: O(1)

Método 2 – Estándar: La idea es seguir colocando bits fijos de num en reverse_num hasta que num se convierta en cero. Después de que num se convierta en cero , cambie los bits restantes de reverse_num . Deje que num se almacene usando 8 bits y num sea 00000110 . Después del ciclo obtendrás reverse_num como 00000011 . Ahora necesita desplazar a la izquierda número_reverso 5 veces más y obtendrá el reverso exacto 01100000. 

A continuación se muestra la implementación del enfoque anterior:

// C code to implement the approach
#include <stdio.h>
 
// Function to reverse bits of num
unsigned int reverseBits(unsigned int num)
{
    unsigned int count = sizeof(num) * 8 - 1;
    unsigned int reverse_num = num;
 
    num >>= 1;
    while (num) {
        reverse_num <<= 1;
        reverse_num |= num & 1;
        num >>= 1;
        count--;
    }
    reverse_num <<= count;
    return reverse_num;
}
 
// Driver's code
int main()
{
    unsigned int x = 1;
    printf("%u", reverseBits(x));
    getchar();
}

2147483648

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

 Método 3: tabla de búsqueda: podemos invertir los bits de un número en O (1) si conocemos el tamaño del número. Podemos implementarlo usando la tabla de búsqueda. Consulte Bits inversos utilizando la tabla de búsqueda en tiempo O(1) para obtener más detalles. 

Fuente: https://graphics.stanford.edu/~seander/bithacks.html