Bit a bit OR (o | ) de un rango

Posted on by Rudeus Greyrat

Dados dos enteros L y R. Determine el OR bit a bit de todos los enteros en el rango [L, R] (ambos inclusive).

Ejemplos :  

Input: L = 3, R = 8
Output: 15
3 | 4 | 5 | 6 | 7 | 8 = 15

Input: L = 12, R = 18
Output: 31
12 | 13 | 14 | 15 | 16 | 17 | 18 = 31

Un enfoque ingenuo es atravesar todos los enteros entre L y R y hacer OR bit a bit de todos los números.

Un enfoque eficiente es seguir los siguientes pasos:  

  1. Encuentre la posición del bit más significativo (MSB) en ambos números (L y R)
  2. Si la posición de ambos MSB es diferente, establezca todos los bits desde max(MSB1, MSB2), incluido este bit diferente, hasta Oth bit, es decir, agregue el valor (1 << i) para todos los 0 ≤ i ≤ max( MSB1, MSB2) en la respuesta.
  3. Si la posición de ambos MSB es la misma, entonces 
    • Configure este bit correspondiente a MSB o agregue el valor (1 << MSB) en la respuesta.
    • Reste el valor (1 << MSB) de ambos números (L y R).
    • Repita los pasos 1, 2 y 3.

A continuación se muestra el funcionamiento del algoritmo anterior cuando L = 18 y R = 21. 

L = 18, R = 21
The result is initially 0.
The position of Most Significant Bit in L = 4
Position of Most Significant Bit in R = 4
Since positions are same, add value (1 << 4) i.e. 16 to the result.

Subtract (1 << 4) from L, L becomes 2.
Subtract (1 << 4) from R, R becomes 5.

Now, Position of MSB in L is 1
Position of MSB in R is 2
Since positions are different all value (1 << i) for all 
0 ≤ i ≤ max(MSB1, MSB2)
i.e. Add ((1 << 2) + (1 << 1) + (1 << 0)) = 7
Hence, final result is 16 + 7 = 23.

A continuación se muestra la implementación del enfoque anterior. 

C++

// C++ Program to find the bitwise
// OR of all the integers in range L-R
#include <bits/stdc++.h>
using namespace std;
 
// Returns the Most Significant Bit
// Position (MSB)
int MSBPosition(long long int N)
{
    int msb_p = -1;
    while (N) {
        N = N >> 1;
        msb_p++;
    }
    return msb_p;
}
 
// Returns the Bitwise OR of all
// integers between L and R
long long int findBitwiseOR(long long int L,
                            long long int R)
{
    long long int res = 0;
 
    // Find the MSB position in L
    int msb_p1 = MSBPosition(L);
 
    // Find the MSB position in R
    int msb_p2 = MSBPosition(R);
 
    while (msb_p1 == msb_p2) {
        long long int res_val = (1 << msb_p1);
 
        // Add this value until msb_p1 and
        // msb_p2 are same;
        res += res_val;
 
        L -= res_val;
        R -= res_val;
 
        // Calculate msb_p1 and msb_p2
        msb_p1 = MSBPosition(L);
        msb_p2 = MSBPosition(R);
    }
    // Find the max of msb_p1 and msb_p2
    msb_p1 = max(msb_p1, msb_p2);
 
    // Set all the bits from msb_p1 upto
    // 0th bit in the result
    for (int i = msb_p1; i >= 0; i--) {
        long long int res_val = (1 << i);
        res += res_val;
    }
    return res;
}
 
// Driver Code
int main()
{
    int L = 12, R = 18;
    cout << findBitwiseOR(L, R) << endl;
    return 0;
}

Java

// Java Program to find
// the bitwise OR of all
// the integers in range L-R
import java.io.*;
 
class GFG
{
 
// Returns the Most Significant
// Bit Position (MSB)
static int MSBPosition(long N)
{
    int msb_p = -1;
    while (N > 0)
    {
        N = N >> 1;
        msb_p++;
    }
    return msb_p;
}
 
// Returns the Bitwise
// OR of all integers
// between L and R
static long findBitwiseOR(long L,
                          long R)
{
    long res = 0;
 
    // Find the MSB
    // position in L
    int msb_p1 = MSBPosition(L);
 
    // Find the MSB
    // position in R
    int msb_p2 = MSBPosition(R);
 
    while (msb_p1 == msb_p2)
    {
        long res_val = (1 << msb_p1);
 
        // Add this value until
        // msb_p1 and msb_p2 are same;
        res += res_val;
 
        L -= res_val;
        R -= res_val;
 
        // Calculate msb_p1
        // and msb_p2
        msb_p1 = MSBPosition(L);
        msb_p2 = MSBPosition(R);
    }
     
    // Find the max of
    // msb_p1 and msb_p2
    msb_p1 = Math.max(msb_p1,
                      msb_p2);
 
    // Set all the bits
    // from msb_p1 upto
    // 0th bit in the result
    for (int i = msb_p1; i >= 0; i--)
    {
        long res_val = (1 << i);
        res += res_val;
    }
    return res;
}
 
// Driver Code
public static void main (String[] args)
{
    int L = 12, R = 18;
    System.out.println(findBitwiseOR(L, R));
}
}
 
// This code is contributed
// by anuj_67.

Python3

# Python3 Program to find the bitwise
# OR of all the integers in range L-R
 
# Returns the Most Significant Bit
# Position (MSB)
def MSBPosition(N) :
  
    msb_p = -1
    while (N) :
        N = N >> 1
        msb_p += 1
  
    return msb_p
  
 
# Returns the Bitwise OR of all
# integers between L and R
def findBitwiseOR(L, R) :
 
    res = 0
 
    # Find the MSB position in L
    msb_p1 = MSBPosition(L)
 
    # Find the MSB position in R
    msb_p2 = MSBPosition(R)
 
    while (msb_p1 == msb_p2) :
        res_val = (1 << msb_p1)
 
        # Add this value until msb_p1 and
        # msb_p2 are same;
        res += res_val
 
        L -= res_val
        R -= res_val
 
        # Calculate msb_p1 and msb_p2
        msb_p1 = MSBPosition(L)
        msb_p2 = MSBPosition(R)
      
    # Find the max of msb_p1 and msb_p2
    msb_p1 = max(msb_p1, msb_p2)
 
    # Set all the bits from msb_p1 upto
    # 0th bit in the result
    for i in range(msb_p1, -1, -1) :
        res_val = (1 << i)
        res += res_val
     
    return res
  
 
# Driver Code
if __name__ == "__main__" :
  
    L , R= 12 ,18
    print(findBitwiseOR(L, R))
 
# This code is contributed by Ryuga

C#

// C# Program to find
// the bitwise OR of all
// the integers in range L-R
using System;
 
class GFG
{
 
// Returns the Most Significant
// Bit Position (MSB)
static int MSBPosition(long N)
{
    int msb_p = -1;
    while (N > 0)
    {
        N = N >> 1;
        msb_p++;
    }
    return msb_p;
}
 
// Returns the Bitwise
// OR of all integers
// between L and R
static long findBitwiseOR(long L,
                          long R)
{
    long res = 0;
 
    // Find the MSB
    // position in L
    int msb_p1 = MSBPosition(L);
 
    // Find the MSB
    // position in R
    int msb_p2 = MSBPosition(R);
 
    while (msb_p1 == msb_p2)
    {
        long res_val = (1 << msb_p1);
 
        // Add this value until
        // msb_p1 and msb_p2 are same;
        res += res_val;
 
        L -= res_val;
        R -= res_val;
 
        // Calculate msb_p1
        // and msb_p2
        msb_p1 = MSBPosition(L);
        msb_p2 = MSBPosition(R);
    }
     
    // Find the max of
    // msb_p1 and msb_p2
    msb_p1 = Math.Max(msb_p1,
                      msb_p2);
 
    // Set all the bits
    // from msb_p1 upto
    // 0th bit in the result
    for (int i = msb_p1; i >= 0; i--)
    {
        long res_val = (1 << i);
        res += res_val;
    }
    return res;
}
 
// Driver Code
public static void Main ()
{
    int L = 12, R = 18;
    Console.WriteLine(findBitwiseOR(L, R));
}
}
 
// This code is contributed
// by anuj_67.

PHP

<?php
// PHP Program to find the
// bitwise OR of all the
// integers in range L-R
 
// Returns the Most Significant
// Bit Position (MSB)
function MSBPosition($N)
{
    $msb_p = -1;
    while ($N)
    {
        $N = $N >> 1;
        $msb_p++;
    }
    return $msb_p;
}
 
// Returns the Bitwise
// OR of all integers
// between L and R
function findBitwiseOR($L, $R)
{
    $res = 0;
 
    // Find the MSB
    // position in L
    $msb_p1 = MSBPosition($L);
 
    // Find the MSB
    // position in R
    $msb_p2 = MSBPosition($R);
 
    while ($msb_p1 == $msb_p2)
    {
        $res_val = (1 << $msb_p1);
 
        // Add this value until
        // msb_p1 and msb_p2 are same;
        $res += $res_val;
 
        $L -= $res_val;
        $R -= $res_val;
 
        // Calculate msb_p1
        // and msb_p2
        $msb_p1 = MSBPosition($L);
        $msb_p2 = MSBPosition($R);
    }
     
    // Find the max of
    // msb_p1 and msb_p2
    $msb_p1 = max($msb_p1,
                  $msb_p2);
 
    // Set all the bits from msb_p1
    // upto 0th bit in the result
    for ($i = $msb_p1; $i >= 0; $i--)
    {
        $res_val = (1 << $i);
        $res += $res_val;
    }
    return $res;
}
 
// Driver Code
$L = 12; $R = 18;
echo findBitwiseOR($L, $R);
 
// This code is contributed
// by anuj_67.
?>

Javascript

<script>
    // Javascript Program to find
    // the bitwise OR of all
    // the integers in range L-R
     
    // Returns the Most Significant
    // Bit Position (MSB)
    function MSBPosition(N)
    {
        let msb_p = -1;
        while (N > 0)
        {
            N = N >> 1;
            msb_p++;
        }
        return msb_p;
    }
 
    // Returns the Bitwise
    // OR of all integers
    // between L and R
    function findBitwiseOR(L, R)
    {
        let res = 0;
 
        // Find the MSB
        // position in L
        let msb_p1 = MSBPosition(L);
 
        // Find the MSB
        // position in R
        let msb_p2 = MSBPosition(R);
 
        while (msb_p1 == msb_p2)
        {
            let res_val = (1 << msb_p1);
 
            // Add this value until
            // msb_p1 and msb_p2 are same;
            res += res_val;
 
            L -= res_val;
            R -= res_val;
 
            // Calculate msb_p1
            // and msb_p2
            msb_p1 = MSBPosition(L);
            msb_p2 = MSBPosition(R);
        }
 
        // Find the max of
        // msb_p1 and msb_p2
        msb_p1 = Math.max(msb_p1,
                          msb_p2);
 
        // Set all the bits
        // from msb_p1 upto
        // 0th bit in the result
        for (let i = msb_p1; i >= 0; i--)
        {
            let res_val = (1 << i);
            res += res_val;
        }
        return res;
    }
     
    let L = 12, R = 18;
    document.write(findBitwiseOR(L, R));
     
</script>
Producción: 

31

 

Complejidad temporal: O(N), donde N es el bit más significativo. 
 

Publicación traducida automáticamente

Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *