Posición del bit común más a la derecha en dos números

Dados dos números no negativos m y n . Encuentre la posición del mismo bit más a la derecha en la representación binaria de los números.

Ejemplos:  

Input : m = 10, n = 9
Output : 3
(10)10 = (1010)2
(9)10 = (1001)2
It can be seen that the 3rd bit
from the right is same.

Input : m = 16, n = 7
Output : 4
(16)10 = (10000)2
(7)10 = (111)2, can also be written as
     = (00111)2
It can be seen that the 4th bit
from the right is same.

Enfoque: obtenga el xor bit a bit de m y n . Sea xor_value = m ^ n. Ahora, obtenga la posición del bit no establecido más a la derecha en xor_value .

Explicación: la operación xor bit a bit produce un número que tiene bits no establecidos solo en las posiciones donde los bits de m y n son iguales. Por lo tanto, la posición del bit no establecido más a la derecha en xor_value da la posición del mismo bit más a la derecha.

C++

// C++ implementation to find the position
// of rightmost same bit
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the position of
// rightmost set bit in 'n'
int getRightMostSetBit(unsigned int n)
{
    return log2(n & -n) + 1;
}
 
// Function to find the position of
// rightmost same bit in the
// binary representations of 'm' and 'n'
int posOfRightMostSameBit(unsigned int m,
                          unsigned int n)
{
    // position of rightmost same bit
    return getRightMostSetBit(~(m ^ n));
}
 
// Driver program to test above
int main()
{
    int m = 16, n = 7;
    cout << "Position = "
         << posOfRightMostSameBit(m, n);
    return 0;
}

Java

// Java implementation to find the position
// of rightmost same bit
class GFG {
         
    // Function to find the position of
    // rightmost set bit in 'n'
    static int getRightMostSetBit(int n)
    {
        return (int)((Math.log(n & -n))/(Math.log(2)))
                                                  + 1;
    }
     
    // Function to find the position of
    // rightmost same bit in the
    // binary representations of 'm' and 'n'
    static int posOfRightMostSameBit(int m,int n)
    {
         
        // position of rightmost same bit
        return getRightMostSetBit(~(m ^ n));
    }
     
    //Driver code
    public static void main (String[] args)
    {
        int m = 16, n = 7;
         
        System.out.print("Position = "
            + posOfRightMostSameBit(m, n));
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 implementation to find the
# position of rightmost same bit
import math
 
# Function to find the position
# of rightmost set bit in 'n'
def getRightMostSetBit(n):
 
    return int(math.log2(n & -n)) + 1
 
# Function to find the position of
# rightmost same bit in the binary
# representations of 'm' and 'n'
def posOfRightMostSameBit(m, n):
 
    # position of rightmost same bit
    return getRightMostSetBit(~(m ^ n))
 
# Driver Code
m, n = 16, 7
print("Position = ", posOfRightMostSameBit(m, n))
 
# This code is contributed by Anant Agarwal.

C#

// C# implementation to find the position
// of rightmost same bit
using System;
 
class GFG
{
    // Function to find the position of
    // rightmost set bit in 'n'
    static int getRightMostSetBit(int n)
    {
        return (int)((Math.Log(n & -n)) / (Math.Log(2))) + 1;
    }
      
    // Function to find the position of
    // rightmost same bit in the
    // binary representations of 'm' and 'n'
    static int posOfRightMostSameBit(int m,int n)
    {
        // position of rightmost same bit
        return getRightMostSetBit(~(m ^ n));
    }
     
    //Driver code
    public static void Main ()
    {
        int m = 16, n = 7;
        Console.Write("Position = "
              + posOfRightMostSameBit(m, n));
    }
}
//This code is contributed by Anant Agarwal.

PHP

<?php
// PHP implementation to
// find the position
// of rightmost same bit
 
// Function to find the position of
// rightmost set bit in 'n'
function getRightMostSetBit($n)
{
    return log($n & -$n) + 1;
}
 
// Function to find the position of
// rightmost same bit in the
// binary representations of 'm' and 'n'
function posOfRightMostSameBit($m,
                               $n)
{
     
    // position of rightmost same bit
    return getRightMostSetBit(~($m ^ $n));
}
 
    // Driver Code
    $m = 16; $n = 7;
    echo "Position = "
        , ceil(posOfRightMostSameBit($m, $n));
         
// This code is contributed by anuj_67.
?>

Javascript

<script>
// JavaScript implementation to find the position
// of rightmost same bit
 
// Function to find the position of
// rightmost set bit in 'n'
function getRightMostSetBit(n)
{
    return Math.log2(n & -n) + 1;
}
 
// Function to find the position of
// rightmost same bit in the
// binary representations of 'm' and 'n'
function posOfRightMostSameBit(m, n)
{
 
    // position of rightmost same bit
    return getRightMostSetBit(~(m ^ n));
}
 
// Driver program to test above
    let m = 16, n = 7;
    document.write("Position = "
        + posOfRightMostSameBit(m, n));
 
// This code is contributed by Manoj.
</script>

Producción: 

Position = 4

Complejidad de tiempo : O(1)

Espacio Auxiliar: O(1)

Enfoque alternativo: hasta que ambos valores se vuelvan cero, verifique los últimos bits de ambos números y el desplazamiento a la derecha. En cualquier momento, ambos bits son iguales, devuelve el contador.

Explicación: el bit más a la derecha de dos valores m y n son iguales solo cuando ambos valores son pares o impares. 

C++

// C++ implementation to find the position
// of rightmost same bit
#include <iostream>
using namespace std;
     
// Function to find the position of
// rightmost same bit in the binary
// representations of 'm' and 'n'
static int posOfRightMostSameBit(int m, int n)
{
     
    // Initialize loop counter
    int loopCounter = 1;
     
    while (m > 0 || n > 0)
    {
         
        // Check whether the value 'm' is odd
        bool a = m % 2 == 1;
         
        // Check whether the value 'n' is odd
        bool b = n % 2 == 1;
         
        // Below 'if' checks for both
        // values to be odd or even
        if (!(a ^ b))
        {
            return loopCounter;
        }
         
        // Right shift value of m
        m = m >> 1;
         
        // Right shift value of n
        n = n >> 1;
        loopCounter++;
    }
     
    // When no common set is found
    return -1;
}
 
// Driver code
int main()
{
    int m = 16, n = 7;
     
    cout << "Position = "
         <<  posOfRightMostSameBit(m, n);
}
 
// This code is contributed by shivanisinghss2110

Java

// Java implementation to find the position
// of rightmost same bit
class GFG {
     
    // Function to find the position of
    // rightmost same bit in the
    // binary representations of 'm' and 'n'
    static int posOfRightMostSameBit(int m,int n)
    {
        int loopCounter = 1; // Initialize loop counter
        while (m > 0 || n > 0){
             
            boolean a = m%2 == 1; //Check whether the value 'm' is odd
            boolean b = n%2 == 1; //Check whether the value 'n' is odd
             
            // Below 'if' checks for both values to be odd or even
            if (!(a ^ b)){
                return loopCounter;}
             
            m = m >> 1; //Right shift value of m
            n = n >> 1; //Right shift value of n
            loopCounter++;
        }
        return -1; //When no common set is found
    }
       
    //Driver code
    public static void main (String[] args)
    {
        int m = 16, n = 7;
           
        System.out.print("Position = "
            + posOfRightMostSameBit(m, n));
    }
}

Python3

# Python3 implementation to find the position
# of rightmost same bit
 
# Function to find the position of
# rightmost same bit in the
# binary representations of 'm' and 'n'
def posOfRightMostSameBit(m, n):
     
    # Initialize loop counter
    loopCounter = 1
     
    while (m > 0 or n > 0):
         
        # Check whether the value 'm' is odd
        a = m % 2 == 1
         
        # Check whether the value 'n' is odd
        b = n % 2 == 1
 
        # Below 'if' checks for both
        # values to be odd or even
        if (not (a ^ b)):
            return loopCounter
             
        # Right shift value of m
        m = m >> 1
         
        # Right shift value of n
        n = n >> 1
        loopCounter += 1
         
    # When no common set is found
    return -1
 
# Driver code
if __name__ == '__main__':
     
    m, n = 16, 7
 
    print("Position = ",
    posOfRightMostSameBit(m, n))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation to find the position
// of rightmost same bit
using System;
class GFG
{
 
  // Function to find the position of
  // rightmost same bit in the
  // binary representations of 'm' and 'n'
  static int posOfRightMostSameBit(int m, int n)
  {
    int loopCounter = 1; // Initialize loop counter
    while (m > 0 || n > 0)
    {
 
      Boolean a = m % 2 == 1; // Check whether the value 'm' is odd
      Boolean b = n % 2 == 1; // Check whether the value 'n' is odd
 
      // Below 'if' checks for both values to be odd or even
      if (!(a ^ b))
      {
        return loopCounter;
      }
 
      m = m >> 1; // Right shift value of m
      n = n >> 1; // Right shift value of n
      loopCounter++;
    }
    return -1; // When no common set is found
  }
 
  // Driver code
  public static void Main (String[] args)
  {
    int m = 16, n = 7;        
    Console.Write("Position = "
                  + posOfRightMostSameBit(m, n));
  }
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// JavaScript implementation to find the position
// of rightmost same bit
     
// Function to find the position of
// rightmost same bit in the binary
// representations of 'm' and 'n'
function posOfRightMostSameBit(m, n)
{
     
    // Initialize loop counter
    let loopCounter = 1;
     
    while (m > 0 || n > 0)
    {
         
        // Check whether the value 'm' is odd
        let a = m % 2 == 1;
         
        // Check whether the value 'n' is odd
        let b = n % 2 == 1;
         
        // Below 'if' checks for both
        // values to be odd or even
        if (!(a ^ b))
        {
            return loopCounter;
        }
         
        // Right shift value of m
        m = m >> 1;
         
        // Right shift value of n
        n = n >> 1;
        loopCounter++;
    }
     
    // When no common set is found
    return -1;
}
 
// Driver code
    let m = 16, n = 7;
     
    document.write("Position = "
        + posOfRightMostSameBit(m, n));
 
// This code is contributed by Manoj.
</script>

Producción: 

Position = 4

Complejidad de tiempo : O(1)

Espacio Auxiliar: O(1)

Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

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