Leetcode题解剑指 Offer 65. 不用加减乘除做加法

PROBLEM

难度简单

MY ANSWER

无。

BETTER SOLUTION

非进位和n=a^b，进位c=a&b<<1，s=a+b= n+c。循环求n和c，直到进位c=0。时间空间复杂度O(1)。需要使用无符号整数才可以移位。

class Solution {
public:
    int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (unsigned int) (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
};

SUMMARY

熟悉加法的位运算实现，需要使用无符号整数才可以移位。