快捷導(dǎo)航

Java不用算數(shù)運算符來實現(xiàn)求和方法

更新時間：2022年04月02日 15:06:28 作者：Scintillator. /

我們都知道，Java的運算符除了具有優(yōu)先級之外，還有一個結(jié)合性的特點。當(dāng)一個表達式中出現(xiàn)多種運算符時，執(zhí)行的先后順序不僅要遵守運算符優(yōu)先級別的規(guī)定，還要受運算符結(jié)合性的約束，以便確定是自左向右進行運算還是自右向左進行運算，但是如果不用運算符怎么求和呢

今天遇到了這樣一個題

在這里插入圖片描述

題目說了不能用算數(shù)運算符，那么我們就只能從邏輯運算符和移位運算符入手了。

我們知道 ^ (異或)操作是對兩個數(shù)進行無進位求和，如果兩個數(shù)相加本來就不產(chǎn)生進位，那么該和就是兩數(shù)之和。這就是解題的關(guān)鍵所在。一般來說，兩數(shù)相加是會產(chǎn)生進位的，而要得到正確的和，應(yīng)該是在 “無進位之和” 的基礎(chǔ)上加上進位，那我們首先應(yīng)該得到進位。我們知道，當(dāng)兩個數(shù)對應(yīng)位置都為1的情況下，才會有進位的產(chǎn)生，即對應(yīng)位置 A&B==1的條件下，就可以得到每一位的進位，但是進位是將這個1加到對應(yīng)的更高一位，所以我們將得到的進位整體進行左移一位，再和之前得到的 “無進位之和” 相加，就可以得到兩數(shù)之和。

我們發(fā)現(xiàn)這里就可以無限套娃了，要得到 “無進位之和” 和 “產(chǎn)生的進位” 之和，那么將這兩個數(shù)再分別看做新的兩個數(shù)，對其求和。也是重復(fù)之前的操作，直到兩數(shù)不能產(chǎn)生進位，就可以直接通過 ^ 運算得到結(jié)果。

假設(shè)我們求 23 + 16 的值

在這里插入圖片描述

根據(jù)上述思路，我們很容易就可以寫出代碼

public static int addAB(int A, int B) {
		// 當(dāng)兩數(shù)的產(chǎn)生的進位為 0,就退出循環(huán)，返回其無進位和，就是結(jié)果
        while ((A & B) != 0) {
            int A_B = A ^ B;// 無進位求和
            int AB = (A & B) << 1;// 得到進位
            // 接下來就是求 得到的進位 + 無進位之和，重復(fù)前面的操作，直到不產(chǎn)生進位
            A = A_B;
            B = AB;
        }
        // 最后返回新的無進位之和
        return (A ^ B);
    }

那么為了驗證它的正確性，我們這里使用對數(shù)器，將該函數(shù)與 ’ + ’ 運算符比較。

public static void main(String[] args) {
    int count = 1_0000_0000;// 比較次數(shù) 100000000次
    Random random = new Random();// 生成隨機數(shù)字
    boolean flag = true;// 相等則為 true

    for (int i = 0; i < count; i++) {
        int num1 = random.nextInt(Integer.MAX_VALUE/2);// 隨機正數(shù)1
        int num1_2 = random.nextInt(Integer.MAX_VALUE/2);// 隨機正數(shù)2
        // 隨機正數(shù)1 + 隨機正數(shù)2
        if ((num1+num1_2) != addAB(num1,num1_2)){
            // 有一次不相等的，則退出循環(huán)
            flag = false;
            break;
        }

        int num2 = -random.nextInt(Integer.MAX_VALUE/2);// 隨機負(fù)數(shù)1
        int num2_2 = -random.nextInt(Integer.MAX_VALUE/2);// 隨機負(fù)數(shù)2
        // 隨機負(fù)數(shù)1  + 隨機負(fù)數(shù)2
        if ((num2+num2_2) != addAB(num2,num2_2)){
            // 有一次不相等的，則退出循環(huán)
            flag = false;
            break;
        }

        int num3 = random.nextInt(Integer.MAX_VALUE);// 隨機正數(shù)
        int num4 = -random.nextInt(Integer.MAX_VALUE);// 隨機負(fù)數(shù)
        // 隨機正數(shù)  + 隨機負(fù)數(shù)
        if ((num3+num4) != addAB(num3,num4)){
            // 有一次不相等的，則退出循環(huán)
            flag = false;
            break;
        }
    }
    System.out.println(flag);
}

運行結(jié)果：

在這里插入圖片描述