Dados dos números n1 y n2 . La tarea es encontrar la posición del primer bit que no coincide en la representación binaria de los dos números de la izquierda. Necesitamos encontrar este bit después de hacer iguales las longitudes de las representaciones binarias de ambos números. Hacemos que las longitudes sean iguales agregando ceros en el número más pequeño.
Nota :
- Por ejemplo : n1 = 1, n2 = 7. La representación binaria de n1 y n2 será «1» y «111» respectivamente. Agregue dos ceros a n1 para convertirlo en «100».
- Imprime cero si n1 es igual a n2.
Ejemplos :
Input: n1 = 12, n2 = 34 Output: 2 Binary representation of 12 is 1100 and of 34 is 100010. First make both representations of the same length by appending 0s. So the first representation now becomes 11000. The second bit is the different bit. Input: n1 = 1, n2 = 2 Output: 2
Para encontrar la posición del bit diferente más a la izquierda entre la representación de bits de dos números, se puede hacer una comparación bit a bit o se puede usar una fórmula derivada. Aunque la complejidad del tiempo para ambos es la misma.
Para encontrar el bit más diferente a la izquierda, primero iguale la longitud de bits de ambos números multiplicando el más pequeño con pow (2, diferencia de longitud de bits). Después de igualar la longitud de bits, tome XOR de ambos números. Ahora, el bit diferente más a la izquierda se refleja claramente en el valor XOR. Restar la longitud en bits del valor XOR de la longitud en bits del número dado más 1 es la posición del bit diferente más a la izquierda que se puede concluir.
Algoritmo:
- Encuentre la longitud de bits de n1 y n2.
- Iguale la longitud en bits de ambos números colocando cero a la derecha del número más pequeño (lo mismo que multiplicar uno más pequeño por pow (2, diferencia de longitud en bits))
- Toma XOR de ambos números
- La diferencia entre la longitud en bits de cualquier número y la longitud en bits del valor XOR requiere una respuesta más 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the leftmost
// position of first dis-similar bit
#include <bits/stdc++.h>
using namespace std;
// Function to find first dis-similar bit
int bitPos(int n1, int n2)
{
// return zero for equal number
if (n1 == n2)
return 0;
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
int bitCount1 = floor(log2(n1)) + 1;
int bitCount2 = floor(log2(n2)) + 1;
// find bit difference and maxBit
int bitDiff = abs(bitCount1 - bitCount2);
int maxBitCount = max(bitCount1, bitCount2);
if (bitCount1 > bitCount2) {
n2 = n2 * pow(2, bitDiff);
}
else {
n1 = n1 * pow(2, bitDiff);
}
int xorValue = n1 ^ n2;
int bitCountXorValue = floor(log2(xorValue)) + 1;
int disSimilarBitPosition = maxBitCount - bitCountXorValue + 1;
return disSimilarBitPosition;
}
// Driver program
int main()
{
int n1 = 53, n2 = 55;
cout << bitPos(n1, n2);
return 0;
}
Java
// Java program to find the leftmost position of
// first dis-similar bit
import java.io.*;
class GFG {
// Function to find first dis-similar bit
static int bitPos(int n1, int n2)
{
// return zero for equal number
if (n1 == n2)
return 0;
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
int bitCount1 = (int)Math.floor(Math.log(n1) /
Math.log(2)) + 1;
int bitCount2 = (int)Math.floor(Math.log(n2) /
Math.log(2)) + 1;
// find bit difference and maxBit
int bitDiff = Math.abs(bitCount1 - bitCount2);
int maxBitCount = Math.max(bitCount1,
bitCount2);
if (bitCount1 > bitCount2)
{
n2 = n2 * (int)Math.pow(2, bitDiff);
}
else
{
n1 = n1 * (int)Math.pow(2, bitDiff);
}
int xorValue = n1 ^ n2;
int bitCountXorValue = (int)Math.floor(Math.log(xorValue) /
Math.log(2)) + 1;
int disSimilarBitPosition = maxBitCount -
bitCountXorValue + 1;
return disSimilarBitPosition;
}
// Driver Code
public static void main (String[] args) {
int n1 = 53, n2 = 55;
System.out.println(bitPos(n1, n2));
}
}
// This code is contributed by ajit
Python3
# Python3 program to Find the leftmost # position of first dis-similar bit # from math lib import floor() # and log2() from math import floor, log2 # Function to find first # dis-similar bit def bitPos(n1, n2) : # return zero for equal number if n1 == n2 : return 0 # find the 1st dis-similar bit # count bit length of n1 and n bitCount1 = floor(log2(n1)) + 1 bitCount2 = floor(log2(n2)) + 1 # find bit difference and maxBit bitDiff = abs(bitCount1 - bitCount2) maxBitCount = max(bitCount1, bitCount2) if (bitCount1 > bitCount2) : n2 *= pow(2, bitDiff) else : n1 *= pow(2, bitDiff) xorValue = n1 ^ n2 bitCountXorValue = floor(log2(xorValue)) + 1 disSimilarBitPosition = (maxBitCount - bitCountXorValue + 1) return disSimilarBitPosition # Driver code if __name__ == "__main__" : n1, n2 = 53, 55 print(bitPos(n1, n2)) # This code is contributed by Ryuga
C#
// C# to find the leftmost position of
// first dis-similar bit
using System;
class GFG
{
// Function to find first dis-similar bit
static int bitPos(int n1, int n2)
{
// return zero for equal number
if (n1 == n2)
return 0;
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
int bitCount1 = (int)Math.Floor(Math.Log(n1) /
Math.Log(2)) + 1;
int bitCount2 = (int)Math.Floor(Math.Log(n2) /
Math.Log(2)) + 1;
// find bit difference and maxBit
int bitDiff = Math.Abs(bitCount1 - bitCount2);
int maxBitCount = Math.Max(bitCount1,
bitCount2);
if (bitCount1 > bitCount2)
{
n2 = n2 * (int)Math.Pow(2, bitDiff);
}
else
{
n1 = n1 * (int)Math.Pow(2, bitDiff);
}
int xorValue = n1 ^ n2;
int bitCountXorValue = (int)Math.Floor(Math.Log(xorValue) /
Math.Log(2)) + 1;
int disSimilarBitPosition = maxBitCount -
bitCountXorValue + 1;
return disSimilarBitPosition;
}
// Driver Code
public static void Main()
{
int n1 = 53, n2 = 55;
Console.Write(bitPos(n1, n2));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program to find the leftmost
// position of first dis-similar bit
// Function to find first dis-similar bit
function bitPos($n1, $n2)
{
// return zero for equal number
if ($n1 == $n2)
return 0;
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
$bitCount1 = floor(log($n1, 2)) + 1;
$bitCount2 = floor(log($n2, 2)) + 1;
// find bit difference and maxBit
$bitDiff = abs($bitCount1 - $bitCount2);
$maxBitCount = max($bitCount1, $bitCount2);
if ($bitCount1 > $bitCount2)
{
$n2 = $n2 * pow(2, $bitDiff);
}
else {
$n1 = $n1 * pow(2, $bitDiff);
}
$xorValue = $n1 ^ $n2;
$bitCountXorValue = floor(log($xorValue, 2)) + 1;
$disSimilarBitPosition = $maxBitCount -
$bitCountXorValue + 1;
return $disSimilarBitPosition;
}
// Driver Code
$n1 = 53;
$n2 = 55;
echo bitPos($n1, $n2);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find the leftmost
// position of first dis-similar bit
// Function to find first dis-similar bit
function bitPos(n1, n2)
{
// Return zero for equal number
if (n1 == n2)
return 0;
// Find the 1st dis-similar bit
// count bit length of n1 and n2
let bitCount1 = Math.floor(Math.log2(n1)) + 1;
let bitCount2 = Math.floor(Math.log2(n2)) + 1;
// find bit difference and maxBit
let bitDiff = Math.abs(bitCount1 - bitCount2);
let maxBitCount = Math.max(bitCount1, bitCount2);
if (bitCount1 > bitCount2)
{
n2 = n2 * Math.pow(2, bitDiff);
}
else
{
n1 = n1 * Math.pow(2, bitDiff);
}
let xorValue = n1 ^ n2;
let bitCountXorValue = Math.floor(
Math.log2(xorValue)) + 1;
let disSimilarBitPosition = maxBitCount -
bitCountXorValue + 1;
return disSimilarBitPosition;
}
// Driver code
let n1 = 53, n2 = 55;
document.write(bitPos(n1, n2));
// This code is contributed by Manoj.
</script>
Producción:
5
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA