Copy set bits in a range

Problem Statement:

You are given 2 numbers x and y and a range [i,r] 1 <= l, r <= 32.

You need to set bits of y in range [l, r] that are set bits in x.

Example

A = 10101110101
B = 10010011001

L = 3
R = 7

As we need to copy the set bits from ‘A’ to ‘B’ so we need to ‘OR’.
So we need to ‘or’ the digits ‘R’ to ‘L’ from A to B as shown below:

	        R       L
A = 1 0 1 0 1 0 1 0 1 0 1
B = 1 0 0 1 0 0 1 1 0 0 1
--------------------------
            1 0 1 1 1

So final answer is :

	        R       L
A = 1 0 1 0 1 0 1 0 1 0 1
B = 1 0 0 1 0 0 1 1 0 0 1
--------------------------
    1 0 0 1 1 0 1 1 1 0 1

Solution

To get the answer we need to OR B with a mask i.e:

	           R       L
A    = 1 0 1 0 1 0 1 0 1 0 1
B    = 1 0 0 1 0 0 1 1 0 0 1
Mask = 0 0 0 0 1 0 1 0 1 0 0
--------------------------
       1 0 0 1 1 0 1 1 1 0 1

Now the next task is how to get the mask:

So to get the mask we will concentrate on A

Step 1:

	           R       L
A    = 1 0 1 0 1 0 1 0 1 0 1
Mask =

Step 2:
Make the mask as binary 1

	           R       L
A    = 1 0 1 0 1 0 1 0 1 0 1
Mask = 0 0 0 0 0 0 0 0 0 0 1

Step 3:
Now shift the mask 5 times.

	            R       L
A     = 1 0 1 0 1 0 1 0 1 0 1
m|<<5 = 0 0 0 0 1 0 0 0 0 0 0

Step 4:
Minus 1 from that

	                R       L
A         = 1 0 1 0 1 0 1 0 1 0 1
(m|<<5)-1 = 0 0 0 0 0 1 1 1 1 1 1

Step 5:
Shift 2 times

	                    R       L
A             = 1 0 1 0 1 0 1 0 1 0 1
(m|<<5)-1]<<2 = 0 0 0 0 1 1 1 1 1 0 0

Step 6:
Take the ‘and’ of “A” and “mask”

	                    R       L
A             = 1 0 1 0 1 0 1 0 1 0 1
(m|<<5)-1]<<2 = 0 0 0 0 1 1 1 1 1 0 0
---------------------------------------
                0 0 0 0 1 0 1 0 1 0 0

You get the mask bit as the result.

Now take the result and then ‘or’ it with B to get final result.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

void copy_set_bits(unsigned &x, unsigned &y, unsigned l, unsigned r) 
{ 
    if (l < 1 || r > 32) 
        return ; 

     int maskLength = (1<<(r-l+1)) - 1; 
  
    int mask = ((maskLength)<<(l-1)) & x ; 

    y = y | mask; 
} 
  
int main() 
{ 
   unsigned x = 10, y = 12, l = 2, r = 3; 
   copy_set_bits(x, y, l, r); 
   cout << "Changed y is " << y<<endl; 
   return 0; 
} 

Output:

Changed y is 14