Bitwise Rotation

Easy
0/40
Average time to solve is 15m
3 upvotes
Asked in company
Walmart

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
13 2
12 -2
Sample Output 1:
7
3
Explanation of sample input 1:
For the first test case, 
Bits representation for N = 13 will be 1101.
After K = 2 right rotations, Bits representation will be 0111.
The integer value corresponding to ‘0111’ is 7. Hence the answer is 7.

For the second test case, 
Bits representation for N = 12 will be 1100.
After K = 2 left rotations, Bits representation will be 0011.
The integer value corresponding to ‘0011’ is 3. Hence the answer is 3.
Sample Input 2:
2
21 3
5 -3
Sample Output 2:
22
5
Hint

Try to use bitwise shift operators.

Approaches (2)
Brute Force

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.
Time Complexity

O(log(N) + K), where N is the given number and K is the number of bitwise rotations to be performed.

 

The time complexity O(log(N)) is used to find the total number of bits in the given number. All bitwise operation takes O(1) time. We are doing shifting operations K times. Hence the overall time complexity is O(log(N) + K).

Space Complexity

O(1).

 

We are using constant space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Bitwise Rotation
Full screen
Console