Copiar bits establecidos en un rango

Dados dos números x e y, y un rango [l, r] donde 1 <= l, r <= 32. La tarea es considerar establecer bits de y en el rango [l, r] y establecer estos bits en x también.
Ejemplos: 

Input  : x = 10, y = 13, l = 2, r = 3
Output : x = 14
Binary representation of 10 is 1010 and 
that of y is 1101. There is one set bit
in y at 3'rd position (in given range). 
After we copy this bit to x, x becomes 1110
which is binary representation of 14.

Input  : x = 8, y = 7, l = 1, r = 2
Output : x = 11

Fuente: Entrevista de DE Shaw
 

Método 1 (Bits de copia uno por uno) 
Podemos encontrar bits establecidos de y uno por uno atravesando el rango dado. Para cada bit establecido, lo hacemos OR al bit existente de x, de modo que se establece en x, si no estaba establecido. A continuación se muestra la implementación de C++.
 

// C++ program to rearrange array in alternating
// C++ program to copy set bits in a given
// range [l, r] from y to x.
#include <bits/stdc++.h>
using namespace std;
 
// Copy set bits in range [l, r] from y to x.
// Note that x is passed by reference and modified
// by this function.
void copySetBits(unsigned &x, unsigned y,
                 unsigned l, unsigned r)
{
   // l and r must be between 1 to 32
   // (assuming ints are stored using
   //  32 bits)
   if (l < 1 || r > 32)
      return ;
 
   // Traverse in given range
   for (int i=l; i<=r; i++)
   {
       // Find a mask (A number whose
       // only set bit is at i'th position)
       int mask = 1 << (i-1);
 
       // If i'th bit is set in y, set i'th
       // bit in x also.
       if (y & mask)
          x = x | mask;
   }
}
 
// Driver code
int main()
{
   unsigned x = 10, y = 13, l = 1, r = 32;
   copySetBits(x, y, l, r);
   cout << "Modified x is " << x;
   return 0;
}

// Java program to rearrange array in alternating
// Java program to copy set bits in a given
// range [l, r] from y to x.
import java.util.*;
 
class GFG{
 
// Copy set bits in range [l, r] from y to x.
// Note that x is passed by reference and modified
// by this function.
static int copySetBits(int x, int y,
                 int l, int r)
{
   // l and r must be between 1 to 32
   // (assuming ints are stored using
   //  32 bits)
   if (l < 1 || r > 32)
      return x;
 
   // Traverse in given range
   for (int i = l; i <= r; i++)
   {
       // Find a mask (A number whose
       // only set bit is at i'th position)
       int mask = 1 << (i-1);
 
       // If i'th bit is set in y, set i'th
       // bit in x also.
       if ((y & mask)!=0)
          x = x | mask;
   }
    
   return x;
}
 
// Driver code
public static void main(String[] args)
{
   int x = 10, y = 13, l = 1, r = 32;
  x = copySetBits(x, y, l, r);
   System.out.print("Modified x is " +  x);
}
}
 
// This code is contributed by umadevi9616

# Python program to rearrange array in alternating
# Python program to copy set bits in a given
# range [l, r] from y to x.
 
# Copy set bits in range [l, r] from y to x.
# Note that x is passed by reference and modified
# by this function.
def copySetBits(x, y, l, r):
   
    # l and r must be between 1 to 32
    # (assuming ints are stored using
    # 32 bits)
    if (l < 1 or r > 32):
        return x;
 
    # Traverse in given range
    for i in range(l, r + 1):
       
        # Find a mask (A number whose
        # only set bit is at i'th position)
        mask = 1 << (i - 1);
 
        # If i'th bit is set in y, set i'th
        # bit in x also.
        if ((y & mask) != 0):
            x = x | mask;
    return x;
 
# Driver code
if __name__ == '__main__':
    x = 10;
    y = 13;
    l = 1;
    r = 32;
    x = copySetBits(x, y, l, r);
    print("Modified x is ", x);
 
# This code is contributed by gauravrajput1

// C# program to rearrange array in alternating
// C# program to copy set bits in a given
// range [l, r] from y to x.
using System;
 
public class GFG {
 
    // Copy set bits in range [l, r] from y to x.
    // Note that x is passed by reference and modified
    // by this function.
    static int copySetBits(int x, int y, int l, int r)
    {
       
        // l and r must be between 1 to 32
        // (assuming ints are stored using
        // 32 bits)
        if (l < 1 || r > 32)
            return x;
 
        // Traverse in given range
        for (int i = l; i <= r; i++)
        {
           
            // Find a mask (A number whose
            // only set bit is at i'th position)
            int mask = 1 << (i - 1);
 
            // If i'th bit is set in y, set i'th
            // bit in x also.
            if ((y & mask) != 0)
                x = x | mask;
        }
 
        return x;
    }
 
    // Driver code
    public static void Main(String[] args) {
        int x = 10, y = 13, l = 1, r = 32;
        x = copySetBits(x, y, l, r);
        Console.Write("Modified x is " + x);
    }
}
 
// This code is contributed by umadevi9616

<script>
// javascript program to rearrange array in alternating
// javascript program to copy set bits in a given
// range [l, r] from y to x.
 
    // Copy set bits in range [l, r] from y to x.
    // Note that x is passed by reference and modified
    // by this function.
    function copySetBits(x , y , l , r)
    {
     
        // l and r must be between 1 to 32
        // (assuming ints are stored using
        // 32 bits)
        if (l < 1 || r > 32)
            return x;
 
        // Traverse in given range
        for (i = l; i <= r; i++)
        {
         
            // Find a mask (A number whose
            // only set bit is at i'th position)
            var mask = 1 << (i - 1);
 
            // If i'th bit is set in y, set i'th
            // bit in x also.
            if ((y & mask) != 0)
                x = x | mask;
        }
 
        return x;
    }
 
    // Driver code
        var x = 10, y = 13, l = 1, r = 32;
        x = copySetBits(x, y, l, r);
        document.write("Modified x is " + x);
 
// This code is contributed by gauravrajput1
</script>

Modified x is 15

Complejidad de tiempo: O(r)

Espacio Auxiliar: O(1)

 
Método 2 (Copiar todos los bits usando una máscara de un bit)
 

// C++ program to copy set bits in a given
// range [l, r] from y to x.
#include <bits/stdc++.h>
using namespace std;
 
// Copy set bits in range [l, r] from y to x.
// Note that x is passed by reference and modified
// by this function.
void copySetBits(unsigned &x, unsigned y,
                 unsigned l, unsigned r)
{
    // l and r must be between 1 to 32
    if (l < 1 || r > 32)
        return ;
 
    // get the length of the mask
    int maskLength = (1ll<<(r-l+1)) - 1;
 
    // Shift the mask to the required position
    // "&" with y to get the set bits at between
    // l ad r in y
    int mask = ((maskLength)<<(l-1)) & y ;
    x = x | mask;
}
 
// Driver code
int main()
{
   unsigned x = 10, y = 13, l = 2, r = 3;
   copySetBits(x, y, l, r);
   cout << "Modified x is " << x;
   return 0;
}

// Java program to copy set bits in a given
// range [l, r] from y to x.
import java.util.*;
 
class GFG{
 
// Copy set bits in range [l, r] from y to x.
// Note that x is passed by reference and modified
// by this function.
static int copySetBits(int x, int y,
                 int l, int r)
{
   
    // l and r must be between 1 to 32
    if (l < 1 || r > 32)
        return x;
 
    // get the length of the mask
    int maskLength = (int)((1L<<(r-l+1)) - 1);
 
    // Shift the mask to the required position
    // "&" with y to get the set bits at between
    // l ad r in y
    int mask = ((maskLength)<<(l-1)) & y ;
    x = x | mask;
    return x;
}
 
// Driver code
public static void main(String[] args)
{
   int x = 10, y = 13, l = 2, r = 3;
  x =  copySetBits(x, y, l, r);
   System.out.print("Modified x is " +  x);
}
}
 
// This code is contributed by umadevi9616

# Python program to copy set bits in a given
# range [l, r] from y to x.
 
# Copy set bits in range [l, r] from y to x.
# Note that x is passed by reference and modified
# by this function.
def copySetBits(x, y, l, r):
 
    # l and r must be between 1 to 32
    if (l < 1 or r > 32):
        return x;
 
    # get the length of the mask
    maskLength = (int) ((1 << (r - l + 1)) - 1);
 
    # Shift the mask to the required position
    # "&" with y to get the set bits at between
    # l ad r in y
    mask = ((maskLength) << (l - 1)) & y;
    x = x | mask;
    return x;
 
# Driver code
if __name__ == '__main__':
    x = 10;
    y = 13;
    l = 2;
    r = 3;
    x = copySetBits(x, y, l, r);
    print("Modified x is " , x);
 
# This code is contributed by gauravrajput1

// C# program to copy set bits in a given
// range [l, r] from y to x.
using System;
 
public class GFG
{
 
    // Copy set bits in range [l, r] from y to x.
    // Note that x is passed by reference and modified
    // by this function.
    static int copySetBits(int x, int y, int l, int r) {
 
        // l and r must be between 1 to 32
        if (l < 1 || r > 32)
            return x;
 
        // get the length of the mask
        int maskLength = (int) ((1L << (r - l + 1)) - 1);
 
        // Shift the mask to the required position
        // "&" with y to get the set bits at between
        // l ad r in y
        int mask = ((maskLength) << (l - 1)) & y;
        x = x | mask;
        return x;
    }
 
    // Driver code
    public static void Main(String[] args) {
        int x = 10, y = 13, l = 2, r = 3;
        x = copySetBits(x, y, l, r);
        Console.Write("Modified x is " + x);
    }
}
 
// This code is contributed by gauravrajput1

<script>
// javascript program to copy set bits in a given
// range [l, r] from y to x.
 
    // Copy set bits in range [l, r] from y to x.
    // Note that x is passed by reference and modified
    // by this function.
    function copySetBits(x , y , l , r) {
 
        // l and r must be between 1 to 32
        if (l < 1 || r > 32)
            return x;
 
        // get the length of the mask
        var maskLength = parseInt( ((1 << (r - l + 1)) - 1));
 
        // Shift the mask to the required position
        // "&" with y to get the set bits at between
        // l ad r in y
        var mask = ((maskLength) << (l - 1)) & y;
        x = x | mask;
        return x;
    }
 
    // Driver code
        var x = 10, y = 13, l = 2, r = 3;
        x = copySetBits(x, y, l, r);
        document.write("Modified x is " + x);
     
// This code is contributed by gauravrajput1
</script>

Modified x is 14

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Gracias a Ashish Rathi por sugerir esta solución en un comentario.
Este artículo es una contribución de Rishi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.