Intercambiar bits en un número dado

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++ 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 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 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.

# 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# 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 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.
?>

<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>

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++ 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.

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));
}

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.

# 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.

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.

<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 

#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;
}

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

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

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

<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>

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.