Last Updated: 17 Mar, 2021

Swap Adjacent Bit Pairs

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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:

Let oddPositionBits and evenPositionBits be the two variables that store the value of bits at odd positions and even positions respectively.
Set oddPositionBits as the Bitwise AND of N and 0x55555555.
Set evenPositionBits as the Bitwise AND of N and 0xAAAAAAAA.
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.
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.
Return the variable ans.

Solve now