題目說了不能用算數運算符,那麼我們就只能從 邏輯運算子 和 移位運算子 入手了。
我們知道 ^ (異或)運算是對兩個數進行無進位求和,如果兩個數相加本來就不產生進位,那麼該和就是兩數之和。這就是解題的關鍵。一般來說,兩數相加是會產生進位的,而要得到正確的和,應該是在 “無進位之和” 的基礎上加上進位,那我們首先應該得到進位。我們知道,當兩個數對應位置都為1的情況下,才會有進位的產生,也就是對應位置A&B==1的條件下,就可以得到每一位的進位,但是進位是將這個1加到對應的更高一位,所以我們將得到的進位整體進行左移一位,再和之前得到的「無進位之和」 相加,就可以得到兩數之和。
我們發現這裡就可以無限套娃了,要得到「無進位之和」 和「產生的進位」 之和,那麼將這兩個數再分別看做新的兩個數,對其求和。也是重複之前的操作,直到兩數不能產生進位,就可以直接透過 ^ 運算得到結果。
假設我們求23 16 的值
#根據上述思路,我們很容易就可以寫出程式碼
public static int addAB(int A, int B) { // 当两数的产生的进位为 0,就退出循环,返回其无进位和,就是结果 while ((A & B) != 0) { int A_B = A ^ B;// 无进位求和 int AB = (A & B) << 1;// 得到进位 // 接下来就是求 得到的进位 + 无进位之和,重复前面的操作,直到不产生进位 A = A_B; B = AB; } // 最后返回新的无进位之和 return (A ^ B); }
那麼為了驗證它的正確性,我們這裡使用對數器,將函數與’ ’ 運算子比較。
public static void main(String[] args) { int count = 1_0000_0000;// 比较次数 100000000次 Random random = new Random();// 生成随机数字 boolean flag = true;// 相等则为 true for (int i = 0; i < count; i++) { int num1 = random.nextInt(Integer.MAX_VALUE/2);// 随机正数1 int num1_2 = random.nextInt(Integer.MAX_VALUE/2);// 随机正数2 // 随机正数1 + 随机正数2 if ((num1+num1_2) != addAB(num1,num1_2)){ // 有一次不相等的,则退出循环 flag = false; break; } int num2 = -random.nextInt(Integer.MAX_VALUE/2);// 随机负数1 int num2_2 = -random.nextInt(Integer.MAX_VALUE/2);// 随机负数2 // 随机负数1 + 随机负数2 if ((num2+num2_2) != addAB(num2,num2_2)){ // 有一次不相等的,则退出循环 flag = false; break; } int num3 = random.nextInt(Integer.MAX_VALUE);// 随机正数 int num4 = -random.nextInt(Integer.MAX_VALUE);// 随机负数 // 随机正数 + 随机负数 if ((num3+num4) != addAB(num3,num4)){ // 有一次不相等的,则退出循环 flag = false; break; } } System.out.println(flag); }
運行結果:
最後輸出結果為true ,說明我們計算隨機產生的正數正數、負數負數、正數負數分別100000000次,沒有一次出錯,表示函數可靠。
以上是Java不用算數運算子怎麼實現求和的詳細內容。更多資訊請關注PHP中文網其他相關文章!