LeetCode 371 Sum of Two Integers

Problem:

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Summary:

不使用+和-符号，计算两个整型数之和。

Analysis:

XOR相当于二进制数的无进位加法。进位位由两数&运算后左移一位确定。

Example:

用此方法计算5 + 3：

1、无进位结果：101 ^ 011 = 110　　进位：101 & 011 = 001　　左移：001 << 1 = 010

2、将进位与原结果相加：110 ^ 010 = 100　　进位：110 & 010 = 010　　左移：010 << 1 = 100

3、将进位与原结果相加：100 ^ 100 = 000　　进位：100 & 100 = 100　　左移：100 << 1 = 1000

4、将进位与原结果相加：000 ^ 1000 = 1000　　进位：000 & 1000 = 0000

故：和为1000₂ = 8

1 class Solution { 2 public: 3 int getSum(int a, int b) { 4 while (b) { 5 int carry = (a & b) << 1; 6 a = a ^ b; 7 b = carry; 8 } 9 10 return a; 11 } 12 };

Recursion:

1 class Solution { 2 public: 3 int getSum(int a, int b) { 4 5 return b ? getSum (a ^ b, (a & b) << 1) : a; 6 } 7 };

转载于:https://www.cnblogs.com/VickyWang/p/5988911.html