Swap Adjacent Bit Pairs

Easy
0/40
Average time to solve is 10m
profile
Contributed by
28 upvotes
Asked in companies
AmazonAdobeQualcomm

Problem statement

You are given an integer 'N'. Your task is to find the number formed after swapping each even bit of 'N' in its binary representation with its adjacent bit on the right, assuming that the least significant bit is an odd bit.

For example :

Consider the integer N = 45 whose binary representation is 101101. The resulting number formed after swapping each even bit with its adjacent bit to the right will be 30 (011110) in this case.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first and only line of each test case contains the integer 'N'.
Output Format : 
For each test case, print the resulting integer formed after swapping each even bit.

Print the output of each test case in a new line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10^5
1 <= N <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
9
2
Sample Output 1 :
6 
1
Explanation For Sample Input 1 :
For the first test case : 
The binary representation of 9 is 1001. Here, we will swap the 2nd bit with the 1st bit and the 4th bit with 3rd bit. The resulting binary number will be 0110. Hence, the answer is 6 in this case.

For the second test case : 
The binary representation of 2 is 10. Here, we will swap the 2nd bit with the 1st bit. The resulting binary number will be 01 or 1. Hence, the answer is 1 in this case.
Sample Input 2 :
2
7
10
Sample Output 2 :
11
5
Hint

Try to separate all the even bits and the odd bits.

Approaches (1)
Solution using Bitwise Operators

The idea is to first separate all the bits that are present at the odd positions and the even positions. After separating the bits at even and odd positions, we can swap them by right shifting the number formed by taking bits at even position by 1 bit and left shifting the number formed by taking bits at the odd position by 1 bit. So, our final result will be the Bitwise OR of the two values. To get the bits at the odd position, we will need to toggle all the bits at even position in the binary representation of N off, while keeping the bits at odd positions unchanged, to do so, we will take the Bitwise AND of N with the binary number of the form of  01010101… As taking the Bitwise AND will make all even bits 0 while the odd bits will remain the same. As the number of bits in our input is at most 32, so will take the number  01..(repeated16 times), which can be represented as 0x55555555 in hexadecimal form. Similarly, to get the bits at even positions, we will take Bitwise AND of N with 0xAAAAAAAA.

 

Steps:

  1. Let oddPositionBits and evenPositionBits be the two variables that store the value of bits at odd positions and even positions respectively.
  2. Set oddPositionBits as the Bitwise AND of N and 0x55555555.
  3. Set evenPositionBits as the Bitwise AND of N and 0xAAAAAAAA.
  4. Left shift oddPositionBits by 1 bit and right shift evenPositionBits by 1 bit. In this step, we are swapping the positions of the odd bits and the even bits.
  5. Let ans be the variable that stores the final result. Set ans as the Bitwise OR of oddPositionBits and evenPositionBits. Here, we are recombining the od bits and the even bits after swapping them.
  6. Return the variable ans.
Time Complexity

O(1).

 

Finding the Bitwise AND and Bitwise OR takes constant time. Hence, the overall Time Complexity is O(1).

Space Complexity

O(1).

 

We are using only constant extra space. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Swap Adjacent Bit Pairs
Full screen
Console