俄羅斯農夫法的乘法算法

算法簡介：

俄羅斯農夫法的乘法算法，整數與整數相乘的方法如下：

代碼如下：

    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。

       (2)m為偶數

               m右移一位，并將結果賦值給m，n左移一位，并將結果賦值給n。

    一直循環以上兩個步驟，直到m的值變為1為止。

    最后的結果的絕對值是res，再加上m× n 的正負號，得出最終結果。

算法的時間復雜度：O(1)