Умножение двух чисел с оператором сдвига

Опубликовано: 20 Января, 2022

Для любых данных двух чисел n и m вы должны найти n * m без использования оператора умножения.
Примеры :

 Ввод: n = 25, m = 13.
Выход: 325

Ввод: n = 50, m = 16.
Выход: 800

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

We can solve this problem with the shift operator. The idea is based on the fact that every number can be represented in binary form. And multiplication with a number is equivalent to multiplication with powers of 2. Powers of 2 can be obtained using left shift operator.
Check for every set bit in the binary representation of m and for every set bit left shift n, count times where count if place value of the set bit of m and add that value to answer.
 

C++

// CPP program to find multiplication
// of two number without use of
// multiplication operator
#include<bits/stdc++.h>
using namespace std;
 
// Function for multiplication
int multiply(int n, int m)
{ 
    int ans = 0, count = 0;
    while (m)
    {
        // check for set bit and left
        // shift n, count times
        if (m % 2 == 1)             
            ans += n << count;
 
        // increment of place value (count)
        count++;
        m /= 2;
    }
    return ans;
}
 
// Driver code
int main()
{
    int n = 20 , m = 13;
    cout << multiply(n, m);
    return 0;
}

Java

// Java program to find multiplication
// of two number without use of
// multiplication operator
class GFG
{
     
    // Function for multiplication
    static int multiply(int n, int m)
    {
        int ans = 0, count = 0;
        while (m > 0)
        {
            // check for set bit and left
            // shift n, count times
            if (m % 2 == 1)            
                ans += n << count;
     
            // increment of place
            // value (count)
            count++;
            m /= 2;
        }
         
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 20, m = 13;
         
        System.out.print( multiply(n, m) );
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# python 3 program to find multiplication
# of two number without use of
# multiplication operator
 
# Function for multiplication
def multiply(n, m):
    ans = 0
    count = 0
    while (m):
        # check for set bit and left
        # shift n, count times
        if (m % 2 == 1):
            ans += n << count
 
        # increment of place value (count)
        count += 1
        m = int(m/2)
 
    return ans
 
# Driver code
if __name__ == "__main__":
    n = 20
    m = 13
    print(multiply(n, m))
     
# This code is contributed by
# Ssanjit_Prasad

C#

// C# program to find multiplication
// of two number without use of
// multiplication operator
using System;
 
class GFG
{
     
    // Function for multiplication
    static int multiply(int n, int m)
    {
        int ans = 0, count = 0;
        while (m > 0)
        {
            // check for set bit and left
            // shift n, count times
            if (m % 2 == 1)        
                ans += n << count;
     
            // increment of place
            // value (count)
            count++;
            m /= 2;
        }
         
        return ans;
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 20, m = 13;
         
        Console.WriteLine( multiply(n, m) );
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find multiplication
// of two number without use of
// multiplication operator
 
// Function for multiplication
function multiply( $n, $m)
{
    $ans = 0; $count = 0;
    while ($m)
    {
        // check for set bit and left
        // shift n, count times
        if ($m % 2 == 1)            
            $ans += $n << $count;
 
        // increment of place value (count)
        $count++;
        $m /= 2;
    }
    return $ans;
}
 
// Driver code
$n = 20 ; $m = 13;
echo multiply($n, $m);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// JavaScript program to find multiplication
// of two number without use of
// multiplication operator
 
// Function for multiplication
function multiply(n, m)
{
    let ans = 0, count = 0;
    while (m)
    {
        // check for set bit and left
        // shift n, count times
        if (m % 2 == 1)            
            ans += n << count;
 
        // increment of place value (count)
        count++;
        m = Math.floor(m / 2);
    }
    return ans;
}
 
// Driver code
 
    let n = 20 , m = 13;
    document.write(multiply(n, m));
  
// This code is contributed by Surbhi Tyagi.
 
</script>

Выход :

 260

Сложность времени: O (log n)
Связанная статья:
Русский крестьянин (умножьте два числа с помощью побитовых операторов)
Эта статья предоставлена Шивамом Прадханом (anuj_charm). Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ