Given a number x and two positions (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.
Method 1
Let p1 and p2 be the two given positions.
Example 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)
Example 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)
Solution
We need to swap two sets of bits. XOR can be used in a similar way as it is used to swap 2 numbers. Following is the algorithm.
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
Implementation:
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 numberclass 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 numberdef 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 coderes = swapBits(28, 0, 3, 2)print("Result =", res)# This code is contributed# by Anant Agarwal. |
C#
// C# Program to swap bits// in a given numberusing 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 bitsfunction 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> |
Output
Result = 7
Time Complexity: O(1), as we are using constant-time operations.
Auxiliary Space: O(1), as we are not using any extra space.
Following is a shorter implementation of the same logic
C++
// C++ program of the 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 approachdef 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 approachfunction 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> |
Time Complexity: O(1), as we are using constant-time operations.
Auxiliary Space: O(1), as we are not using any extra space.
Method 2 –
This solution focuses on calculating the values of bits to be swapped using AND gate. Then we can set/unset those bits based on whether the bits are to be swapped. For the number of bits to be swapped (n) –
- Calculate shift1 = The value after setting bit at p1 position to 1
- Calculate shift2 = The value after setting bit at p2 position to 1
- value1 = Number to check if num at position p1 is set or not.
- value2 = Number to check if num at position p2 is set or not.
- If value1 and value2 are different is when we have to swap the bits.
Example:
[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
Implementation
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 coderes = 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 codelet res = swapBits(28, 0, 3, 2);document.write("Result = " + res);// This code is contributed by suresh07 </script> |
Output
Result = 7
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the number of bits to be swapped.
Auxiliary Space: O(1), as we are not using any extra space.
References:
Swapping individual bits with XOR
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
