Swap All Odd And Even Bits
Try First, Check Solution later1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.
1. You are given a number n.Input Format
2. You have to swap all odd position bits with even position bits.
3. Every odd position bit is swapped with adjacent bit on left side.
4. Every even position bit is swapped with adjacent bit on right side.
5. Print the number formed after swapping.
A number nOutput Format
Check the sample ouput and question video.Question Video
1 <= n <= 10^9Sample Input
In this problem, we are given a number N and we need to swap all even position bits with odd position bits and then return the resultant number thus formed. Thus we need to swap 1 with 2, 3 with 4, ... (2k - 1) with (2k).
Let us take an example to understand the problem better:
N = 10
Binary Representation = 1 0 1 0
Index = 4 3 2 1
Binary After Swapping = 0 1 0 1
Output = 5
The problem statement can be reframed as given a number N we need to shift all its even position bits by 1 to the right side and all its odd position bits by 1 to its left side.
To achieve this we will be maintaining two integers one will be storing the result of all even bits and the other one will be storing the result of all odd bits. Now we know that even bits are of type ...1010...1010 which is the same as 0x...A...A... so we can take AND operation with 0xAAAAAAAA to get all even bits, similarly, we can take AND operation result of N with 0x555555555 to get our odd bits as 0x55 is same as 01010101 which implies that this contains 1 only at odd positions. Now, as soon as we have our bits separated we just need to left shift odd bits and right shift even bits and take their OR to get the final result.
Time Complexity: O(1)
The time complexity for the function is constant.Space Complexity: O(n)
The space complexity for the function is constant.
Asked in Companies