El valor más grande posible de M que no exceda N teniendo el mismo Bitwise OR y XOR entre ellos

Dado un número entero N , la tarea es encontrar el número más grande M , donde ( M < N ), tal que N(XOR)M sea igual a N(OR)M , es decir , (N ^ M) = (N | M) .

Ejemplos: 
 

Entrada: N = 5 
Salida:
5 ^ 4 = 1 y 5 | 4 = 5. Por lo tanto, XOR y OR entre ellos no son iguales. 
5^3 = 6 y 5 | 3 = 7. Por lo tanto, XOR y OR entre ellos no son iguales. 
5^2 = 7 y 5 | 2 = 7. Por lo tanto, XOR y OR entre ellos son iguales.
Entrada: N = 14 
Salida:
 

Enfoque: 
para obtener el número M requerido , recorra todos los bits de N desde su bit menos significativo (LSB) hasta su bit más significativo (MSB). Aquí surgen dos casos: 
 

  1. Si el i -ésimo bit de N es 1 entonces: 
    • Si el i -ésimo bit de M se establece en 1 , entonces N^M no será igual a N|M como (1^1 = 0) y (1|1 = 1) .
    • Si el i -ésimo bit se establece de M a 0 , entonces N^M será igual a N|M como (1^0 = 1) y (1|0 = 1) .
    • Entonces, si el i -ésimo bit de N es 1 , establezca el i -ésimo bit de M en 0 .
  2. Si el i -ésimo bit de N es 0 entonces: 
    • Si el i -ésimo bit de M se establece en 1 , entonces N^M será igual a N|M como ( 0^1 = 1 ) y ( 0|1 = 1 ).
    • Si establecemos el i -ésimo bit de M en 0 , entonces N^M será igual a N|M como ( 0^0 = 0 ) y ( 0|0 = 0 ).
    • Entonces, si el i -ésimo bit de M se establece en 0 o 1 , N^M siempre será igual a N|M .
    • Como se debe encontrar el valor más grande de M que es menor que N , siempre establezca el i -ésimo bit de M en 1 .

Ilustración: 
 

  • norte = 5
  • representación de 32 bits de 5 = 00000000000000000000000000000101
  • Índice LSB de 5 = 31
  • índice MSB de 5 = 29
  • Pasando de LSB a MSB, es decir, de 31 a 29:
    • Para el índice 31, N[31] = 1. Por lo tanto, M[31] debe establecerse en 0.
    • Para el índice 30, N[30] = 0. Por lo tanto, M[30] debe establecerse en 1.
    • Para el índice 29, N[29] = 1. Por lo tanto, M[29] debe establecerse en 0.
  • Así, la representación de 32 bits de M es 000000000000000000000000000000010, que es igual a 2 en representación decimal.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find required
// number M
int equalXORandOR(int n)
{
    // Initialising m
    int m = 0;
 
    // Finding the index of the
    // most significant bit of N
    int MSB = (int)log2(n);
 
    // Calculating required number
    for (int i = 0; i <= MSB; i++) {
 
        if (!(n & (1 << i))) {
            m += (1 << i);
        }
    }
 
    return m;
}
 
// Driver Code
int main()
{
    int n = 14;
    cout << equalXORandOR(n);
    return 0;
}

Java

// Java program to implement
// the above approach
class GFG{
 
// Function to find required
// number M
static int equalXORandOR(int n)
{
     
    // Initialising m
    int m = 0;
 
    // Finding the index of the
    // most significant bit of N
    int MSB = (int)Math.log(n);
 
    // Calculating required number
    for(int i = 0; i <= MSB; i++)
    {
        if ((n & (1 << i)) <= 0)
        {
            m += (1 << i);
        }
    }
    return m;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 14;
     
    System.out.print(equalXORandOR(n));
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program to implement
# the above approach
from math import log2
 
# Function to find required
# number M
def equalXORandOR(n):
 
    # Initialising m
    m = 0
 
    # Finding the index of the
    # most significant bit of N
    MSB = int(log2(n))
 
    # Calculating required number
    for i in range(MSB + 1):
        if(not(n & (1 << i))):
            m += (1 << i)
 
    return m
 
# Driver Code
n = 14
 
# Function call
print(equalXORandOR(n))
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to find required
// number M
static int equalXORandOR(int n)
{
     
    // Initialising m
    int m = 0;
 
    // Finding the index of the
    // most significant bit of N
    int MSB = (int)Math.Log(n);
 
    // Calculating required number
    for(int i = 0; i <= MSB; i++)
    {
        if ((n & (1 << i)) <= 0)
        {
            m += (1 << i);
        }
    }
    return m;
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 14;
     
    Console.Write(equalXORandOR(n));
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
 
// javascript program to implement
// the above approach   
// Function to find required
    // number M
    function equalXORandOR(n) {
 
        // Initialising m
        var m = 0;
 
        // Finding the index of the
        // most significant bit of N
        var MSB = parseInt( Math.log(n));
 
        // Calculating required number
        for (i = 0; i <= MSB; i++) {
            if ((n & (1 << i)) <= 0) {
                m += (1 << i);
            }
        }
        return m;
    }
 
    // Driver Code
     
        var n = 14;
 
        document.write(equalXORandOR(n));
 
// This code contributed by Rajput-Ji
 
</script>
Producción: 

1

 

Complejidad de tiempo: O(log 2 N) 
Espacio auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por doreamon_ 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 *