Swap two bits in a number

In this problem, we have to swap bits in a given number or an integer. This can be solved in constant time O(1) using XOR operation. So before moving towards this problem first we have to understand what is a bit that needs to be swapped.

Table of contents:

1. Introduction to bits and Problem statement
2. Naive Approach
3. Time and Space Complexity Analysis of Naive Approach
4. XOR Swap Approach
5. Time and Space Complexity analysis of XOR Swap Approach

Introduction to bits and Problem statement

A bit is the smallest unit of information in computing. It can have only two values that are 0 and 1. Bits are grouped into bit multiples which is known as bytes to store data and information to execute instructions.
Example: Suppose if we have a binary number 0011010 so in this an individual digit that is 0 or 1 is known as a bit.

Now coming back to our problem we are given an integer or a number and we have to swap two bits in binary representation of that number at given positions. The positions are considered from the left most or from least significant bit (least significant bit is the leftmost bit).
Example:

Suppose we have a number 12 and two given positions are 0 and 2. Here one thing is important 0 and 2 are taken into consideration according to the least significant bit that means 0th position is to the immediate right of least significant bit and in the same way 2 is third to the right of least significant bit. We are supposed to swap two bits at given position and return a newly formed number. So let us see how to approach this problem and its implementation.

Naive Approach

So we will start with converting the given number into its binary form and then we will swap the two bits at given positions and after getting a new binary number we will convert that number into its decimal form and finally print that number.

Example: we have a number 12 so first convert it into its binary equivalent so it comes out to be 1100 as for finding binary equivalent we have to divide the number by and store the remainder and after that reverse the whole to get the binary number. See below to get clear understanding.

12/2=6 remainder=0
6/2=3 remainder=0
3/2=1 remainder=1

Now 1 has come so we will stop and including 1(last digit) we will move up in reverse manner from lower side and we will get 1100 as a binary equivalent of 12.
After finding this we will swap the two bits ate given position i.e, 0 and 2 so 0th position in 1100 is second from left i.e, 1(bolder digit) and 2nd position in 1100 is third from the right i.e, 0(bolder digit). We will simply swap these two bits and we will get a new binary number as 1001. So now convert this to its decimal. To convert in decimal form we will multiply with the power of 2 just like below.

1001 ,first we will assign position numbers to each bit from rightmost side
3210 ,these are positions for each bit. Now multiply each bit with power of 2 and power is equal to position number and add them all. See this:

(1 * 2^3)+(0 * 2^2)+(0 * 2^1)+(1 * 2^0)=9 so our final answer is 9 .

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cout<<"Enter a number:"<<'\n';
    cin>>n;
    
    int a,b;
    cout<<"Enter bit positions:"<<'\n';
    cin>>a>>b;
    
    int bin[32];
    int i = 0;
    
    //converting decimal to binary
    while (n > 0) {
        bin[i] = n % 2;
        n = n / 2;
        i++;
    }
    
    reverse(bin,bin+i);  //reversing because we have to move from bottom to top
    
    swap(bin[a+1],bin[b+1]);  //swapping two bits
    
    int b=1,ans=0;
    
    //converting binary to decimal
    for(int j=0;j<i;j++){
        int rem=bin[j]%10;
        bin[j]/=10;
        ans+=rem*b;
        b*=2;
    }
    cout<<"Number after swapping two bits:"<<'\n';
    cout<<ans;
    return 0;
}

Output:

Enter a number:
12
Enter bit positions:
0 2
Number after swapping two bits:
9

Time and Space Complexity Analysis of Naive Approach

The time complexity of above code is O(i) where i is the size of the binary number formed, as we are traversing all the binary number bits are also using swap built in function which also takes linear time.

So we can further improve the time complexity for this problem by using different concept.

XOR Swap Approach

We will first find the bits and then use XOR based swapping method. First let us see what is XOR based swapping method. It is a swapping technique or a method with the help of which we can swap two numbers. The concept to swap two numbers is that, suppose we have two numbers a and b so we will perform XOR operation in such a way that a becomes (a XOR b) , b becomes (a XOR b) and again a is equal to (a XOR b).
a=a^b;
b=a^b;
a=a^b;
We will perform these operations to swap two bits in a number. Rest of the thing remains same as above approach. See this example to get clear view of XOR based concept.

Example:

We have a=10 and b=5, so
a=a^b // now a becomes 15 or 1111 (10 XOR 5 = 15)
b=a^b // now b becomes 10 or 1010 (15 XOR 5 = 10)
a=a^b // now again performing this a becomes 5 or 0101 (15 XOR 10 = 5)
so as we can see that we have successfully swapped two numbers, as a becomes 5 and b becomes 10. Lets see the implementation of given problem using this concept.

C++ implementation:

#include<bits/stdc++.h>
using namespace std;

//function swaps bits at position a and b in the given number n
int swB(int n, int a, int b)
{
	//Move ath bit to rightmost side
	int a1 = (n >> a) & 1;

	//Move bth bit to rightmost side
	int b1 = (n >> b) & 1;

	//XOR the two bits
	int c = (a1 ^ b1);

	//Put the xor bit back to its original position
	c = (c << a) | (c << b);

	//XOR with the original given number so they are swapped
	int answer = n ^ c;
	return answer;
}
int main(void)
{
	int n;
    cout<<"Enter a number:"<<'\n';
    cin>>n;
    
    int a,b;
    cout<<"Enter bit positions:"<<'\n';
    cin>>a>>b;
    
    cout<<"Number after swapping two bits:"<<'\n';
    cout<<swB(12,0,2);
	return 0;
}

Output:

Enter a number:
12
Enter bit positions:
0 2
Number after swapping two bits:
9

Time and Space Complexity analysis of XOR Swap Approach

The time complexity of above code is O(1) as we are not using any loops and we are also not using any built-in function for swapping the bits.
The space complexity is also O(1) as no extra space or memory is required by this program.

So now I will conclude with the hope that you all will definitely try this problem after taking help from this article at OpenGenus.
Happy coding.

Thank you.