371 .两整数之和

371 .两整数之和

• 地址：https://leetcode-cn.com/problems/sum-of-two-integers/

• 题目：不使用运算符 + 和 - ，计算两整数 a 、b 之和。

• 示例：

  示例1：
  	输入: a = 1, b = 2
  	输出: 3
  

• 思路：位运算

  • 观察位运算中的加法
    • 0+0=0
    • 0+1=1
    • 1+0=0
    • 1+1=0（进位1）
  • 可以发现，在位运算中的加法（不考虑进位1）就是异或运算的结果。
  • 但是仅仅有异或运算是不够的，我们还需要知道，何时发生了进位，这就需要用到&运算（注意到：&运算得到的进位1需要移1位来得到实际真实的进位）.

• 总结：

  • 1.a+b的问题可以拆分为，（a+b的无进位结果）+（a+b的进位结果）
  • 2.无进位结果通过异或算出
  • 3.有进位结果通过&算出
  • 4.循环此过程，直到进位为0.（此时，异或运算已经得到了最终结果，所以直接跳出循环。）

• 代码：

  • class Solution {
    public:
        int getSum(int a, int b) {
            while(b)
            {
                int c=(a&b)<<1;
                a=a^b;
                b=c;
            }
            return a;
        }
    };
    

• 代码出现的问题：

  忽略的重点，常见易错点

• 这里回顾一下C++的左移操作

  • shift-expression >> additive-expression
  • 左移运算符使shift 表达式中的位向左移动由加法表达式指定的位置数。 因移位运算而空出的位上将用零填充。 左移是逻辑移动（从末端移掉的位将被舍弃，包括符号位）。 有关位移位种类的详细信息，请参阅按位移位。

• 问题：当a和b都为负数时，此时a&b符号为1，移位时会发生溢出，导致错误。（因编译器的不同会发生不同的状况，或许不报错，但是实质上是错误行为。）

• 所以使用unsigned强制转换：

• 代码：
  #include<iostream>
  using namespace std;
  class Solution {
  public:
      int getSum(int a, int b) {
          while(b)
          {
              int c=(unsigned int)(a&b)<<1;
              a=a^b;
              b=c;
          }
          return a;
      }
  };