前言

在上一篇中，我們介紹了使用位運(yùn)算實(shí)現(xiàn)加法和減法運(yùn)算，接下來(lái)本文主要介紹如何用位運(yùn)算實(shí)現(xiàn)乘法運(yùn)算，在實(shí)現(xiàn)乘法時(shí)要用位運(yùn)算實(shí)現(xiàn)，并且不能出現(xiàn)加減乘除任何符號(hào)。

之前介紹過(guò)一篇如何用位運(yùn)算實(shí)現(xiàn)加法和減法： 如何用位運(yùn)算實(shí)現(xiàn)加減運(yùn)算？

正文

在用位運(yùn)算實(shí)現(xiàn)之前，我們先來(lái)回憶一下小學(xué)時(shí)，學(xué)乘法時(shí)用的十字相乘法。

十進(jìn)制相乘

例如，26 * 15，在進(jìn)行乘法操作時(shí)，我們一般這樣算，先用5乘以6得到30，把0寫(xiě)下把3記在一邊，再用5乘以2得到10再加上之前的3寫(xiě)在下面，得到130；計(jì)算完5再計(jì)算1分別乘以6和2把得到的結(jié)果26記在下面，然后把130和26相加(有錯(cuò)位)得到390。

二進(jìn)制相乘

看完了十進(jìn)制的相乘，再來(lái)看下二進(jìn)制的相乘，基本原理是一樣的，也是以十字相乘法為例，計(jì)算 5 * 7。

5的二進(jìn)制為101，7的二進(jìn)制為111，來(lái)看下二進(jìn)制的十字相乘法。

可以看到二進(jìn)制為101和二進(jìn)制111用傳統(tǒng)的方式來(lái)計(jì)算，得到的結(jié)果為100011，而二進(jìn)制100011對(duì)應(yīng)的十進(jìn)制為35。
所以說(shuō)，在計(jì)算的過(guò)程中，十進(jìn)制和二進(jìn)制的計(jì)算方式是一樣的，當(dāng)然這里就不進(jìn)行舉例和證明了。

思路分析

既然計(jì)算過(guò)程有了，那么怎么樣用代碼來(lái)實(shí)現(xiàn)呢？

我們?cè)賮?lái)看下上圖中二進(jìn)制的計(jì)算過(guò)程：

• 先用二進(jìn)制111的最后一位1 乘上 101 得到 101。
• 再用二進(jìn)制111的倒數(shù)第2位1 乘上 101 得到 101。
• 再用二進(jìn)制111的倒數(shù)第3位1 乘上 101 得到 101。
• 得到的三個(gè)101進(jìn)行二進(jìn)制相加，得到 100011。

注意，第2步和第3步得到的結(jié)果101都往前挪了一位，相當(dāng)于1010和10100，也就是最后相加的計(jì)算為：10100 + 1010 + 101 = 100011。

再來(lái)看得到最終相加的計(jì)算10100 + 1010 + 101 = 100011，也就是只要我們找到如何把數(shù)據(jù)轉(zhuǎn)換為幾位數(shù)的相加就可以了，因?yàn)橹耙呀?jīng)實(shí)現(xiàn)了如何用位運(yùn)算實(shí)現(xiàn)加法操作。

這三個(gè)數(shù)101、1010、10100的數(shù)量剛好與二進(jìn)制111的個(gè)數(shù)相同，也就是二進(jìn)制(上圖下面那個(gè)乘數(shù)111)有幾位就會(huì)產(chǎn)生幾個(gè)數(shù)相加，如果是與11111相乘就會(huì)產(chǎn)生5個(gè)數(shù)相加。

再來(lái)看數(shù)據(jù)之前的關(guān)系：

• 第一次相乘結(jié)果：101 = 101 + 0
• 第二次相乘結(jié)果：1111 = 101 < 1 + 101 = 1010 + 101
• 第三次相乘結(jié)果：100011 = 101 < 2 + 1111 = 10100 + 1010 + 101

從這里我們可以看到，每計(jì)算一次，101只需要向左移一次再加上上一次的計(jì)算結(jié)果就可以了。

那么，怎么知道要左移多少次呢？從這里例子中看，111每次計(jì)算后，向右移動(dòng)一次，101也跟著向左移動(dòng)一次，直到111只剩最后一位，則停止計(jì)算就好了。

代碼實(shí)現(xiàn)

根據(jù)上面的思路，來(lái)實(shí)現(xiàn)一下代碼：

// 用位運(yùn)算實(shí)現(xiàn)加法
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;
}

// 用位運(yùn)算實(shí)現(xiàn)減法
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;
}

運(yùn)行一下代碼，看下結(jié)果：

可以看到計(jì)算是正確的，而且還支持負(fù)數(shù)。

總結(jié)

本文介紹了如何用純位運(yùn)算實(shí)現(xiàn)乘法的運(yùn)算，并介紹了實(shí)現(xiàn)思路以及分析，需要注意的是，位運(yùn)算右移的時(shí)候需要使用無(wú)符號(hào)右移，否則的話，會(huì)出現(xiàn)死循環(huán)的。

另外，本文只是介紹利用位運(yùn)算來(lái)實(shí)現(xiàn)乘法的實(shí)現(xiàn)過(guò)程、知識(shí)點(diǎn)的介紹，雖然是使用的位運(yùn)算但是效率是不能和Java原生的加法運(yùn)算相比的，并沒(méi)有原生的效率高。

到此這篇關(guān)于Java利用位運(yùn)算實(shí)現(xiàn)乘法運(yùn)算詳解的文章就介紹到這了,更多相關(guān)Java位運(yùn)算實(shí)現(xiàn)乘法運(yùn)算內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論