俄罗斯农夫法的乘法算法，俄罗斯农夫乘法,算法简介： 俄罗斯农夫法

俄罗斯农夫法的乘法算法，俄罗斯农夫乘法,算法简介： 俄罗斯农夫法

算法简介：

俄罗斯农夫法的乘法算法，整数与整数相乘的方法如下：

代码如下：

    import java.util.Scanner;      public class Algorithm_1 {          /**          * 实现俄罗斯农夫法的乘法算法          *           * @param args          */          public static void main(String[] args) {              Scanner sc = new Scanner(System.in);              int m, n, flag,res;              while (true) {                  m = sc.nextInt();                  n = sc.nextInt();                  flag = 0;res=0;                  if (m < 0) {                      m = 0 - m;                      flag = 1;                  }                  if (n < 0) {                      n = 0 - n;                      flag = 1 - flag;                  }                  while (m >= 1) {                      if ((m &amp; 1) == 1) {// odd                          res+=n;                          m=(m-1)>>1;                          n=n<<1;                      }                      else{                          m=m>>1;                          n=n<<1;                      }                  }                  if(0 == flag){                      System.out.println("m &times; n = "+res);                  }else{                      System.out.println("m &times; n = -"+res);                  }              }          }      }      /*      * 测试数据：      * 输入：0 0 输出：0      * 输入：13 18 输出：234      * 输入：-13 18 输出：-234      * 输入：13 -18 输出：-234      * 输入：-13 -18 输出：234      */  

算法分析：首先，对输入的两个整数m和n进行正负判断，我的程序中用到的是flag来标记正负的；既然不能用*/ %等等这些复杂的运算符，那通常的做法是用位运算来进行乘除；然后，m×n得分奇数和偶数两种情况来进行不同的处理。

 具体思路：flag判断正负：当m>0, n>0 时，flag=0；

当m>0, n<0 时，flag=1；

当m<0, n>0 时，flag=1；

当m<0, n<0 时，flag=0；

 这里用两个if来判断即可列出四种情况。 res用来存放结果。 如果m>=1，则分两种情况，

(1)m为奇数

 res加上n的值，然后将m-1右移一位，并将结果赋值给m，

n左移一位，并将结果赋值给n。

    (2)m为偶数            m右移一位，并将结果赋值给m，n左移一位，并将结果赋值给n。 一直循环以上两个步骤，直到m的值变为1为止。最后的结果的绝对值是res，再加上m×n的正负号，得出最终结果。

算法的时间复杂度：O(1)