Bits inversos usando la tabla de búsqueda en tiempo O(1)

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

Input : n = 1
Output : 2147483648  
On a machine with size of unsigned
bit as 32. Reverse of 0....001 is
100....0.

Input : n = 2147483648
Output : 1       

En la publicación anterior , habíamos visto dos métodos que resolvieron este problema en tiempo O (n) y O (logn). Aquí resolvemos este problema en tiempo O(1) usando la tabla de búsqueda. Es difícil invertir los 32 bits (asumiendo que esto es del tamaño de int) de una sola vez usando la tabla de búsqueda («porque no es factible crear una tabla de búsqueda de tamaño 2 ³² -1″). Entonces dividimos 32 bits en 8 bits de fragmentos (tabla de búsqueda de tamaño 2 ⁸ -1 «0-255»). Tabla de búsquedaen el cuento de búsqueda almacenaremos el reverso de cada número que está en un rango (0-255) LookupTable[0] = 0 | binario 00000000 Reverse 00000000 LookupTable[1] = 128 | binario 00000001 inverso 10000000 LookupTable[2] = 64 | binario 00000010 inverso 01000000 LookupTanle[3] = 192 | binario 00000011 inverso 11000000 LookupTable[4] = 32 | binario 00000100 inverso 00100000 y así sucesivamente… hasta la tabla de búsqueda[255]. Tomemos un ejemplo de cómo funciona la tabla de búsqueda. let número = 12456 en binario = 00000000000000000011000010101000

Split it into 8 bits chunks  :  00000000 | 00000000 | 00110000 | 10101000
         in decimal          :     0          0          48       168
reverse each chunks using lookup table :
Lookuptable[ 0 ] = 0  | in binary 00000000
Lookuptable[48 ] = 12 | in binary 00001100
Lookuptable[168] = 21 | in binary 00010101
 
Now Binary :  
00000000 | 00000000 | 00001100 | 00010101

Binary chunks after rearrangement : 
00010101 | 00001100 | 00000000 | 00000000   
  
Reverse of 12456 is 353107968  

// CPP program to reverse bits using lookup table.
 
#include <bits/stdc++.h>
using namespace std;
 
// Generate a lookup table for 32bit operating system
// using macro
 
#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
 
#define R4(n)                                              \
    R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
 
#define R6(n)                                              \
    R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
 
// Lookup table that store the reverse of each table
 
unsigned int lookuptable[256]
    = { R6(0), R6(2), R6(1), R6(3) };
 
/* Function to reverse bits of num */
 
int reverseBits(unsigned int num)
{
    int reverse_num = 0; // Reverse and then rearrange
    // first chunk of 8 bits from right
    reverse_num = lookuptable[num & 0xff] << 24 |
                  // second chunk of 8 bits from right
                  lookuptable[(num >> 8) & 0xff] << 16
                  | lookuptable[(num >> 16) & 0xff] << 8
                  | lookuptable[(num >> 24) & 0xff];
    return reverse_num;
} // driver program to test above function
int main()
{
    int x = 12456;
    printf("%u", reverseBits(x));
    return 0;
}

// Java program to reverse bits using lookup table.
import java.util.*;
 
class GFG {
 
    // Lookup table that store the reverse of each table
    public static ArrayList<Integer> lookuptable
        = new ArrayList<Integer>();
 
    // Generate a lookup table for 32bit operating system
    // using macro
    public static void R2(int n)
    {
        lookuptable.add(n);
        lookuptable.add(n + 2 * 64);
        lookuptable.add(n + 1 * 64);
        lookuptable.add(n + 3 * 64);
    }
 
    public static void R4(int n)
    {
        R2(n);
        R2(n + 2 * 16);
        R2(n + 1 * 16);
        R2(n + 3 * 16);
    }
 
    public static void R6(int n)
    {
        R4(n);
        R4(n + 2 * 4);
        R4(n + 1 * 4);
        R4(n + 3 * 4);
    }
 
    // Function to reverse bits of num
    public static int reverseBits(int num)
    {
 
        int reverse_num = 0;
 
        // Reverse and then rearrange
 
        // first chunk of 8 bits from right
        reverse_num
            = lookuptable.get(num & 0xff) << 24 |
              // second chunk of 8 bits from right
              lookuptable.get((num >> 8) & 0xff) << 16
              | lookuptable.get((num >> 16) & 0xff) << 8
              | lookuptable.get((num >> 24) & 0xff);
        return reverse_num;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        R6(0);
        R6(2);
        R6(1);
        R6(3);
        // Driver program to test above function
        int x = 12456;
        System.out.println(reverseBits(x));
    }
}
 
// This code is contributed by phasing17

#Python3 program to reverse bits using lookup table.
 
# Lookup table that store the reverse of each table
lookuptable = []
  
# Generate a lookup table for 32bit operating system
# using macro
def R2(n):
    return lookuptable.extend([n,     n + 2*64,     n + 1*64,     n + 3*64])
 
def R4(n):
    return R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
 
def R6(n):
    return R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
 
lookuptable.extend([R6(0), R6(2), R6(1), R6(3)])
 
# Function to reverse bits of num
def reverseBits(num):
 
    reverse_num = 0
 
    # Reverse and then rearrange
 
    # first chunk of 8 bits from right
    reverse_num = lookuptable[num & 0xff ]<<24  | lookuptable[ (num >> 8) & 0xff ]<<16 |lookuptable[ (num >> 16 )& 0xff ]<< 8 | lookuptable[ (num >>24 ) & 0xff ]
   
    return reverse_num
 
# Driver program to test above function
x = 12456
print(reverseBits(x))
 
 
#This code is contributed by phasing17

// C# program to reverse bits using lookup table.
 
using System;
using System.Collections.Generic;
 
class GFG {
 
  // Lookup table that store the reverse of each table
  public static List<int> lookuptable = new List<int>();
 
  // Generate a lookup table for 32bit operating system
  // using macro
  public static void R2(int n)
  {
    lookuptable.Add(n);
    lookuptable.Add(n + 2 * 64);
    lookuptable.Add(n + 1 * 64);
    lookuptable.Add(n + 3 * 64);
  }
 
  public static void R4(int n)
  {
    R2(n);
    R2(n + 2 * 16);
    R2(n + 1 * 16);
    R2(n + 3 * 16);
  }
 
  public static void R6(int n)
  {
    R4(n);
    R4(n + 2 * 4);
    R4(n + 1 * 4);
    R4(n + 3 * 4);
  }
 
  // Function to reverse bits of num
  public static int reverseBits(int num)
  {
 
    int reverse_num = 0;
 
    // Reverse and then rearrange
 
    // first chunk of 8 bits from right
    reverse_num = lookuptable[num & 0xff] << 24 |
      // second chunk of 8 bits from right
      lookuptable[(num >> 8) & 0xff] << 16
      | lookuptable[(num >> 16) & 0xff] << 8
      | lookuptable[(num >> 24) & 0xff];
    return reverse_num;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    R6(0);
    R6(2);
    R6(1);
    R6(3);
    int x = 12456;
 
    // Function call
    Console.WriteLine(reverseBits(x));
  }
}
 
// This code is contributed by phasing17

Producción:

353107968

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)