Programa para invertir bits de un número Eficientemente

Dado un entero no negativo N. La tarea es invertir los bits del número N e imprimir el equivalente decimal del número obtenido después de invertir los bits. 
Nota : No se están considerando los ceros iniciales.
Ejemplos: 
 

Input : 11
Output : 4
(11)10 = (1011)2
After inverting the bits, we get:
(0100)2 = (4)10.

Input : 20
Output : 11
(20)10 = (10100)2.
After inverting the bits, we get:
(01011)2 = (11)10.

Un problema similar ya se trata en Invertir bits reales de un número .
En este artículo, se analiza un enfoque eficiente que utiliza operadores bit a bit. A continuación se muestra el algoritmo paso a paso para resolver el problema:
 

1. Calcular el número total de bits en el número dado. Esto se puede hacer calculando:

   X = log2N

   Donde N es el número dado y X es el número total de bits de N.

2. El siguiente paso es generar un número con X bits y todos los bits configurados. Es decir, 11111….X-veces . Esto se puede hacer calculando:

   Step-1: M = 1 << X
   Step-2: M = M | (M-1)

   Donde M es el número de bits X requerido con todos los bits establecidos.

3. El paso final es calcular el XOR bit a bit de M con N, que será nuestra respuesta.

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

// C++ program to invert actual bits
// of a number.
#include <bits/stdc++.h>
  
using namespace std;
  
// Function to invert bits of a number
int invertBits(int n)
{
    // Calculate number of bits of N-1;
    int x = log2(n) ;
  
    int m = 1 << x;
  
    m = m | m - 1;
  
    n = n ^ m;
  
    return n;
}
  
// Driver code
int main()
{
    int n = 20;
  
    cout << invertBits(n);
  
    return 0;
}

// Java program to invert 
// actual bits of a number. 
import java.util.*;
  
class GFG
{
// Function to invert 
// bits of a number 
static int invertBits(int n) 
{ 
    // Calculate number of bits of N-1; 
    int x = (int)(Math.log(n) / 
                  Math.log(2)) ; 
  
    int m = 1 << x; 
  
    m = m | m - 1; 
  
    n = n ^ m; 
  
    return n; 
} 
  
// Driver code 
public static void main(String[] args) 
{ 
    int n = 20; 
  
    System.out.print(invertBits(n)); 
}
} 
  
// This code is contributed by Smitha

# Python3 program to invert actual
# bits of a number.
import math
  
# Function to invert bits of a number
def invertBits(n):
      
    # Calculate number of bits of N-1
    x = int(math.log(n, 2))
  
    m = 1 << x
  
    m = m | m - 1
  
    n = n ^ m
  
    return n
  
# Driver code
n = 20
  
print(invertBits(n))
  
# This code is contributed 29AjayKumar

// C# program to invert 
// actual bits of a number. 
using System;
  
  
   
public class GFG
{
// Function to invert 
// bits of a number 
static int invertBits(int n) 
{ 
    // Calculate number of bits of N-1; 
    int x = (int)(Math.Log(n) / 
                  Math.Log(2)) ; 
   
    int m = 1 << x; 
   
    m = m | m - 1; 
   
    n = n ^ m; 
   
    return n; 
} 
   
// Driver code 
public static void Main() 
{ 
    int n = 20; 
   
    Console.Write(invertBits(n)); 
}
} 
   
// This code is contributed by Subhadeep

<?php
// PHP program to invert actual 
// bits of a number.
  
// Function to invert bits 
// of a number
function invertBits($n)
{
    // Calculate number of
    // bits of N-1;
    $x = log($n, 2);
  
    $m = 1 << $x;
  
    $m = $m | $m - 1;
  
    $n = $n ^ $m;
  
    return $n;
}
  
// Driver code
$n = 20;
  
echo(invertBits($n));
  
// This code is contributed 
// by mits
?>

<script>
  
// Javascript program to invert actual bits
// of a number.
  
// Function to invert bits of a number
function invertBits(n)
{
    // Calculate number of bits of N-1;
    let x = parseInt(Math.log(n) / Math.log(2)) ;
  
    let m = 1 << x;
  
    m = m | m - 1;
  
    n = n ^ m;
  
    return n;
}
  
// Driver code
    let n = 20;
  
    document.write(invertBits(n));
  
</script>

11

Complejidad de Tiempo : O(log ₂ n) 
Espacio Auxiliar : O(1)