Last Updated: 8 Dec, 2020
Bitwise Rotation
Easy
Asked in company
You are given two integers, ‘N’ and ‘K’ .Your task is to bitwise rotate the given integer ‘N’, ‘K’ number of times. The Bit Rotation is an operation similar to shift except that the bits that fall off at one end are put back to the other end.
1- If ‘K’ is negative, you have to perform left rotation. The bits that fall off at the left end are put back at the right end.
2- If ‘K’ is positive, you have to perform the right rotation. The bits that fall off at the right end are put back at the left end.
For example:
Consider If N = 13 and K = 2, then
Bits representation of N is 1101.
As K is greater than 0, we have to perform the right rotation
After the first rotation, bits representation will be 1110
After the second rotation, bits representation will be 0111
The integer value corresponding to ‘0111’ is 7. Hence the answer is 7.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
For each test case, there will be two space-separated integers, ‘N’ and ‘K’, denoting the given number and number of bitwise rotations you have to perform on ‘N’.
Output Format:
For each test, print a single integer representing the updated value of ‘N’ after ‘K’ bitwise rotations.
Print the output of each test case in a separate 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
1 <= N <= 10^12
-10^9 <= K <= 10^9
Time limit: 1 sec
Approaches
In this approach, we will first calculate the number of bits in the bits representation of N and store that number as size. We will also store the MSB(Most Significant Bit) of N in a variable msb. For K times, we will shift the bits using a suitable bitwise shift operation on N (according to the sign of K). In the end, we will set N as N & (1<<(size) -1) to remove the extra bits and return the updated N.
Algorithm:
- We will calculate the number of bits in N and store it in variable size.
- Initialize size as 0.
- Declare a variable temp and set temp as N.
- While temp is not equal to 0, do the following:
- Increment size by 1.
- Set temp as temp / 2.
- Now, we have calculated the size.
- Declare a variable msb to store the value of the most significant digit.
- Set msb as 1 is left shifted by size - 1 i.e. 1<<(size-1).
- Declare a variable left to store whether to do a left rotation or right rotation.
- Set left as true if K is less than zero. Otherwise, set left as false.
- Set K as the absolute value of K.
- Declare a variable checkMsb to check whether msb bit is 1 or 0.
- If left is true, do the following steps K times:
- Set checkMsb as bitwise AND operation of N and msb , i.e., N & msb.
- Performing left shift on N by setting N as N << 1.
- Set the first bit according to checkMsb.
- If checkMsb is greater than 0:
- Set N as bitwise OR of N and 1, i.e., N | 1.
- Otherwise, do the following K times for right rotation :
- Declare a variable to checkLsb to check whether LSB is 1 or 0.
- Set checkLsb as bitwise AND operation of N and 1, i.e., N & 1.
- Performing right shift on N by setting N = N>>1.
- Set the msb bit according to checkLsb.
- If checkLsb is greater than 0:
- Set N as bitwise OR of N and msb, i.e., N | msb.
- Now,remove the extra bits by updating N as N & ( (1<<size) - 1).
- Return the variable N.
In this approach, we will first calculate the number of bits in the bits representation of N and store that number as size. We will reduce K to K % size as we know rotating the bits any multiple of size times, we will get the initial bits representation.
For right rotation, we need to move the last K bits to the front, and the remaining size-K bits are shifted K times towards the right.
For left rotation, we need to move the first K bits to the end, and the remaining size-K bits are shifted K times towards the left.
We will use this observation to obtain the answer, and we will use bitwise shift operators to shift these bits.
Algorithm:
- We will calculate the number of bits in N and store it in variable size.
- Initialize size as 0.
- Declare a variable temp and set temp as N.
- While temp is not equal to 0, do the following:
- Increment size by 1.
- Set temp as temp / 2.
- Now, we have calculated the size.
- Declare a variable left to store whether to do a left rotation or right rotation.
- Set left as true if K is less than zero. Otherwise, set left as false.
- Set K as the absolute value of K.
- Set K as K%size.
- If left is true, do the following steps:
- We will shift the first K bits to the end, for which we will right shift N (size-K) times and store that value in a variable named lastK.
- Set lastK as N>>(size-K).
- We will left shift the remaining size-K bits K times by setting N as N<<K.
- To obtain the final answer, we will add these bits by setting N as bitwise OR of N and lastK, i.e., N | lastK.
- Otherwise, do the following for right rotation :
- We will shift the last K bits to the front, for which we will perform left shift operation on N by (size-K) times and store that value in a variable named firstK.
- Set firstK as N<<(size-K).
- We will right-shift the remaining size-K bits K times by setting N as N>>K.
- To obtain the final answer, we will add these bits by setting N as bitwise OR of N and firstK, i.e., N | firstK.
- Now,remove the extra bits by updating N as N & ( (1<<size) - 1).
- Return the variable N.