LeetCode 371. 兩整數(shù)之和題意不使用運(yùn)算符 和 -計(jì)算兩個(gè)整數(shù) a、b 之和。思路位運(yùn)算模擬加法加法的兩個(gè)部分無進(jìn)位相加a ^ b異或相同為 0不同為 1進(jìn)位(a b) 1與運(yùn)算后左移一位不斷將「無進(jìn)位和」與「進(jìn)位」相加直到進(jìn)位為 0。Java 的 int 是 32 位補(bǔ)碼溢出會(huì)自動(dòng)截?cái)嘁虼素?fù)數(shù)同樣適用。Java 實(shí)現(xiàn)classSolution{publicintgetSum(inta,intb){while(b!0){intcarry(ab)1;// 計(jì)算進(jìn)位aa^b;// 無進(jìn)位相加bcarry;// 把進(jìn)位加到下一輪}returna;}}示例以 a 1, b 2 為例輪次 a b carry初始 1 2 -1 1 ^ 2 3 (1 2) 1 0 0b 0返回 3。以 a -1, b 1 為例循環(huán)若干輪后進(jìn)位也會(huì)變?yōu)?0最終返回 0。復(fù)雜度維度 復(fù)雜度時(shí)間 O(1)最多循環(huán) 32 次空間 O(1)遞歸寫法可選classSolution{publicintgetSum(inta,intb){if(b0)returna;returngetSum(a^b,(ab)1);}}注意點(diǎn)· 1 后可能溢出但 Java 的 int 會(huì)自動(dòng)丟棄高位正好符合補(bǔ)碼加法?！?循環(huán)條件用 b ! 0不要寫成 b 0否則負(fù)數(shù)進(jìn)位會(huì)出錯(cuò)。