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