Dado un entero no negativo n. El problema es invertir los bits de n e imprimir el número obtenido tras invertir los bits. Tenga en cuenta que la representación binaria real del número se está considerando para invertir los bits, no se están considerando los 0 iniciales.
Ejemplos:
Input : 11
Output : 4
(11)10 = (1011)[2]
After inverting the bits, we get:
(0100)2 = (4)10.
Input : 10
Output : 5
(10)10 = (1010)2.
After reversing the bits we get:
(0101)2 = (101)2
= (5)10.
Método 1 (usando operadores bit a bit)
Requisito previo: alternar k-ésimo bit de un número
C++
// CPP program to invert actual bits
// of a number.
#include <bits/stdc++.h>
using namespace std;
void invertBits(int num)
{
// calculating number of bits
// in the number
int x = log2(num) + 1;
// Inverting the bits one by one
for (int i = 0; i < x; i++)
num = (num ^ (1 << i));
cout << num;
}
// Driver code
int main()
{
int num = 11;
invertBits(num);
return 0;
}
Java
// Java program to invert
// actual bits of a number.
import java.io.*;
class GFG
{
static void invertBits(int num)
{
// calculating number of
// bits in the number
int x = (int)(Math.log(num) /
Math.log(2)) + 1;
// Inverting the
// bits one by one
for (int i = 0; i < x; i++)
num = (num ^ (1 << i));
System.out.println(num);
}
// Driver code
public static void main (String[] args)
{
int num = 11;
invertBits(num);
}
}
// This code is contributed
// by Anuj_67
Python3
# Python3 program to invert actual # bits of a number. import math def invertBits(num): # calculating number of bits # in the number x = int(math.log2(num)) + 1 # Inverting the bits one by one for i in range(x): num = (num ^ (1 << i)) print(num) # Driver Code num = 11 invertBits(num) # This code is contributed # by Rituraj Jain
C#
// C# program to invert
// actual bits of a number.
using System;
class GFG
{
static void invertBits(int num)
{
// calculating number of
// bits in the number
int x = (int)(Math.Log(num) /
Math.Log(2)) + 1;
// Inverting the
// bits one by one
for (int i = 0; i < x; i++)
num = (num ^ (1 << i));
Console.WriteLine(num);
}
// Driver code
public static void Main ()
{
int num = 11;
invertBits(num);
}
}
// This code is contributed
// by Anuj_67
PHP
<?php
// PHP program to invert actual bits
// of a number.
function invertBits( $num)
{
// calculating number of bits
// in the number
$x = log($num) + 1;
// Inverting the bits one by one
for($i = 0; $i < $x; $i++)
$num = ($num ^ (1 << $i));
echo $num;
}
// Driver code
$num = 11;
invertBits($num);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to invert
// actual bits of a number.
function invertBits(num)
{
// calculating number of
// bits in the number
let x =
parseInt(Math.log(num) / Math.log(2), 10) + 1;
// Inverting the
// bits one by one
for (let i = 0; i < x; i++)
num = (num ^ (1 << i));
document.write(num);
}
let num = 11;
invertBits(num);
</script>
Producción
4
Complejidad temporal : O(log n)
Espacio auxiliar : O(1)
Método 2 (usando Bitset )
Aquí usamos flip() de bitset para invertir los bits del número, para evitar cambiar los ceros iniciales en la representación binaria del número, hemos calculado el número de bits en la representación binaria y volteó solo los bits reales del número. Hemos usado to_ulong() para convertir un conjunto de bits en un número.
C++
// CPP program to invert actual bits
// of a number.
#include <bits/stdc++.h>
using namespace std;
void invertBits(int num)
{
// calculating number of bits
// in the number
int x = log2(num) + 1;
// Considering number to be 32 bit integer;
bitset<32> b(num);
// reversing the bits one by one
for (int i = 0; i < x; i++)
b.flip(i);
// converting bitset to number
cout << b.to_ulong();
}
// Driver code
int main()
{
int num = 11;
invertBits(num);
return 0;
}
Java
// Java program to invert actual
// bits of a number.
class GFG
{
static void invertBits(int num)
{
// calculating number of
// bits in the number
int x = (int)(Math.log(num) /
Math.log(2)) + 1;
// Inverting the bits
// one by one
for (int i = 0; i < x; i++)
num = (num ^ (1 << i));
System.out.print(num);
}
// Driver code
public static void main(String[] args)
{
int num = 11;
invertBits(num);
}
}
// This code is contributed by Mukul Singh
Python 3
# Python 3 program to invert actual # bits of a number. import math def invertBits(num): # calculating number of # bits in the number x = int(math.log(num, 2.0) + 1); # Inverting the bits # one by one for i in range(0, x): num = (num ^ (1 << i)); print(num); # Driver code num = 11; invertBits(num); # This code is contributed # by Akanksha Rai
C#
// C# program to invert actual
// bits of a number.
using System;
class GFG
{
static void invertBits(int num)
{
// calculating number of
// bits in the number
int x = (int)Math.Log(num, 2) + 1;
// Inverting the bits
// one by one
for (int i = 0; i < x; i++)
num = (num ^ (1 << i));
Console.Write(num);
}
// Driver code
static void Main()
{
int num = 11;
invertBits(num);
}
}
// This code is contributed by Anuj_67
PHP
<?php
// PHP program to invert actual
// bits of a number.
function invertBits($num)
{
// calculating number of
// bits in the number
$x = log($num) + 1;
// Inverting the bits
// one by one
for ($i = 0; $i < $x; $i++)
$num = ($num ^ (1 << $i));
echo $num;
}
// Driver code
$num = 11;
invertBits($num);
// This code is contributed
// by ajit
?>
Javascript
<script>
// Javascript program to invert actual bits of a number.
function invertBits(num)
{
// calculating number of
// bits in the number
let x = Math.log(num, 2) + 1;
// Inverting the bits
// one by one
for (let i = 0; i < x; i++)
num = (num ^ (1 << i));
document.write(num);
}
let num = 11;
invertBits(num);
</script>
Producción
4
Complejidad temporal: O(log n)
Espacio auxiliar: O(1)
Método 3 (usando máscara de bits):
Aquí, crearemos una máscara configurando todos los bits de MSB (incluido MSB) y luego tomaremos XOR con el número original
C++
// CPP program to invert actual bits
// of a number.
#include <bits/stdc++.h>
using namespace std;
void invertBits(int num)
{
// calculating the mask
int x = num; // say num = 100000
x |= x >> 1; // 100000 | 010000 = 110000
x |= x >> 2; // 110000 | 001100 = 111100
x |= x >> 4; // 111100 | 000011 = 111111
x |= x >> 8; // 111111 | 000000 = 111111
x |= x >> 16; // 111111 | 000000 = 111111
cout << (num ^ x); // 100000 | 111111 = 011111
}
// Driver code
int main()
{
int num = 11;
invertBits(num);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static void invertBits(int num) {
//base case
if(num == 0)
{
System.out.println(1);
return;
}
// calculating the mask
int x = num; // say num = 100000
x |= x >> 1; // 100000 | 010000 = 110000
x |= x >> 2; // 110000 | 001100 = 111100
x |= x >> 4; // 111100 | 000011 = 111111
x |= x >> 8; // 111111 | 000000 = 111111
x |= x >> 16; // 111111 | 000000 = 111111
System.out.println(num ^ x); // 100000 | 111111 = 011111
}
// Driver code
public static void main(String[] args)
{
int num = 11;
invertBits(num);
}
}
// This code is contributed by lapimpale@
C#
// C# code to implement the approach
using System;
class GFG {
public static void invertBits(int num)
{
// base case
if (num == 0) {
Console.WriteLine(1);
return;
}
// calculating the mask
int x = num; // say num = 100000
x |= x >> 1; // 100000 | 010000 = 110000
x |= x >> 2; // 110000 | 001100 = 111100
x |= x >> 4; // 111100 | 000011 = 111111
x |= x >> 8; // 111111 | 000000 = 111111
x |= x >> 16; // 111111 | 000000 = 111111
Console.WriteLine(num
^ x); // 100000 | 111111 = 011111
}
// Driver code
public static void Main(string[] args)
{
int num = 11;
invertBits(num);
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to invert actual bits
// of a number.
function invertBits(num)
{
// calculating the mask
let x = num; // say num = 100000
x |= x >> 1; // 100000 | 010000 = 110000
x |= x >> 2; // 110000 | 001100 = 111100
x |= x >> 4; // 111100 | 000011 = 111111
x |= x >> 8; // 111111 | 000000 = 111111
x |= x >> 16; // 111111 | 000000 = 111111
console.log(num ^ x); // 100000 | 111111 = 011111
}
// Driver code
let num = 11;
invertBits(num);
// This code is contributed by phasing17
Producción
4
Complejidad del tiempo: O(1)
Espacio auxiliar: O(1)
Método 4 (Extraer solo los bits relevantes usando log y XOR)
El número invertido se puede obtener de manera eficiente mediante:
1. Obtener la cantidad de bits usando log2
2. Tomando XOR del número y 2 numOfBits – 1
C++
// CPP program to invert actual bits
// of a number.
#include <bits/stdc++.h>
using namespace std;
void invertBits(int num)
{
// Find number of bits in the given integer
int numOfBits = (int)log2(num) + 1;
// invert the number by taking
// xor of n and (2 raised to numOfBits) - 1
cout << (((1 << numOfBits) - 1) ^ num);
}
// Driver code
int main()
{
int num = 11;
//Function Call
invertBits(num);
return 0;
}
//This code is contributed by phasing17
Producción
4
Complejidad del tiempo : O(1)
Espacio auxiliar: O(1)