Encuentre el número obtenido después de la concatenación de la representación binaria de M y N

Dados dos enteros M y N , la tarea es encontrar el número formado al concatenar los equivalentes binarios de M y N , es decir , M + N.

Ejemplos: 

Entrada: M = 4, N = 5 
Salida: 37 
El equivalente binario de 4 es 100 y para 5 es 101 
después de la concatenación, el número binario resultante 
formado es 100101 cuyo equivalente decimal es 37.

Entrada: M = 3, N = 4 
Salida: 28 

Enfoque: convierta los números M y N en sus equivalentes binarios, luego concatene estos números como M + N e imprima el equivalente decimal del número binario resultante formado después de la concatenación.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to convert decimal number n
// to its binary representation
// stored as an array arr[]
void decBinary(int arr[], int n)
{
    int k = log2(n);
    while (n > 0) {
        arr[k--] = n % 2;
        n /= 2;
    }
}
 
// Function to convert the number
// represented as a binary array
// arr[] into its decimal equivalent
int binaryDec(int arr[], int n)
{
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans += arr[i] << (n - i - 1);
    return ans;
}
 
// Function to concatenate the binary
// numbers and return the decimal result
int concat(int m, int n)
{
 
    // Number of bits in both the numbers
    int k = log2(m) + 1;
    int l = log2(n) + 1;
 
    // Convert the bits in both the integers
    // to the arrays a[] and b[]
    int a[k] = { 0 }, b[l] = { 0 };
 
    // c[] will be the binary array
    // for the result
    int c[k + l] = { 0 };
    decBinary(a, m);
    decBinary(b, n);
 
    // Update the c[] array
    int in = 0;
    for (int i = 0; i < k; i++)
        c[in++] = a[i];
    for (int i = 0; i < l; i++)
        c[in++] = b[i];
 
    // Return the decimal equivalent
    // of the result
    return (binaryDec(c, k + l));
}
 
// Driver code
int main()
{
    int m = 4, n = 5;
 
    cout << concat(m, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to convert decimal number n
    // to its binary representation
    // stored as an array arr[]
    static void decBinary(int arr[], int n)
    {
        int k = (int)(Math.log(n) /
                      Math.log(2));
         
        while (n > 0)
        {
            arr[k--] = n % 2;
            n /= 2;
        }
    }
     
    // Function to convert the number
    // represented as a binary array
    // arr[] into its decimal equivalent
    static int binaryDec(int arr[], int n)
    {
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += arr[i] << (n - i - 1);
        return ans;
    }
     
    // Function to concatenate the binary
    // numbers and return the decimal result
    static int concat(int m, int n)
    {
     
        // Number of bits in both the numbers
        int k = (int)(Math.log(m) /
                      Math.log(2)) + 1;
        int l = (int)(Math.log(n) /
                      Math.log(2)) + 1;
     
        // Convert the bits in both the integers
        // to the arrays a[] and b[]
        int a[] = new int[k];
        int b[] = new int[l];
     
        // c[] will be the binary array
        // for the result
        int c[] = new int[k + l];
        decBinary(a, m);
        decBinary(b, n);
     
        // Update the c[] array
        int in = 0;
        for (int i = 0; i < k; i++)
            c[in++] = a[i];
        for (int i = 0; i < l; i++)
            c[in++] = b[i];
     
        // Return the decimal equivalent
        // of the result
        return (binaryDec(c, k + l));
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int m = 4, n = 5;
     
        System.out.println(concat(m, n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
import math
 
# Function to convert decimal number n
# to its binary representation
# stored as an array arr[]
def decBinary(arr, n):
    k = int(math.log2(n))
    while (n > 0):
        arr[k] = n % 2
        k = k - 1
        n = n//2
 
# Function to convert the number
# represented as a binary array
# arr[] its decimal equivalent
def binaryDec(arr, n):
    ans = 0
    for i in range(0, n):
        ans = ans + (arr[i] << (n - i - 1))
    return ans
 
# Function to concatenate the binary
# numbers and return the decimal result
def concat(m, n):
 
    # Number of bits in both the numbers
    k = int(math.log2(m)) + 1
    l = int(math.log2(n)) + 1
 
    # Convert the bits in both the gers
    # to the arrays a[] and b[]
    a = [0 for i in range(0, k)]
    b = [0 for i in range(0, l)]
 
    # c[] will be the binary array
    # for the result
    c = [0 for i in range(0, k + l)]
    decBinary(a, m);
    decBinary(b, n);
 
    # Update the c[] array
    iin = 0
    for i in range(0, k):
        c[iin] = a[i]
        iin = iin + 1
    for i in range(0, l):
        c[iin] = b[i]
        iin = iin + 1
 
    # Return the decimal equivalent
    # of the result
    return (binaryDec(c, k + l))
 
# Driver code
m = 4
n = 5
 
print(concat(m, n))
 
# This code is contributed by Sanjit_Prasad

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to convert decimal number n
    // to its binary representation
    // stored as an array []arr
    static void decBinary(int []arr, int n)
    {
        int k = (int)(Math.Log(n) /
                      Math.Log(2));
         
        while (n > 0)
        {
            arr[k--] = n % 2;
            n /= 2;
        }
    }
     
    // Function to convert the number
    // represented as a binary array
    // []arr into its decimal equivalent
    static int binaryDec(int []arr, int n)
    {
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += arr[i] << (n - i - 1);
        return ans;
    }
     
    // Function to concatenate the binary
    // numbers and return the decimal result
    static int concat(int m, int n)
    {
     
        // Number of bits in both the numbers
        int k = (int)(Math.Log(m) /
                      Math.Log(2)) + 1;
        int l = (int)(Math.Log(n) /
                      Math.Log(2)) + 1;
     
        // Convert the bits in both the integers
        // to the arrays []a and []b
        int []a = new int[k];
        int []b = new int[l];
     
        // c[] will be the binary array
        // for the result
        int []c = new int[k + l];
        decBinary(a, m);
        decBinary(b, n);
     
        // Update the c[] array
        int iN = 0;
        for (int i = 0; i < k; i++)
            c[iN++] = a[i];
        for (int i = 0; i < l; i++)
            c[iN++] = b[i];
     
        // Return the decimal equivalent
        // of the result
        return (binaryDec(c, k + l));
    }
     
    // Driver code
    public static void Main(String[] args)
    {
        int m = 4, n = 5;
     
        Console.WriteLine(concat(m, n));
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
    // Javascript implementation of the approach
     
    // Function to convert decimal number n
    // to its binary representation
    // stored as an array []arr
    function decBinary(arr, n)
    {
        let k = parseInt(Math.log(n) / Math.log(2), 10);
          
        while (n > 0)
        {
            arr[k--] = n % 2;
            n = parseInt(n / 2, 10);
        }
    }
      
    // Function to convert the number
    // represented as a binary array
    // []arr into its decimal equivalent
    function binaryDec(arr, n)
    {
        let ans = 0;
        for (let i = 0; i < n; i++)
            ans += arr[i] << (n - i - 1);
        return ans;
    }
      
    // Function to concatenate the binary
    // numbers and return the decimal result
    function concat(m, n)
    {
      
        // Number of bits in both the numbers
        let k = parseInt(Math.log(m) / Math.log(2), 10) + 1;
        let l = parseInt(Math.log(n) / Math.log(2), 10) + 1;
      
        // Convert the bits in both the integers
        // to the arrays []a and []b
        let a = new Array(k);
        let b = new Array(l);
      
        // c[] will be the binary array
        // for the result
        let c = new Array(k + l);
        decBinary(a, m);
        decBinary(b, n);
      
        // Update the c[] array
        let iN = 0;
        for (let i = 0; i < k; i++)
            c[iN++] = a[i];
        for (let i = 0; i < l; i++)
            c[iN++] = b[i];
      
        // Return the decimal equivalent
        // of the result
        return (binaryDec(c, k + l));
    }
     
    let m = 4, n = 5;
      
    document.write(concat(m, n));
     
    // This code is contributed by rameshtravel07.
</script>

37

La complejidad temporal de la solución anterior es O(log(m) + log(n)) .

Podemos mejorar la complejidad del tiempo para el problema anterior a O(log(n)) mediante el uso de operadores de desplazamiento binario .

Mejor enfoque : 

Desplazaremos binariamente el número M a la izquierda por el número de bits en n.

Por ejemplo:

M=4, N=5

bin(N) = 101 que tiene representación binaria tres.

Dejaremos el desplazamiento binario M por 3 y luego agregaremos N.

M<<3 + N = 37.

Como los operadores de desplazamiento binario toman un tiempo constante , el segundo paso se realiza en un tiempo constante y la complejidad del tiempo general es O(log(N)) .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to calculate binary
// length of a number.
int getBinaryLength(int n)
{
    int length = 0;
    while (n > 0) {
        length += 1;
        n /= 2;
    }
    return length;
}
 
// Function to concatenate the binary
// numbers and return the decimal result
int concat(int m, int n)
{
    // find binary length of n
    int length = getBinaryLength(n);
 
    // left binary shift m and then add n
    return (m << length) + n;
}
 
// Driver code
int main()
{
    int m = 4, n = 5;
 
    cout << concat(m, n);
 
    return 0;
}
 
// This code is contributed by Vivek Moar

// Java implementation of the approach
import java.util.*;
 
class GFG{
     
// Utility function to calculate binary
// length of a number.
public static int getBinaryLength(int n)
{
    int length = 0;
    while (n > 0)
    {
        length += 1;
        n /= 2;
    }
    return length;
}
  
// Function to concatenate the binary
// numbers and return the decimal result
public static int concat(int m, int n)
{
     
    // Find binary length of n
    int length = getBinaryLength(n);
     
    // left binary shift m and then add n
    return (m << length) + n;
}
 
// Driver code
public static void main(String[] args) throws Exception
{
    int m = 4, n = 5;
 
    System.out.println(concat(m, n));
}
}
 
// This code is contributed by divyesh072019

# Python3 implementation of the approach
 
# Utility function to calculate binary
# length of a number.
 
 
def getBinaryLength(n):
    length = 0
    while(n > 0):
        length += 1
        n //= 2
    return length
 
# Function to concatenate the binary
# numbers and return the decimal result
 
 
def concat(m, n):
    # find binary length of n
    length = getBinaryLength(n)
 
    # left binary shift m and then add n
    return (m << length) + n
 
# Driver code
 
 
m, n = 4, 5
 
print(concat(m, n))
 
# This code is contributed by Vivek Moar

// C# implementation of the approach
using System;
 
class GFG{
     
// Utility function to calculate binary
// length of a number.
static int getBinaryLength(int n)
{
    int length = 0;
     
    while (n > 0)
    {
        length += 1;
        n /= 2;
    }
    return length;
}
   
// Function to concatenate the binary
// numbers and return the decimal result
static int concat(int m, int n)
{
     
    // Find binary length of n
    int length = getBinaryLength(n);
      
    // left binary shift m and then add n
    return (m << length) + n;
}
 
// Driver code
static void Main()
{
    int m = 4, n = 5;
     
    Console.WriteLine(concat(m, n));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
    // Javascript implementation of the approach
     
    // Utility function to calculate binary
    // length of a number.
    function getBinaryLength(n)
    {
        let length = 0;
 
        while (n > 0)
        {
            length += 1;
            n = parseInt(n / 2, 10);
        }
        return length;
    }
 
    // Function to concatenate the binary
    // numbers and return the decimal result
    function concat(m, n)
    {
 
        // Find binary length of n
        let length = getBinaryLength(n);
 
        // left binary shift m and then add n
        return (m << length) + n;
    }
     
    let m = 4, n = 5;
      
    document.write(concat(m, n));
         
</script>

37

Complejidad de tiempo: O(log(n)) .