鲜花：基于位运算的 A+B Problem

前置知识：二进制、按位与&、按位异或^、左移<<。

按位异或的本质是二进制下不进位的加法，也就是对于每一位将值相加再直接对 \(2\) 取模。由于^和+有相同之处，考虑什么时候两者不同，很明显是二进制下需要进位的时候，那么什么时候需要进位呢？枚举可知，只有两个数该位都为 \(1\) 是该位需要进位。该为都为 \(1\)，这不就是按位与吗？然后考虑二进制下的进位，直接使用左移就可以解决。现在就可以递归求解了；边界就是x&y==0，此时直接返回 x^y。我们的递归次数是由最长的连续的 \(1\) 的长度决定的，所以最劣时间复杂度为 \(O(\log w)\)。

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
il int jia(int x,int y)
{
	if(!(x&y))
	{
		return x^y;
	}
	return jia(x^y,(x&y)<<1);
}
int main()
{
	scanf("%d%d",&a,&b);
	printf("%d",jia(a,b));
	return 0;
}

递归常数大，那可不可以实现非递归呢？答案当然是肯定的，不然我就不会写这句话了。非递归的实现就是相同的思路。可以选择单开一个变量存原来的 \(a\)，也可以利用a^b^b==a的性质原地算。

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
int main()
{
	scanf("%d%d",&a,&b);
	while(a&b)
	{
		a=a^b;
		b=((a^b)&b)<<1;
	}
	printf("%d",a^b);
	return 0;
}

递归版31ms，非递归30ms，跑的也不算太慢。其重点是可以扩展到使用bitset实现的高精度。但是还没完工。