[Lc]面试题65不用加减乘除做加法

题目

题解

这道题要求不能使用四则运算，一般这种题就要用位运算。对加法进行分析一下

可以看出，非进位和符合异或逻辑操作，进位位符合逻辑与操作那么只要连续的算进位，直到进位位为0，即可得出最终结果。
对于负数来说，计算机中的数字都是用补码表示，对加减法的处理是相同的，因此这个方法可以对于正数和负数都可以处理

• 时间复杂度$O(1)$，最多32位，是有限的循环
• 空间复杂度$O(1)$

class Solution {//一个方法。逻辑运算
public:
    int add(int a, int b) {
        while(b != 0){//当b不为0的时候，持续运算
            //进位位，注意要左移一位，且遇到左移或者逻辑元素要用括号（优先级的问题）
            //注意C++中负数不允许左移，因此要先转化为无符号整型
            int c = (unsigned int)(a & b) << 1;
            a = a ^ b;//非进位和
            b = c;
        }
        return a;
    }
};