20. Rotate Bits

The problem can be found at the following link: Question Link

My Approach

To rotate the bits of an integer n by d positions, I followed these steps:

• Create a mask named mask_16 to exclusively consider the lower 16 bits of n.

• Calculate d modulo 16 to address situations where d exceeds 16.

• To execute the left rotation, use the expression (n << d | (n >> (16 - d))).

  • This combination shifts n left by d bits and appends the rightmost bits, which are rotated from the left side due to (n >> (16 - d)). Then, apply the mask_16 to eliminate any extra bits.

• Similarly, for the right rotation, employ the formula (n >> d | (n << (16 - d))) and apply the mask_16.

• Finally, return the results as a vector.

With Example

Let's take an example to illustrate how this works:

• Input: n = 10, d = 3

• mask_16 is 65535 (binary: 1111111111111111).

• d modulo 16 is 3.

• Left rotation: (n << 3 | n >> (16 - 3)) results in 80 (binary: 01010000).

• Right rotation: (n >> 3 | n << (16 - 3)) results in 16385 (binary: 0100000000000001).

• So, the output is out = {80, 16385}.

Time and Auxiliary Space Complexity

• Time Complexity: The time complexity of this code is O(1) because the number of operations is constant and not dependent on the input size.

• Auxiliary Space Complexity: The auxiliary space complexity is O(1) as well. We only use a constant amount of additional space to store the results in the out vector.

Code (C++)

class Solution {
public:
    vector<int> rotate(int n, int d) {
        int mask_16 = (1 << 16) - 1;
        d = d % 16;
        
        vector<int> out(2);
        out[0] = (n << d | n >> (16 - d)) & mask_16;
        out[1] = (n >> d | n << (16 - d)) & mask_16;
        
        return out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.