题解：P1001 A+B Problem

首先我们需要知道三个性质。

$a+b=a\operatorname{xor} b+2\times (a\operatorname{and} b)$ 。
$a+0=a$ 。
$0+a=a$ 。

性质

1

的证明：
对于

a,b

在二进制下的每一位都有四种情况。

$a$ 在二进制下的第 $i$ 位为 $1$ 且 $b$ 在二进制下的第 $i$ 位为 $1$ ，则 $1\operatorname{xor} 1+2\times (1\operatorname{and} 1)=2$ 。
$a$ 在二进制下的第 $i$ 位为 $1$ 且 $b$ 在二进制下的第 $i$ 位为 $0$ ，则 $1\operatorname{xor} 0+2\times (1\operatorname{and} 0)=1$ 。
$a$ 在二进制下的第 $i$ 位为 $0$ 且 $b$ 在二进制下的第 $i$ 位为 $1$ ，则 $0\operatorname{xor} 1+2\times (0\operatorname{and} 1)=1$ 。
$a$ 在二进制下的第 $i$ 位为 $0$ 且 $b$ 在二进制下的第 $i$ 位为 $0$ ，则 $0\operatorname{xor} 0+2\times (0\operatorname{and} 0)=0$ 。

发现以上四种情况都成立。

很显然，性质

2,3

成立。
有了这三条性质，我们就可以对

a,b

一直进行变换，直到

a=0

或

b=0

为止。
代码实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int add(int a,int b){
	if(a==0) return b;
	if(b==0) return a;
	return add(a^b,2*(a&b));
}
int main(){
    int a,b;
	cin>>a>>b;
	cout<<add(a,b);
	return 0;
}

题解：P1001 A+B Problem

文章操作

题解：P1001 A+B Problem

相关推荐

评论

题解：P1001 A+B Problem