Dados dos números m y n . Encuentre la posición del bit diferente más a la derecha en la representación binaria de números. Se garantiza que tal bit existe.
Ejemplos:
Input: m = 11, n = 9
Output: 2
(11)10 = (1011)2
(9)10 = (1001)2
It can be seen that 2nd bit from
the right is different
Input: m = 52, n = 4
Output: 5
(52)10 = (110100)2
(4)10 = (100)2, can also be written as
= (000100)2
It can be seen that 5th bit from
the right is different
Enfoque: obtenga el xor bit a bit de m y n . Sea xor_value = m ^ n. Ahora, encuentre la posición del bit 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 establecidos solo en las posiciones donde difieren los bits de m y n . Por lo tanto, la posición del bit establecido más a la derecha en xor_value da la posición del bit diferente más a la derecha.
Efficient way to find the rightmost set bit: log2(n & -n) + 1 gives us the position of the rightmost set bit. (-n) reverses all the bits from left to right till the last set bit for example: n = 16810 binary signed 2's complement of n = 00000000101010002 binary signed 2's complement of -n = 11111111010110002 ∴ (n & -n) = 00000000000010002 = 8 now, log2(n & -n) = log2(8) = 3 log2(n & -n) + 1 = 4 (position of rightmost set bit)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the position
// of rightmost different bit
#include <bits/stdc++.h>
using namespace std;
// Function to find the position of
// rightmost set bit in 'n'
// returns 0 if there is no set bit.
int getRightMostSetBit(int n)
{
// to handle edge case when n = 0.
if (n == 0)
return 0;
return log2(n & -n) + 1;
}
// Function to find the position of
// rightmost different bit in the
// binary representations of 'm' and 'n'
// returns 0 if there is no
// rightmost different bit.
int posOfRightMostDiffBit(int m, int n)
{
// position of rightmost different
// bit
return getRightMostSetBit(m ^ n);
}
// Driver program
int main()
{
int m = 52, n = 24;
cout << "Position of rightmost different bit:"
<< posOfRightMostDiffBit(m, n)<<endl;
return 0;
}
Java
// Java implementation to find the position
// of rightmost different bit
class GFG {
// Function to find the position of
// rightmost set bit in 'n'
// return 0 if there is no set bit.
static int getRightMostSetBit(int n)
{
if(n == 0)
return 0;
return (int)((Math.log10(n & -n)) /
Math.log10(2)) + 1;
}
// Function to find the position of
// rightmost different bit in the
// binary representations of 'm' and 'n'
static int posOfRightMostDiffBit(int m, int n)
{
// position of rightmost different bit
return getRightMostSetBit(m ^ n);
}
// Driver code
public static void main(String arg[])
{
int m = 52, n = 4;
System.out.print("Position = " +
posOfRightMostDiffBit(m, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python implementation
# to find the position
# of rightmost different bit
import math
# Function to find the position of
# rightmost set bit in 'n'
def getRightMostSetBit(n):
if (n == 0):
return 0
return math.log2(n & -n) + 1
# Function to find the position of
# rightmost different bit in the
# binary representations of 'm' and 'n'
def posOfRightMostDiffBit(m, n):
# position of rightmost different
# bit
return getRightMostSetBit(m ^ n)
# Driver code
m = 52
n = 4
print("position = ", int(posOfRightMostDiffBit(m, n)))
# This code is contributed
# by Anant Agarwal.
C#
// C# implementation to find the position
// of rightmost different bit
using System;
class GFG {
// Function to find the position of
// rightmost set bit in 'n'
static int getRightMostSetBit(int n)
{
if (n == 0)
return 0;
return (int)((Math.Log10(n & -n))
/ Math.Log10(2)) + 1;
}
// Function to find the position of
// rightmost different bit in the
// binary representations of 'm' and 'n'
static int posOfRightMostDiffBit(int m, int n)
{
// position of rightmost different bit
return getRightMostSetBit(m ^ n);
}
// Driver code
public static void Main()
{
int m = 52, n = 4;
Console.Write("Position = " +
posOfRightMostDiffBit(m, n));
}
}
// This code is contributed by Smitha.
PHP
<?php
// PHP implementation to
// find the position of
// rightmost different bit
// Function to find the position
// of rightmost set bit in 'n'
function getRightMostSetBit($n)
{
if ($n == 0)
return 0;
return log($n & -$n, (2)) + 1;
}
// Function to find the position of
// rightmost different bit in the
// binary representations of 'm'
// and 'n'
function posOfRightMostDiffBit($m, $n)
{
// position of rightmost
// different bit
return getRightMostSetBit($m ^ $n);
}
// Driver Code
$m = 52;
$n = 4;
echo posOfRightMostDiffBit($m, $n);
// This code is contributed by Ajit
?>
Javascript
<script>
// JavaScript implementation to find the position
// of rightmost different bit
// Function to find the position of
// rightmost set bit in 'n'
// returns 0 if there is no set bit.
function getRightMostSetBit(n)
{
// to handle edge case when n = 0.
if (n == 0)
return 0;
return Math.log2(n & -n) + 1;
}
// Function to find the position of
// rightmost different bit in the
// binary representations of 'm' and 'n'
// returns 0 if there is no
// rightmost different bit.
function posOfRightMostDiffBit(m, n)
{
// position of rightmost different
// bit
return getRightMostSetBit(m ^ n);
}
// Driver program
let m = 52, n = 24;
document.write("Position of rightmost different bit:"
+ posOfRightMostDiffBit(m, n) + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
Producción
Position of rightmost different bit:3
Complejidad del tiempo: O(log 2 n)
Complejidad espacial: O(1)
Usando la función ffs()
C++
// C++ implementation to find the
// position of rightmost different
// bit in two number.
#include <bits/stdc++.h>
using namespace std;
// function to find rightmost different
// bit in two numbers.
int posOfRightMostDiffBit(int m, int n)
{
return ffs(m ^ n);
}
// Driver code
int main()
{
int m = 52, n = 4;
cout <<"Position = " <<
posOfRightMostDiffBit(m, n);
return 0;
}
Java
// Java implementation to find the
// position of rightmost different
// bit in two number.
import java.util.*;
class GFG{
// function to find rightmost
// different bit in two numbers.
static int posOfRightMostDiffBit(int m,
int n)
{
return (int)Math.floor(
Math.log10(
Math.pow(m ^ n,
2)))+2;
}
// Driver code
public static void main(String[] args)
{
int m = 52, n = 4;
System.out.println("Position = " +
posOfRightMostDiffBit(m, n));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation to find the
# position of rightmost different
# bit in two number.
from math import floor, log10
# Function to find rightmost different
# bit in two numbers.
def posOfRightMostDiffBit(m, n):
return floor(log10(pow(m ^ n, 2))) + 2
# Driver code
if __name__ == '__main__':
m, n = 52, 4
print("Position = ",
posOfRightMostDiffBit(m, n))
# This code is contributed by mohit kumar 29
C#
// C# implementation to find the
// position of rightmost different
// bit in two number.
using System;
class GFG
{
// function to find rightmost
// different bit in two numbers.
static int posOfRightMostDiffBit(int m,
int n)
{
return (int)Math.Floor(Math.Log10(
Math.Pow(m ^ n, 2))) + 2;
}
// Driver code
public static void Main(String[] args)
{
int m = 52, n = 4;
Console.Write("Position = " +
posOfRightMostDiffBit(m, n));
}
}
// This code is contributed by shivanisinghss2110
PHP
<?php
// PHP implementation to find the
// position of rightmost different
// bit in two number.
// function to find rightmost
// different bit in two numbers.
function posOfRightMostDiffBit($m, $n)
{
$t = floor(log($m ^ $n, 2));
return $t;
}
// Driver code
$m = 52;
$n = 4;
echo "Position = " ,
posOfRightMostDiffBit($m, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript implementation to find the
// position of rightmost different
// bit in two number.
// function to find rightmost
// different bit in two numbers.
function posOfRightMostDiffBit(m, n)
{
return parseInt(Math.floor
(Math.log10(Math.pow(m ^ n, 2))), 10) + 2;
}
let m = 52, n = 4;
document.write(
"Position = " + posOfRightMostDiffBit(m, n)
);
</script>
Producción
Position = 5
Complejidad del tiempo: O(log 2 n)
Complejidad espacial: 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