算法设计：如何用移位运算符将两个数相乘？

本文概述

• C++
• Java
• Python3
• C#
• PHP

对于给定的两个数字n和m, 你必须找到n * m而不使用任何乘法运算符。

例子 ：

Input: n = 25 , m = 13
Output: 325

Input: n = 50 , m = 16
Output: 800

我们可以使用移位运算符解决此问题。这个想法基于这样一个事实, 即每个数字都可以二进制形式表示。与数字的乘积等效于乘以2的幂。可以使用左移位运算符获得2的幂。

检查m的二进制表示形式中的每个设置位, 以及每个左移n的设置位, 计数次数, 以计算m的设置位的位置值并将该值相加。

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.
?>

输出：

260

时间复杂度：O(log n)

相关文章：俄罗斯农民(使用按位运算符将两个数字相乘)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。