Programa para hallar el producto de un número con un Número de Mersenne

Dado un número entero N y un número de Mersenne M , la tarea es imprimir su producto sin usar el operador ‘*’ .
Nota: Los números de Mersenne son aquellos números que son uno menos que una potencia de dos .

Ejemplos:

Entrada: N = 4, M = 15
Salida: 60

Entrada: N = 9, M = 31
Salida: 279

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

Supongamos que M se puede representar como 2X – 1 , entonces el producto de N con M se puede representar como N · 2X – N.

Por lo tanto, el producto de cualquier número de Mersenne con cualquier número N puede representarse como (N << log ₂ (M+1)) – N .

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find product of a
// Mersenne number with another number
long multiplyByMersenne(long N, long M)
{
    // Stores the power of
    // 2 of integer M + 1
    long x = log2(M + 1);
 
    // Return the product
    return ((N << x) - N);
}
 
// Driver Code
int main()
{
    long N = 4;
    long M = 15;
 
    cout << multiplyByMersenne(N, M);
 
    return 0;
}

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG
{
 
// Function to find product of a
// Mersenne number with another number
static long multiplyByMersenne(long N, long M)
{
   
    // Stores the power of
    // 2 of integer M + 1
    long x = (int)(Math.log(M + 1) / Math.log(2));
 
    // Return the product
    return ((N << x) - N);
}
 
// Driver Code
public static void main(String[] args)
{
    long N = 4;
    long M = 15;
 
    System.out.print(multiplyByMersenne(N, M));
}
}
 
// This code is contributed by souravghosh0416.

# Python3 program for the above approach
import math
 
# Function to find product of a
# Mersenne number with another number
def multiplyByMersenne(N, M) :
     
    # Stores the power of
    # 2 of integer M + 1
    x = int(math.log2(M + 1))
 
    # Return the product
    return ((N << x) - N)
 
# Driver Code
N = 4
M = 15
 
print(multiplyByMersenne(N, M))
 
# This code is contributed by sanjoy_62.

// C# program for the above approach
using System;
class GFG{
 
  // Function to find product of a
  // Mersenne number with another number
  static int multiplyByMersenne(int N, int M)
  {
 
    // Stores the power of
    // 2 of integer M + 1
    int x = (int)(Math.Log(M + 1) / Math.Log(2));
 
    // Return the product
    return ((N << x) - N);
  }
 
  // Driver Code
  static public void Main()
  {
    int N = 4;
    int M = 15;
 
    Console.Write(multiplyByMersenne(N, M));
  }
}
 
// This code is contributed by splevel62.

<script>
 
// Javascript implementation of above approach
 
// Function to find product of a
// Mersenne number with another number
function multiplyByMersenne(N, M)
{
   
    // Stores the power of
    // 2 of integer M + 1
    let x = (Math.log(M + 1) / Math.log(2));
 
    // Return the product
    return ((N << x) - N);
}
 
// Driver code
let N = 4;
let M = 15;
 
document.write(multiplyByMersenne(N, M));
 
// This code is contributed by target_2
 
</script>

60

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)