Swap Adjacent Bit Pairs
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

Question

Swap Adjacent Bit Pairs

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

Accepted Answer

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.

Accepted Answer

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:

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.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(1)Explanation:

O(1).

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

Python (3.5)

'''

    Time Complexity: O(1)

    Space Complexity: O(1)

'''





def swapAdjacentBits(n):



    # Finding the odd position bits and even position bits

    oddPositionBits = n & (0x55555555)

    evenPositionBits = n & (0xAAAAAAAA)



    # Swapping the obtained value

    oddPositionBits <<= 1

    evenPositionBits >>= 1



    # Combining the separated values

    ans = oddPositionBits | evenPositionBits



    return ans

Java (SE 1.8)

/*

    Time Complexity: O(1)

    Space Complexity: O(1)

*/



public class Solution 

{

    public static int swapAdjacent(int n) 

    {

        // Finding the odd position bits and even position bits

        int oddPositionBits = n & (0x55555555);

        int evenPositionBits = n & (0xAAAAAAAA);



        // Swapping the obtained value

        oddPositionBits <<= 1;

        evenPositionBits >>= 1;



        // Combining the separated values

        int ans = oddPositionBits | evenPositionBits;



        return ans;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(1)

    Space Complexity: O(1)

*/



int swapAdjacentBits(int n)

{

    // Finding the odd position bits and even position bits

    int oddPositionBits = n &(0x55555555);

    int evenPositionBits = n &(0xAAAAAAAA);



    // Swapping the obtained value

    oddPositionBits <<= 1;

    evenPositionBits >>= 1;



    // Combining the separated values

    int ans = oddPositionBits | evenPositionBits;



	return ans;

}