俄罗斯农夫法的乘法算法

2018-07-20 来源：open-open

算法简介：

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

代码如下：

    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 & 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 × n = "+res);  
                }else{  
                    System.out.println("m × 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。