Java怎麼用位元運算實作乘法運算

十進位相乘

例如，26 * 15，在進行乘法運算時，我們一般這樣算，先用5乘以6 得到30，把0寫下把3記在一邊，再用5乘以2得到10再加上之前的3寫在下面，得到130；計算完5再計算1 分別乘以6和2把得到的結果26記在下面，然後把130和26 相加(有錯位)得到390。

二進位相乘

看完了十進制的相乘，再來看下二進位的相乘，基本原理是一樣的，也是以十字相乘法為例，計算5 * 7。

5的二進位為101，7的二進位為111，來看下二進位的十字相乘法。

可以看到二進位為101和二進位111用傳統的方式來計算，得到的結果為 100011，而二進位100011對應的十進位為35。
所以說，在計算的過程中，十進制和二進制的計算方式是一樣的，當然這裡就不進行舉例和證明了。

思路分析

既然計算過程有了，那麼怎麼樣用程式碼來實作呢？

我們再來看下上圖中二進位的計算過程：

• #先用二進位111的最後一位1 乘上101 得到101。

• 再用二進位111的倒數第2位元1 乘以101 得到101。

• 再用二進位111的倒數第3位元1 乘以101 得到101。

• 得到的三個101進行二進位相加，得到 100011。

注意，第2步和第3步驟得到的結果101都往前挪了一位，相當於1010和10100，也就是最後相加的計算為：10100 1010 101 = 100011。

再來看得到最終相加的計算10100 1010 101 = 100011，也就是只要我們找到如何把資料轉換為幾位數的相加就可以了，因為之前已經實現瞭如何用位元運算實現加法操作。

這三個數字101、1010、10100的數量剛好與二進位111的數量相同，也就是二進位(上圖下面那個乘數111)有幾位就會產生幾個數相加，如果是與11111相乘就會產生5個數相加。

再來看資料之前的關係：

• 第一次相乘結果：101 = 101 0

• 第二次相乘結果：1111 = 101

• ##第三次相乘結果：

  100011 = 101

101只需要向左移一次再加上上一次的計算結果就可以了。

111每次計算後，向右移動一次，101也跟著向左移動一次，直到111只剩下最後一位，則停止計算就好了。

// 用位运算实现加法
public static int add(int a, int b) {
    int sum = 0;
    while (b != 0) {
        sum = a ^ b;
        b = (a & b) << 1;
        a = sum;
    }
    return sum;
}

// 用位运算实现减法
public static int multi(int a, int b) {
    int res = 0;
    while (b != 0) {
        if ((b & 1) != 0) {
            res = add(res, a);
        }
        a <<= 1;
        b >>>= 1;
    }
    return res;
}

以上是Java怎麼用位元運算實作乘法運算的詳細內容。更多資訊請關注PHP中文網其他相關文章！