leetcode-top面试题两整数之和

布满荆棘的人生 2021-11-26 13:36 194阅读 0赞

**题目**不使用运算符 + 和 - ，计算两整数 a 、b 之和。  
示例 1:  
输入: a = 1, b = 2  
输出: 3  
示例 2：  
输入: a = -2, b = 3  
输出: 1  
*来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/sum-of-two-integers][https_leetcode-cn.com_problems_sum-of-two-integers]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*  
**思路**  
第一种情况：（不存在进位）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
第二种情况：（存在进位）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
第三种情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]

**实现代码**

public static int getSum(int a, int b) {
            int and = a & b; //与运算结果，1的位代表两个数值都为1，存在进位
            int eor = a ^ b; //异或运算结果，1的位代表两个数值对应位有一个为1
    
            //若and不为0，意味着存在进位情况，将进位左移
            if(and != 0) {
                and = and << 1;
            }
    
            //当进位为1的位数和有一位为1的位数相遇，与运算为1，证明再次存在进位运算
            while((and & eor) != 0){
                //计算新的进位
                int newAnd = and & eor;
                //再次比较出有一位为1的位数
                eor = and ^ eor;
                //把进位左移
                and = newAnd <<1;
            }
            //进位和有一位为1的位已经没有重叠，通过异或运算得出最终位数状态
            //为什么用抑或而不是或运算，因为之前应该进位的位没有改为0，
            //而该进的位已经写到最终的位置，因此原有两位都是1的值要通过抑或变为0
            return and ^ eor;
        }

[https_leetcode-cn.com_problems_sum-of-two-integers]: https://leetcode-cn.com/problems/sum-of-two-integers
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20211126/b56fcfd7ea394deaa8cd11e3c0e6db0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20211126/279f367dafc44e4abaa6989b9396f619.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20211126/e4de66bfaeca46abb3a2a736429a1243.png