Swap bits in a given number

Given a number x and two positions (0 based from the right side) in the binary representation of x, write a function that swaps n bits at the given two positions and returns the result. It is also given that the two sets of bits do not overlap.

Examples:

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)
Explanation:
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)

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)
Explanation:
The 2 bits starting from 0th position (from right side) are
swapped with 2 bits starting from 4th position (from right side)

Using XOR - O(1) time and O(1) space

We need to swap two sets of bits. XOR can be used in a similar way as it is used to swap 2 numbers using XOR.

The idea is to swap n bits at positions p1 and p2 in a number x by isolating these bit sets, XORing them to find the differences, and then selectively flipping only the bits that need to change, using the property that XOR marks differing bits and applying a second XOR operation restores the correct values in their swapped positions.

Step by step approach:

1. Extract the first set of n bits from position p1 by right-shifting and masking with an n-bit mask
2. Extract the second set of n bits from position p2 using the same technique
3. XOR these two sets to identify which corresponding bits differ between them
4. Position these XOR differences back at their original locations (p1 and p2)
5. XOR the original number with these positioned differences to selectively flip only the bits that need to change

// C++ Program to swap bits // in a given number #include <bits/stdc++.h> using namespace std; // Function to swap bits in a given number 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 xorVal = (set1 ^ set2);  // Put the Xor bits back to their original positions   xorVal = (xorVal << p1) | (xorVal << p2);  // Xor the 'Xor' with the original number so that the   // two sets are swapped   int result = x ^ xorVal;  return result; } int main() {  int res = swapBits(28, 0, 3, 2);  cout << res;  return 0; } 

// Java Program to swap bits // in a given number class GfG {  // Function to swap bits in a given number  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 xorVal = (set1 ^ set2);  // Put the Xor bits back to their original positions   xorVal = (xorVal << p1) | (xorVal << p2);  // Xor the 'Xor' with the original number so that the   // two sets are swapped   int result = x ^ xorVal;  return result;  }  public static void main(String[] args) {  int res = swapBits(28, 0, 3, 2);  System.out.println(res);  } } 

# Python Program to swap bits # in a given number # Function 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  xorVal = (set1 ^ set2) # Put the Xor bits back to their original positions  xorVal = (xorVal << p1) | (xorVal << p2) # Xor the 'Xor' with the original number so that the  # two sets are swapped  result = x ^ xorVal return result if __name__ == "__main__": res = swapBits(28, 0, 3, 2) print(res) 

// C# Program to swap bits // in a given number using System; class GfG {  // Function to swap bits in a given number  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 xorVal = (set1 ^ set2);  // Put the Xor bits back to their original positions   xorVal = (xorVal << p1) | (xorVal << p2);  // Xor the 'Xor' with the original number so that the   // two sets are swapped   int result = x ^ xorVal;  return result;  }  static void Main(string[] args) {  int res = swapBits(28, 0, 3, 2);  Console.WriteLine(res);  } } 

// JavaScript Program to swap bits // in a given number // Function 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 xorVal = (set1 ^ set2);  // Put the Xor bits back to their original positions   xorVal = (xorVal << p1) | (xorVal << p2);  // Xor the 'Xor' with the original number so that the   // two sets are swapped   let result = x ^ xorVal;  return result; } let res = swapBits(28, 0, 3, 2); console.log(res); 

7

Checking Each bit - O(1) time and O(1) space

The idea is to perform a bit-by-bit swap by iterating through each of the n positions, checking if the corresponding bits at the two positions differ, and if they do, flipping both bits to effectively swap their values - this approach handles the swap one bit at a time rather than operating on the entire bit sequences in a single operation.

Step by step approach:

1. For each of the n positions, create masks to isolate individual bits at both locations.
2. Check if the bits at the two positions are different (one is 0 and one is 1).
3. If they differ, flip both bits by clearing the set bit and setting the unset bit.
4. If the bits are identical (both 0 or both 1), no action is needed.
5. Increment both position pointers and continue until all n bits are processed.

// C++ Program to swap bits // in a given number #include <bits/stdc++.h> using namespace std; int swapBits(int x, int p1, int p2, 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 = ((x & shift1));  value2 = ((x & 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  x = x & (~shift1);    // set bit at p2 position  x = x | shift2;  }  // if bit at p2 position is set  else {    // set bit at p2 position  x = x & (~shift2);    // unset bit at p2 position  x = x | shift1;  }  }  p1++;  p2++;  }    // return final result  return x; } int main() {  int res = swapBits(28, 0, 3, 2);  cout << 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) {  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 = (x & shift1);  value2 = (x & 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  x = x & (~shift1);    // set bit at p2 position  x = x | shift2;  }  // if bit at p2 position is set  else {    // set bit at p2 position  x = x & (~shift2);    // unset bit at p2 position  x = x | shift1;  }  }  p1++;  p2++;  n--;  }    // return final result  return x;  }  public static void main(String[] args) {  int res = swapBits(28, 0, 3, 2);  System.out.println(res);  } } 

# Python Program to swap bits # in a given number def swapBits(x, p1, p2, n): shift1 = shift2 = value1 = 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 = x & shift1 value2 = x & shift2 # check if value1 and value2 are different # i.e. at one position bit is set and other it is not if (not value1 and value2) or (not value2 and value1): # if bit at p1 position is set if value1: # unset bit at p1 position x = x & (~shift1) # set bit at p2 position x = x | shift2 # if bit at p2 position is set else: # set bit at p2 position x = x & (~shift2) # unset bit at p2 position x = x | shift1 p1 += 1 p2 += 1 n -= 1 # return final result return x if __name__ == "__main__": res = swapBits(28, 0, 3, 2) print(res) 

// C# Program to swap bits // in a given number using System; class GfG {  static int swapBits(int x, 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 = (x & shift1);  value2 = (x & shift2);  // check if value1 and value2 are different  // i.e. at one position bit is set and other it is not  if ((!Convert.ToBoolean(value1) && value2 != 0) ||   (!Convert.ToBoolean(value2) && value1 != 0)) {    // if bit at p1 position is set  if (value1 != 0) {    // unset bit at p1 position  x = x & (~shift1);    // set bit at p2 position  x = x | shift2;  }  // if bit at p2 position is set  else {    // set bit at p2 position  x = x & (~shift2);    // unset bit at p2 position  x = x | shift1;  }  }  p1++;  p2++;  }  // return final result  return x;  }  static void Main(string[] args) {  int res = swapBits(28, 0, 3, 2);  Console.WriteLine(res);  } } 

// JavaScript Program to swap bits // in a given number function swapBits(x, p1, p2, n) {  let 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 = x & shift1;  value2 = x & 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  x = x & (~shift1);  // set bit at p2 position  x = x | shift2;  }  // if bit at p2 position is set  else {  // set bit at p2 position  x = x & (~shift2);  // unset bit at p2 position  x = x | shift1;  }  }  p1++;  p2++;  }  // return final result  return x; } let res = swapBits(28, 0, 3, 2); console.log(res); 

7

Related Article:

• Swapping individual bits with XOR