02. Copy Set Bits in Range

The problem can be found at the following link:

My approach

This is a simple bit masking question where we need to generate a mask to filter out specific bits from y and then perform a bitwise OR operation (x or y) to copy the values of y into x.

To create the mask, follow these steps:

First, determine the length of the filter mask.
Create the mask by left-shifting 1 by the mask length.
Obtain the desired mask by subtracting 1 from the mask and left-shifting it by l - 1.
Once the mask is ready, apply it to filter out the relevant bits from y, and perform a bitwise OR operation with x to copy the filtered values into x.

Example

Given:
- x = 1090 (10001000010)
- y = 1211 (10010111011)
- l = 2
- r = 6

Steps:

1. Since l = 2 and r = 6 are inclusive in the range, 
   maskLen = 5.

2. Calculate the mask:
   - Initialize mask as 1 shifted left by maskLen: mask = 1 << 5 = 32 (100000)

   - Subtract 1 from mask: mask = mask - 1 = 31 (011111)
     (We obtain a mask with the required length of 5 ones)

   - Shift the mask towards the left boundary by (l - 1): mask = mask << (l - 1) = (0111110)
     (This is our required mask)
 
 3. Filter out y value:
    y' = y & mask = (10010111011) & (0111110) = (0111010)

 4. Copy x or y:
    Result = x | y' = (10001000010) | (0111010) = 1146 (10001111010)

Time and Auxiliary Space Complexity

Time Complexity : O(1), as it does not depend on the size of the inputs x and y.
Auxiliary Space Complexity : constant as it does not depend on variables

Code (C++)


class Solution {
public:
    int setSetBit(int x, int y, int l, int r) {
        int maskLen = r - l + 1;
        int mask = (1 << maskLen) - 1;
        mask = mask << (l - 1);
        y = y & mask;
        return (x | y);  
    }
};

Contribution and Support

Previous07-2023(july)Next07-2023(july)

Last updated 1 year ago

Was this helpful?

My approach

This is a simple bit masking question where we need to generate a mask to filter out specific bits from y and then perform a bitwise OR operation (x or y) to copy the values of y into x.

To create the mask, follow these steps:

First, determine the length of the filter mask.

Create the mask by left-shifting 1 by the mask length.

Obtain the desired mask by subtracting 1 from the mask and left-shifting it by l - 1.

Once the mask is ready, apply it to filter out the relevant bits from y, and perform a bitwise OR operation with x to copy the filtered values into x.

Example

Given:
- x = 1090 (10001000010)
- y = 1211 (10010111011)
- l = 2
- r = 6

Steps:

1. Since l = 2 and r = 6 are inclusive in the range, 
   maskLen = 5.

2. Calculate the mask:
   - Initialize mask as 1 shifted left by maskLen: mask = 1 << 5 = 32 (100000)

   - Subtract 1 from mask: mask = mask - 1 = 31 (011111)
     (We obtain a mask with the required length of 5 ones)

   - Shift the mask towards the left boundary by (l - 1): mask = mask << (l - 1) = (0111110)
     (This is our required mask)
 
 3. Filter out y value:
    y' = y & mask = (10010111011) & (0111110) = (0111010)

 4. Copy x or y:
    Result = x | y' = (10001000010) | (0111010) = 1146 (10001111010)

class Solution { public: int setSetBit(int x, int y, int l, int r) { int maskLen = r - l + 1; int mask = (1 << maskLen) - 1; mask = mask << (l - 1); y = y & mask; return (x | y); } };