Bitwise Rotation

Posted: 8 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.
Try Problem