Dado un número x y dos posiciones (desde el lado derecho) en la representación binaria de x, escriba una función que intercambie n bits en las dos posiciones dadas y devuelva el resultado. También se da que los dos conjuntos de bits no se superponen.
Método 1
Sean p1 y p2 las dos posiciones dadas.
Ejemplo 1
Input: x = 47 (00101111) p1 = 1 (Start from the second bit from the right side) p2 = 5 (Start from the 6th bit from the right side) n = 3 (No of bits to be swapped) Output: 227 (11100011) The 3 bits starting from the second bit (from the right side) are swapped with 3 bits starting from 6th position (from the right side)
Ejemplo 2
Input: x = 28 (11100) p1 = 0 (Start from first bit from right side) p2 = 3 (Start from 4th bit from right side) n = 2 (No of bits to be swapped) Output: 7 (00111) The 2 bits starting from 0th position (from right side) are swapped with 2 bits starting from 4th position (from right side)
Solución
Necesitamos intercambiar dos conjuntos de bits. XOR se puede usar de manera similar a como se usa para intercambiar 2 números . El siguiente es el algoritmo.
1) Move all bits of the first set to the rightmost side set1 = (x >> p1) & ((1U << n) - 1) Here the expression (1U << n) - 1 gives a number that contains last n bits set and other bits as 0. We do & with this expression so that bits other than the last n bits become 0. 2) Move all bits of second set to rightmost side set2 = (x >> p2) & ((1U << n) - 1) 3) XOR the two sets of bits xor = (set1 ^ set2) 4) Put the xor bits back to their original positions. xor = (xor << p1) | (xor << p2) 5) Finally, XOR the xor with original number so that the two sets are swapped. result = x ^ xor
Implementación:
C++
// C++ Program to swap bits
// in a given number
#include <bits/stdc++.h>
using namespace std;
int swapBits(unsigned int x, unsigned int p1,
unsigned int p2, unsigned int n)
{
/* Move all bits of first set to rightmost side */
unsigned int set1 = (x >> p1) & ((1U << n) - 1);
/* Move all bits of second set to rightmost side */
unsigned int set2 = (x >> p2) & ((1U << n) - 1);
/* Xor the two sets */
unsigned int Xor = (set1 ^ set2);
/* Put the Xor bits back to their original positions */
Xor = (Xor << p1) | (Xor << p2);
/* Xor the 'Xor' with the original number so that the
two sets are swapped */
unsigned int result = x ^ Xor;
return result;
}
/* Driver code*/
int main()
{
int res = swapBits(28, 0, 3, 2);
cout << "Result = " << res;
return 0;
}
// This code is contributed by rathbhupendra
C
// C Program to swap bits
// in a given number
#include <stdio.h>
int swapBits(unsigned int x, unsigned int p1, unsigned int p2, unsigned int n)
{
/* Move all bits of first set to rightmost side */
unsigned int set1 = (x >> p1) & ((1U << n) - 1);
/* Move all bits of second set to rightmost side */
unsigned int set2 = (x >> p2) & ((1U << n) - 1);
/* XOR the two sets */
unsigned int xor = (set1 ^ set2);
/* Put the xor bits back to their original positions */
xor = (xor << p1) | (xor << p2);
/* XOR the 'xor' with the original number so that the
two sets are swapped */
unsigned int result = x ^ xor;
return result;
}
/* Driver program to test above function*/
int main()
{
int res = swapBits(28, 0, 3, 2);
printf("\nResult = %d ", res);
return 0;
}
Java
// Java Program to swap bits
// in a given number
class GFG {
static int swapBits(int x, int p1, int p2, int n)
{
// Move all bits of first set
// to rightmost side
int set1 = (x >> p1) & ((1 << n) - 1);
// Move all bits of second set
// to rightmost side
int set2 = (x >> p2) & ((1 << n) - 1);
// XOR the two sets
int xor = (set1 ^ set2);
// Put the xor bits back to
// their original positions
xor = (xor << p1) | (xor << p2);
// XOR the 'xor' with the original number
// so that the two sets are swapped
int result = x ^ xor;
return result;
}
// Driver program
public static void main(String[] args)
{
int res = swapBits(28, 0, 3, 2);
System.out.println("Result = " + res);
}
}
// This code is contributed by prerna saini.
Python3
# Python program to
# swap bits in a given number
def swapBits(x, p1, p2, n):
# Move all bits of first
# set to rightmost side
set1 = (x >> p1) & ((1<< n) - 1)
# Move all bits of second
# set to rightmost side
set2 = (x >> p2) & ((1 << n) - 1)
# XOR the two sets
xor = (set1 ^ set2)
# Put the xor bits back
# to their original positions
xor = (xor << p1) | (xor << p2)
# XOR the 'xor' with the
# original number so that the
# two sets are swapped
result = x ^ xor
return result
# Driver code
res = swapBits(28, 0, 3, 2)
print("Result =", res)
# This code is contributed
# by Anant Agarwal.
C#
// C# Program to swap bits
// in a given number
using System;
class GFG {
static int swapBits(int x, int p1, int p2, int n)
{
// Move all bits of first
// set to rightmost side
int set1 = (x >> p1) & ((1 << n) - 1);
// Move all bits of second set
// set to rightmost side
int set2 = (x >> p2) & ((1 << n) - 1);
// XOR the two sets
int xor = (set1 ^ set2);
// Put the xor bits back to
// their original positions
xor = (xor << p1) | (xor << p2);
// XOR the 'xor' with the original number
// so that the two sets are swapped
int result = x ^ xor;
return result;
}
// Driver program
public static void Main()
{
int res = swapBits(28, 0, 3, 2);
Console.WriteLine("Result = " + res);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to swap bits
// in a given number
// function returns
// the swapped bits
function swapBits($x, $p1, $p2, $n)
{
// Move all bits of first
// set to rightmost side
$set1 = ($x >> $p1) &
((1 << $n) - 1);
// Move all bits of second
// set to rightmost side
$set2 = ($x >> $p2) &
((1 << $n) - 1);
// XOR the two sets
$xor = ($set1 ^ $set2);
// Put the xor bits back to
// their original positions
$xor = ($xor << $p1) |
($xor << $p2);
// XOR the 'xor' with the
// original number so that
// the two sets are swapped
$result = $x ^ $xor;
return $result;
}
// Driver Code
$res = swapBits(28, 0, 3, 2);
echo "\nResult = ", $res;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript Program to swap bits
// in a given number
function swapBits(x, p1, p2, n)
{
// Move all bits of first set
// to rightmost side
let set1 = (x >> p1) & ((1 << n) - 1);
// Move all bits of second set
// to rightmost side
let set2 = (x >> p2) & ((1 << n) - 1);
// XOR the two sets
let xor = (set1 ^ set2);
// Put the xor bits back to
// their original positions
xor = (xor << p1) | (xor << p2);
// XOR the 'xor' with the original number
// so that the two sets are swapped
let result = x ^ xor;
return result;
}
// Driver Code
let res = swapBits(28, 0, 3, 2);
document.write("Result = " + res);
</script>
Producción
Result = 7
Complejidad de tiempo: O(1), ya que estamos usando operaciones de tiempo constante.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Lo que sigue es una implementación más corta de la misma lógica.
C++
// C++ program of th above approach
#include <bits/stdc++.h>
using namespace std;
int swapBits(int x, int p1, int p2, int n)
{
/* xor contains xor of two sets */
int xor = ((x >> p1) ^ (x >> p2)) & ((1U << n) - 1);
/* To swap two sets, we need to again XOR the xor with
* original sets */
return x ^ ((xor << p1) | (xor << p2));
}
// This code is contributed by splevel62.
C
int swapBits(unsigned int x, unsigned int p1, unsigned int p2, unsigned int n)
{
/* xor contains xor of two sets */
unsigned int xor = ((x >> p1) ^ (x >> p2)) & ((1U << n) - 1);
/* To swap two sets, we need to again XOR the xor with original sets */
return x ^ ( (xor << p1) | (xor << p2));
}
Java
static int swapBits(int x, int p1, int p2, int n)
{
/* xor contains xor of two sets */
int xor = ((x >> p1) ^ (x >> p2)) & ((1U << n) - 1);
/* To swap two sets, we need to again XOR the xor with
* original sets */
return x ^ ((xor << p1) | (xor << p2));
}
// This code is contributed by subhammahato348.
Python3
# Python code to implement the approach def swapBits(x, p1, p2, n) : # xor contains xor of two sets xor = (((x >> p1) ^ (x >> p2)) & ((1 << n) - 1)) # To swap two sets, we need to again XOR the xor with original sets return x ^ ( (xor << p1) | (xor << p2)) # This code is contributed by sanjoy_62.
C#
static int swapBits(int x, int p1, int p2, int n)
{
/* xor contains xor of two sets */
int xor = ((x >> p1) ^ (x >> p2)) & ((1U << n) - 1);
/* To swap two sets, we need to again XOR the xor with
* original sets */
return x ^ ((xor << p1) | (xor << p2));
}
// This code is contributed by subhammahato348.
Javascript
<script>
// JavaScript code for the above approach
function swapBits(x, p1, p2, n)
{
/* xor contains xor of two sets */
let xor = ((x >> p1) ^ (x >> p2)) & ((1 << n) - 1);
/* To swap two sets, we need to again XOR the xor with
* original sets */
return x ^ ((xor << p1) | (xor << p2));
}
// This code is contributed by avijitmondal1998.
</script>
Complejidad de tiempo: O(1), ya que estamos usando operaciones de tiempo constante.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Método 2:
esta solución se centra en calcular los valores de los bits que se intercambiarán mediante la puerta AND. Luego podemos activar/desactivar esos bits en función de si los bits se van a intercambiar. Para el número de bits a intercambiar (n) –
- Calcular shift1 = El valor después de configurar el bit en la posición p1 a 1
- Calcular shift2 = El valor después de configurar el bit en la posición p2 a 1
- value1 = Número para verificar si num en la posición p1 está configurado o no.
- value2 = Número para verificar si el número en la posición p2 está configurado o no.
- Si valor1 y valor2 son diferentes es cuando tenemos que intercambiar los bits.
Ejemplo:
[28 0 3 2] num=28 (11100) p1=0 p2=3 n=2 Given = 11100 Required output = 00111 i.e. (00)1(11) msb 2 bits replaced with lsb 2 bits n=2 p1=0, p2=3 shift1= 1, shift2= 1000 value1= 0, value2= 1000 After swap num= 10101 n=3 p1=1, p2=4 shift1= 10, shift2= 10000 value1= 0, value2= 10000 After swap num= 00111
Implementación
C++
#include <iostream>
using namespace std;
int swapBits(unsigned int num, unsigned int p1,
unsigned int p2, unsigned int n)
{
int shift1, shift2, value1, value2;
while (n--) {
// Setting bit at p1 position to 1
shift1 = 1 << p1;
// Setting bit at p2 position to 1
shift2 = 1 << p2;
// value1 and value2 will have 0 if num
// at the respective positions - p1 and p2 is 0.
value1 = ((num & shift1));
value2 = ((num & shift2));
// check if value1 and value2 are different
// i.e. at one position bit is set and other it is not
if ((!value1 && value2) || (!value2 && value1)) {
// if bit at p1 position is set
if (value1) {
// unset bit at p1 position
num = num & (~shift1);
// set bit at p2 position
num = num | shift2;
}
// if bit at p2 position is set
else {
// set bit at p2 position
num = num & (~shift2);
// unset bit at p2 position
num = num | shift1;
}
}
p1++;
p2++;
}
// return final result
return num;
}
/* Driver code*/
int main()
{
int res = swapBits(28, 0, 3, 2);
cout << "Result = " << res;
return 0;
}
Java
class GFG
{
static int swapBits(int num, int p1, int p2, int n)
{
int shift1, shift2, value1, value2;
while (n-- > 0)
{
// Setting bit at p1 position to 1
shift1 = 1 << p1;
// Setting bit at p2 position to 1
shift2 = 1 << p2;
// value1 and value2 will have 0 if num
// at the respective positions - p1 and p2 is 0.
value1 = ((num & shift1));
value2 = ((num & shift2));
// check if value1 and value2 are different
// i.e. at one position bit is set and other it is not
if ((value1 == 0 && value2 != 0) ||
(value2 == 0 && value1 != 0))
{
// if bit at p1 position is set
if (value1 != 0)
{
// unset bit at p1 position
num = num & (~shift1);
// set bit at p2 position
num = num | shift2;
}
// if bit at p2 position is set
else
{
// set bit at p2 position
num = num & (~shift2);
// unset bit at p2 position
num = num | shift1;
}
}
p1++;
p2++;
}
// return final result
return num;
}
// Driver code
public static void main(String[] args)
{
int res = swapBits(28, 0, 3, 2);
System.out.println("Result = " + res);
}
}
// This code is contributed by divyeshrabadiya07
Python3
def swapBits(num, p1, p2, n):
shift1 = 0
shift2 = 0
value1 = 0
value2 = 0
while(n > 0):
# Setting bit at p1 position to 1
shift1 = 1 << p1
# Setting bit at p2 position to 1
shift2 = 1 << p2
# value1 and value2 will have 0 if num
# at the respective positions - p1 and p2 is 0.
value1 = ((num & shift1))
value2 = ((num & shift2))
# check if value1 and value2 are different
# i.e. at one position bit is set and other it is not
if((value1 == 0 and value2 != 0) or (value2 == 0 and value1 != 0)):
# if bit at p1 position is set
if(value1 != 0):
# unset bit at p1 position
num = num & (~shift1)
# set bit at p2 position
num = num | shift2
# if bit at p2 position is set
else:
# set bit at p2 position
num = num & (~shift2)
# unset bit at p2 position
num = num | shift1
p1 += 1
p2 += 1
n -= 1
# return final result
return num
# Driver code
res = swapBits(28, 0, 3, 2)
print("Result =", res)
# This code is contributed by avanitrachhadiya2155
C#
using System;
class GFG
{
static int swapBits(int num, int p1,
int p2, int n)
{
int shift1, shift2, value1, value2;
while (n-- > 0)
{
// Setting bit at p1 position to 1
shift1 = 1 << p1;
// Setting bit at p2 position to 1
shift2 = 1 << p2;
// value1 and value2 will have 0 if num
// at the respective positions - p1 and p2 is 0.
value1 = ((num & shift1));
value2 = ((num & shift2));
// check if value1 and value2 are different
// i.e. at one position bit is set and other it is not
if ((value1 == 0 && value2 != 0) || (value2 == 0 && value1 != 0))
{
// if bit at p1 position is set
if (value1 != 0)
{
// unset bit at p1 position
num = num & (~shift1);
// set bit at p2 position
num = num | shift2;
}
// if bit at p2 position is set
else
{
// set bit at p2 position
num = num & (~shift2);
// unset bit at p2 position
num = num | shift1;
}
}
p1++;
p2++;
}
// return final result
return num;
}
// Driver code
static void Main()
{
int res = swapBits(28, 0, 3, 2);
Console.WriteLine("Result = " + res);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
function swapBits(num, p1, p2, n)
{
let shift1, shift2, value1, value2;
while (n-- > 0)
{
// Setting bit at p1 position to 1
shift1 = 1 << p1;
// Setting bit at p2 position to 1
shift2 = 1 << p2;
// value1 and value2 will have 0 if num
// at the respective positions - p1 and p2 is 0.
value1 = ((num & shift1));
value2 = ((num & shift2));
// Check if value1 and value2 are different
// i.e. at one position bit is set and
// other it is not
if ((value1 == 0 && value2 != 0) ||
(value2 == 0 && value1 != 0))
{
// If bit at p1 position is set
if (value1 != 0)
{
// Unset bit at p1 position
num = num & (~shift1);
// Set bit at p2 position
num = num | shift2;
}
// If bit at p2 position is set
else
{
// Set bit at p2 position
num = num & (~shift2);
// Unset bit at p2 position
num = num | shift1;
}
}
p1++;
p2++;
}
// Return final result
return num;
}
// Driver code
let res = swapBits(28, 0, 3, 2);
document.write("Result = " + res);
// This code is contributed by suresh07
</script>
Producción
Result = 7
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de bits a intercambiar.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Referencias: intercambio de bits individuales con XOR 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