Dado un número, alterne todos los bits después del bit más significativo, incluido el bit más significativo.
Ejemplos:
Input : 10 Output : 5 Binary representation of 10 is 1010 After toggling we get 0101 Input : 5 Output : 2
Podemos alternar un poco haciendo XOR con 1 (Tenga en cuenta que 1 ^ 0 = 1 y 1 ^ 1 = 0). La idea es tomar un número temporal con solo un bit establecido. Uno por uno, mueva el único bit establecido de temperatura a la izquierda y haga XOR con n hasta que cruce el MSB (bit más significativo) de n.
C++
// CPP program to toggle set bits starting
// from MSB
#include<bits/stdc++.h>
using namespace std;
void toggle(int &n)
{
// temporary variable to
// use XOR with one of a n
int temp = 1;
// Run loop until the only
// set bit in temp crosses
// MST of n.
while (temp <= n)
{
// Toggle bit of n
// corresponding to
// current set bit in
// temp.
n = n ^ temp;
// Move set bit to next
// higher position.
temp = temp << 1;
}
}
// Driver code
int main()
{
int n = 10;
toggle(n);
cout << n;
return 0;
}
Java
// Java program to toggle set
// bits starting from MSB
class GFG {
static int toggle(int n) {
// temporary variable to
// use XOR with one of a n
int temp = 1;
// Run loop until the only
// set bit in temp crosses
// MST of n.
while (temp <= n) {
// Toggle bit of n
// corresponding to
// current set bit in
// temp.
n = n ^ temp;
// Move set bit to next
// higher position.
temp = temp << 1;
}
return n;
}
// Driver code
public static void main(String arg[])
{
int n = 10;
n = toggle(n);
System.out.print(n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to toggle # set bits starting # from MSB def toggle(n): # temporary variable to # use XOR with one of a n temp = 1 #Run loop until the only #set bit in temp crosses #MST of n. while (temp <= n): # Toggle bit of n # corresponding to # current set bit in # temp. n = n ^ temp # Move set bit to next # higher position. temp = temp << 1 return n # Driver code n = 10 n=toggle(n) print(n) # This code is contributed # by Anant Agarwal.
C#
// C# program to toggle set
// bits starting from MSB
using System;
class GFG {
// Function to toggle bits
// starting from MSB
static int toggle(int n) {
// temporary variable to
// use XOR with one of a n
int temp = 1;
// Run loop until the only
// set bit in temp crosses
// MST of n.
while (temp <= n) {
// Toggle bit of n
// corresponding to
// current set bit in
// temp.
n = n ^ temp;
// Move set bit to next
// higher position.
temp = temp << 1;
}
return n;
}
// Driver code
public static void Main()
{
int n = 10;
n = toggle(n);
Console.Write(n);
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to toggle set
// bits starting from MSB
function toggle( &$n)
{
// temporary variable to
// use XOR with one of a n
$temp = 1;
// Run loop until the only
// set bit in temp crosses
// MST of n.
while ($temp <= $n)
{
// Toggle bit of n
// corresponding to
// current set bit in
// temp.
$n = $n ^ $temp;
// Move set bit to next
// higher position.
$temp = $temp << 1;
}
}
// Driver code
$n = 10;
toggle($n);
echo $n;
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to toggle set
// bits starting from MSB
function toggle(n)
{
// Temporary variable to
// use XOR with one of a n
let temp = 1;
// Run loop until the only
// set bit in temp crosses
// MST of n.
while (temp <= n)
{
// Toggle bit of n
// corresponding to
// current set bit in
// temp.
n = n ^ temp;
// Move set bit to next
// higher position.
temp = temp << 1;
}
return n;
}
// Driver code
let n = 10;
n = toggle(n);
document.write(n);
// This code is contributed by subham348
</script>
Producción
5
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(1)
La solución anterior se puede optimizar para que funcione en tiempo O(1) bajo el supuesto de que los números se almacenan en 32 bits.
C++
// CPP program to toggle set bits starting
// from MSB
#include<bits/stdc++.h>
using namespace std;
// Returns a number which has all set bits
// starting from MSB of n
int setAllBitsAfterMSB(int n)
{
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n>>1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n>>2;
n |= n>>4;
n |= n>>8;
n |= n>>16;
return n;
}
void toggle(int &n)
{
n = n ^ setAllBitsAfterMSB(n);
}
// Driver code
int main()
{
int n = 10;
toggle(n);
cout << n;
return 0;
}
Java
// Java program to toggle set bits
// starting from MSB
class GFG {
// Returns a number which has all
// set bits starting from MSB of n
static int setAllBitsAfterMSB(int n) {
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n;
}
static int toggle(int n)
{
n = n ^ setAllBitsAfterMSB(n);
return n;
}
// Driver code
public static void main(String arg[])
{
int n = 10;
n = toggle(n);
System.out.print(n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to toggle set bits starting # from MSB # Returns a number which has all set bits # starting from MSB of n def setAllBitsAfterMSB(n): # This makes sure two bits # (From MSB and including MSB) # are set n |= n>>1 # This makes sure 4 bits # (From MSB and including MSB) # are set n |= n>>2 n |= n>>4 n |= n>>8 n |= n>>16 return n def toggle(n): n = n ^ setAllBitsAfterMSB(n) return n #Driver code n = 10 n=toggle(n) print(n) # This code is contributed by Anant Agarwal.
C#
// C# program to toggle set bits
// starting from MSB
using System;
class GFG {
// Returns a number which has all
// set bits starting from MSB of n
static int setAllBitsAfterMSB(int n)
{
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n;
}
static int toggle(int n)
{
n = n ^ setAllBitsAfterMSB(n);
return n;
}
// Driver code
public static void Main()
{
int n = 10;
n = toggle(n);
Console.WriteLine(n);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to toggle set
// bits starting from MSB
// Returns a number which
// has all set bits starting
// from MSB of n
function setAllBitsAfterMSB($n)
{
// This makes sure two bits
// (From MSB and including MSB)
// are set
$n |= $n >> 1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
$n |= $n >> 2;
$n |= $n >> 4;
$n |= $n >> 8;
$n |= $n >> 16;
return $n;
}
function toggle(&$n)
{
$n = $n ^ setAllBitsAfterMSB($n);
}
// Driver Code
$n = 10;
toggle($n);
echo $n;
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to toggle set bits starting
// from MSB
// Returns a number which has all set bits
// starting from MSB of n
function setAllBitsAfterMSB(n)
{
// This makes sure two bits
// (From MSB and including MSB)
// are set
n |= n>>1;
// This makes sure 4 bits
// (From MSB and including MSB)
// are set
n |= n>>2;
n |= n>>4;
n |= n>>8;
n |= n>>16;
return n;
}
function toggle(n)
{
n = n ^ setAllBitsAfterMSB(n);
return n;
}
// Driver code
let n = 10;
document.write(toggle(n));
</script>
Producción
5
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Gracias a Devanshu Agarwal por sugerir este enfoque.
Otro enfoque:
Para alternar un bit específico, podemos tomar XOR de ese bit con 1.
Por lo tanto, para un número de n bits, podemos construir una máscara binaria de la forma 1111….11111, es decir, se establecen todos los n bits. Esto no es más que 2 n – 1.
La implementación se muestra a continuación:
C++
// CPP program to toggle set bits starting
// from MSB
#include<bits/stdc++.h>
using namespace std;
// Returns a number which has all set bits
// starting from MSB of n
int toggle(int num)
{
//the number of bits is equal to log2num + 1
int n = (int)log2(num) + 1;
//calculating mask
int mask = pow(2, n) - 1;
//toggling bits using xor with mask
return num ^ mask;
}
// Driver code
int main()
{
int num = 10;
cout << toggle(num);
}
//this code is contributed by phasing17
Java
// Java program to toggle set bits starting
// from MSB
import java.util.*;
class GFG {
// Returns a number which has all set bits
// starting from MSB of n
static int toggle(int num)
{
// the number of bits is equal to log2num + 1
int n = (int)(Math.log(num) / Math.log(2)) + 1;
// calculating mask
int mask = (int)Math.pow(2, n) - 1;
// toggling bits using xor with mask
return num ^ mask;
}
// Driver code
public static void main(String[] args)
{
int num = 10;
System.out.println(toggle(num));
}
}
// this code is contributed by phasing17
Python3
# Python3 program to toggle set # bits starting from MSB from math import log # Returns a number which has all set bits # starting from MSB of n def toggle(num): # the number of bits is equal to log2num + 1 n = int(log(num, 2)) + 1 # calculating mask mask = pow(2, n) - 1 # toggling bits using xor with mask return num ^ mask # Driver code num = 10 print(toggle(num)) # This code is contributed by phasing17
C#
// C# program to toggle set bits starting
// from MSB
using System;
class GFG {
// Returns a number which has all set bits
// starting from MSB of n
static int toggle(int num)
{
// the number of bits is equal to log2num + 1
int n = (int)(Math.Log(num) / Math.Log(2)) + 1;
// calculating mask
int mask = (int)Math.Pow(2, n) - 1;
// toggling bits using xor with mask
return num ^ mask;
}
// Driver code
public static void Main(string[] args)
{
int num = 10;
Console.WriteLine(toggle(num));
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to toggle set
// bits starting from MSB
// Returns a number which has all set bits
// starting from MSB of n
function toggle(num)
{
// the number of bits is equal to log2num + 1
let n = Math.floor((Math.log(num) / Math.log(2)) + 1);
// calculating mask
let mask = Math.pow(2, n) - 1;
// toggling bits using xor with mask
return num ^ mask;
}
// Driver code
let num = 10;
console.log(toggle(num));
// this code is contributed by phasing17
Producción
5
Complejidad de tiempo : O (logn)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Devanshu Agarwal . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA