#include <iostream>
#include <stdio.h>
using namespace std;
/*
问题:编写一个函数，将两个数字相加。不得使用+或其他算术运算符。
分析：既然不能使用+，应该就是位运算了。
可以将两个数字每次向右移动，每次将移动后的最低位进行与操作，若与操作结果为1，说明这两个数最后的都为1就进位，直到两个数都变成0
假设： 3 + 10
3对应: 00011
10对应: 01010
初始化一个结果result为0：每次将两个数最低位计算后的结果存放在result的第0位，第1位，..,
即可。
那么问题的关键变成：如何求两个数最低位，求某个数的第i位，可以采用将该数与(1<<i)进行与运算
设两个数分别为a,b
int pass = 0;
while( a && b)
{
int aBit = a & 1;
int bBit = b & 1;
//需要进位
if( ( 1 == aBit && 1 == bBit) || ( 1 == aBit))
{
pass = 1;
}
resultBit = ;
result |= resultBit;
}
书上解法：比如759 + 674,加法的：相加和进位拆分开：
1】759和674相加，不进位，得到323
2】759和674相加，只进位，得到1110
将1110 + 323 = 1433
上述只加不进位，就是异或操作
只进位不加，只要a和b的i-1位皆为1，总和的第i位为1，就是AND加上位移操作
输入：
3 5
3 -5
-3 -5
0 5
输出:
8
-2
-8
5
关键:
1
书上解法：比如759 + 674,加法的：相加和进位拆分开：
1】759和674相加，不进位，得到323
2】759和674相加，只进位，得到1110
将1110 + 323 = 1433
上述只加不进位，就是异或操作
只进位不加，只要a和b的i-1位皆为1，总和的第i位为1，就是AND加上位移操作
//递归得加法
int addRecursive(int a ,int b)
{
//注意递归的出口是: b为0，会导致sum为a , pass为0； 如果a为0，那么sum=0,pass为0
if(0 == a)
{
return b;
}
if(0 == b)
{
return a;
}
//累加，但不进位，通过异或实现
int sum = a ^ b;
//只进位，通过与操作，然后左移一位实现
int pass = (a & b) << 1;
return addRecursive(sum , pass);
}
2 注意，由于负数即使右移，填充的也是1，导致while(num1 && num2)陷入死循环，最好的办法就是采用(1<<i)次方取与 或者 次数超过32次就终止
int add(int num1 , int num2)
{
int pass = 0;
int result = 0;
pair<int, int> resultPair;
int resultBit;
int count = 0;
//注意，由于负数即使右移，填充的也是1，导致while(num1 && num2)陷入死循环，最好的办法就是采用(1<<i)次方取与 或者 次数超过32次就终止
//while(num1 || num2)
while(true)
{
//说明其中有一个是负数，直接退出循环
if(count >= 32)
{
break;
}
int bit1 = num1 & (1 );
int bit2 = num2 & (1 );
resultPair = getPassAndBit(bit1 , bit2 , pass );
resultBit = resultPair.first;
pass = resultPair.second;
result |= (resultBit << count);
num1 >>= 1;//右移一位
num2 >>= 1;
count++;
}
return result;
}
*/
//计算当前位和进位，pair第一个元素为当前位，第二个元素为进位
pair<int , int> getPassAndBit(int bit1 , int bit2 , int pass )
{
//如果全为0，进位为0，当前位为0
if( 0 == bit1 && 0 == bit2 && 0 == pass )
{
pair<int, int> result(0, 0);
return result;
}
//如果全为1，进位为1，当前位为1
else if( 1 == bit1 && 1 == bit2 && 1 == pass)
{
pair<int, int> result(1, 1);
return result;
}
//排除全1和全0的情况后：只剩两种可能：三者异或结果为0或1
else
{
//bit1，bit2,pass中有两个1,1个0，三者异或结果为0，此时当前位为0，进位为1
if( (bit1^bit2^pass) == 0)
{
pair<int, int> result(0, 1);
return result;
}
//bit1，bit2,pass中有两个0,1个1，三者异或结果为1，此时当前位为1，进位为0
else
{
pair<int, int> result(1, 0);
return result;
}
}
}
int add(int num1 , int num2)
{
int pass = 0;
int result = 0;
pair<int, int> resultPair;
int resultBit;
int count = 0;
//注意，由于负数即使右移，填充的也是1，导致while(num1 && num2)陷入死循环，最好的办法就是采用(1<<i)次方取与 或者 次数超过32次就终止
//while(num1 || num2)
while(true)
{
//说明其中有一个是负数，直接退出循环
if(count >= 32)
{
break;
}
int bit1 = num1 & (1 );
int bit2 = num2 & (1 );
resultPair = getPassAndBit(bit1 , bit2 , pass );
resultBit = resultPair.first;
pass = resultPair.second;
result |= (resultBit << count);
num1 >>= 1;//右移一位
num2 >>= 1;
count++;
}
return result;
}
//递归得加法
int addRecursive(int a ,int b)
{
//注意递归的出口是: b为0，会导致sum为a , pass为0； 如果a为0，那么sum=0,pass为0
if(0 == a)
{
return b;
}
if(0 == b)
{
return a;
}
//累加，但不进位，通过异或实现
int sum = a ^ b;
//只进位，通过与操作，然后左移一位实现
int pass = (a & b) << 1;
return addRecursive(sum , pass);
}
void process()
{
int num1;
int num2;
while(cin >> num1 >> num2)
{
//int result = add(num1 , num2);
int result = addRecursive(num1 , num2);
cout << result << endl;
}
}
int main(int argc , char* argv[])
{
process();
getchar();
return 0;
}
