为 A xor X = B + X 找到解决方案的算法
Algorithm to find a solution for A xor X = B + X
Given integer A and B, find integer X so that:
- A,B < 2*1e18
- A xor X = B + X
我非常怀疑能否用数学来求解这个方程。这是我 3 年前遇到的一个编码问题,即使现在我自己也无法解决。
到目前为止我的代码:
(这是蛮力解决方案)
#include <iostream>
using namespace std;
int main()
{
unsigned long long a, b;
cin >> a >> b;
for (unsigned long long x = 1; x < max(a, b); x++) {
unsigned long long c = a ^ x;
unsigned long long d = b + x;
if (c == d) {
cout << x << endl;
break;
return 0;
}
}
cout << -1; //if no such integer exists
return 0;
}
不是很难,你只需要从小处着想:假设我们用二进制写A
、B
和X
,Aᵢ
是对应的值到最右边的 2ⁱ 位。
我们知道:Aₒ ⊕ Xₒ = Bₒ + Xₒ
.
让我们用一个例子来了解如何计算:A = 15 和 B = 6。转换为二进制:
A = 1 1 1 1 B = 0 1 1 0
X = a b c d X = a b c d
现在我们有了一些可能性。下面分析一下A和B最右边的位:
1 ⊕ d = 0 + d
我们知道d
只能是0或1,所以:
for d = 0
1 ⊕ d = 0 + d => 1 ⊕ 0 = 0 + 0 => 1 = 0 (not possible)
for d = 1
1 ⊕ d = 0 + d => 1 ⊕ 1 = 0 + 1 => 0 = 1 (not possible)
值得注意的是,XOR 的行为就像二进制和(区别在于 XOR 不会为下一个位和创建结转):
XOR SUM
0 ⊕ 0 = 0 | 0 + 0 = 0
0 ⊕ 1 = 1 | 0 + 1 = 1
1 ⊕ 0 = 1 | 1 + 0 = 1
1 ⊕ 1 = 0 | 1 + 1 = 0
所以并不总能找到满足 A ⊕ X = B + X
的 X,因为不存在满足 1 + d = 0 + d
.
的值 d
总之,如果X存在,就这样找吧,从右到左,一点一点找。
完整示例
A = 15, B = 7:
A = 1 1 1 1 B = 0 1 1 1
X = a b c d X = a b c d
1 ⊕ d = 1 + d
这里,d = 0和d = 1都适用,那又如何呢?我们需要检查下一位。假设 d = 1:
A = 1 1 1 1 B = 0 1 1 1
X = a b c d X = a b c d
1 ⊕ d = 1 + d => 1 ⊕ 1 = 1 + 1 => 0 = 0 (possible)
BUT 1 + 1 = 0 generates a carryover for the next bit sum:
Instead of 1 ⊕ c = 1 + c, we have 1 ⊕ c = 1 + c (+1) =
1 ⊕ c = c (not possible)
所以在这种情况下,d 必须为 0。
carryover 0
A = 1 1 1 1 B = 0 1 1 1
X = a b 0 0 X = a b 0 0
-----------------------------------
0 0
we know that c must be 0:
carryover 0 0
A = 1 1 1 1 B = 0 1 1 1
X = a b 0 0 X = a b 0 0
-----------------------------------
1 1 1 1
但是b呢?我们需要像往常一样检查下一位:
if b = 0, there won't be a carryover, so we'll have:
1 ⊕ a = 0 + a (and this is not possible)
so we try b = 1:
1 ⊕ b = 1 + b => 1 ⊕ 1 = 1 + 1 => 0 = 0 (with carryover)
现在,a
:
carryover 1 0 0
A = 1 1 1 1 B = 0 1 1 1
X = a 1 0 0 X = a 1 0 0
-----------------------------------
0 0 0 0 0 0
1 ⊕ a = 0 + a (+1) => 1 ⊕ a = 1 + a
这里a
可以是0和1,但必须是0,以免在和B + X
.
中出现结转
然后,X = 0 1 0 0
,因此 X = 4。
代码
#include <iostream>
using namespace std;
inline int bit(int a, int n) {
if(n > 31) return 0;
return (a & ( 1 << n )) >> n;
}
int main(){
int A = 19;
int B = 7;
int X = 0;
int carryover = 0;
int aCurrent, aNext, bCurrent, bNext;
for(int i = 0; i < 32; i++){
aCurrent = bit(A, i); bCurrent = bit(B, i);
aNext = bit(A, i + 1); bNext = bit(B, i + 1);
if(aCurrent == 0 && bCurrent == 0){
if(carryover) {X = -1; break;}
if(aNext != bNext){
X += 1 << i;
}
carryover = 0;
}
else if(aCurrent == 0 && bCurrent == 1){
if(!carryover) {X = -1; break;}
if(aNext == bNext){
X += 1 << i;
}
carryover = 1;
}
else if(aCurrent == 1 && bCurrent == 0){
if(!carryover) {X = -1; break;}
if(aNext != bNext){
X += 1 << i;
carryover = 1;
}
else {
carryover = 0;
}
}
else if(aCurrent == 1 && bCurrent == 1){
if(carryover) {X = -1; break;}
if(aNext != bNext){
X += 1 << i;
carryover = 1;
}
else {
carryover = 0;
}
}
}
if(X != -1) cout<<"X = "<<X<<endl;
else cout<<"X doesnt exist"<<endl;
return 0;
}
你可以测试一下here。
注意A + X == (A xor X) + ((A and X)<<1)
。所以:
A xor X = A + X - ((A and X)<<1) = B + X
A - B = (A and X)<<1
我们有:
(A - B) and not (A<<1) = 0 (All bits in (A - B) are also set in (A<<1))
(A - B)>>1 = A and X
如果满足条件,对于任何没有在 A 中设置位的整数 Y,(((A - B)>>1) 或 Y) 是一个解。如果你只想要一个解决方案,你可以使用 ((A - B)>>1),其中 Y = 0。否则没有解决方案。
int solve(int a, int b){
int x = (a - b) >> 1;
if ((a ^ x) == b + x)
return x;
else
return ERROR;
}
Given integer A and B, find integer X so that:
- A,B < 2*1e18
- A xor X = B + X
我非常怀疑能否用数学来求解这个方程。这是我 3 年前遇到的一个编码问题,即使现在我自己也无法解决。
到目前为止我的代码: (这是蛮力解决方案)
#include <iostream>
using namespace std;
int main()
{
unsigned long long a, b;
cin >> a >> b;
for (unsigned long long x = 1; x < max(a, b); x++) {
unsigned long long c = a ^ x;
unsigned long long d = b + x;
if (c == d) {
cout << x << endl;
break;
return 0;
}
}
cout << -1; //if no such integer exists
return 0;
}
不是很难,你只需要从小处着想:假设我们用二进制写A
、B
和X
,Aᵢ
是对应的值到最右边的 2ⁱ 位。
我们知道:Aₒ ⊕ Xₒ = Bₒ + Xₒ
.
让我们用一个例子来了解如何计算:A = 15 和 B = 6。转换为二进制:
A = 1 1 1 1 B = 0 1 1 0
X = a b c d X = a b c d
现在我们有了一些可能性。下面分析一下A和B最右边的位:
1 ⊕ d = 0 + d
我们知道d
只能是0或1,所以:
for d = 0
1 ⊕ d = 0 + d => 1 ⊕ 0 = 0 + 0 => 1 = 0 (not possible)
for d = 1
1 ⊕ d = 0 + d => 1 ⊕ 1 = 0 + 1 => 0 = 1 (not possible)
值得注意的是,XOR 的行为就像二进制和(区别在于 XOR 不会为下一个位和创建结转):
XOR SUM
0 ⊕ 0 = 0 | 0 + 0 = 0
0 ⊕ 1 = 1 | 0 + 1 = 1
1 ⊕ 0 = 1 | 1 + 0 = 1
1 ⊕ 1 = 0 | 1 + 1 = 0
所以并不总能找到满足 A ⊕ X = B + X
的 X,因为不存在满足 1 + d = 0 + d
.
d
总之,如果X存在,就这样找吧,从右到左,一点一点找。
完整示例
A = 15, B = 7:
A = 1 1 1 1 B = 0 1 1 1
X = a b c d X = a b c d
1 ⊕ d = 1 + d
这里,d = 0和d = 1都适用,那又如何呢?我们需要检查下一位。假设 d = 1:
A = 1 1 1 1 B = 0 1 1 1
X = a b c d X = a b c d
1 ⊕ d = 1 + d => 1 ⊕ 1 = 1 + 1 => 0 = 0 (possible)
BUT 1 + 1 = 0 generates a carryover for the next bit sum:
Instead of 1 ⊕ c = 1 + c, we have 1 ⊕ c = 1 + c (+1) =
1 ⊕ c = c (not possible)
所以在这种情况下,d 必须为 0。
carryover 0
A = 1 1 1 1 B = 0 1 1 1
X = a b 0 0 X = a b 0 0
-----------------------------------
0 0
we know that c must be 0:
carryover 0 0
A = 1 1 1 1 B = 0 1 1 1
X = a b 0 0 X = a b 0 0
-----------------------------------
1 1 1 1
但是b呢?我们需要像往常一样检查下一位:
if b = 0, there won't be a carryover, so we'll have:
1 ⊕ a = 0 + a (and this is not possible)
so we try b = 1:
1 ⊕ b = 1 + b => 1 ⊕ 1 = 1 + 1 => 0 = 0 (with carryover)
现在,a
:
carryover 1 0 0
A = 1 1 1 1 B = 0 1 1 1
X = a 1 0 0 X = a 1 0 0
-----------------------------------
0 0 0 0 0 0
1 ⊕ a = 0 + a (+1) => 1 ⊕ a = 1 + a
这里a
可以是0和1,但必须是0,以免在和B + X
.
然后,X = 0 1 0 0
,因此 X = 4。
代码
#include <iostream>
using namespace std;
inline int bit(int a, int n) {
if(n > 31) return 0;
return (a & ( 1 << n )) >> n;
}
int main(){
int A = 19;
int B = 7;
int X = 0;
int carryover = 0;
int aCurrent, aNext, bCurrent, bNext;
for(int i = 0; i < 32; i++){
aCurrent = bit(A, i); bCurrent = bit(B, i);
aNext = bit(A, i + 1); bNext = bit(B, i + 1);
if(aCurrent == 0 && bCurrent == 0){
if(carryover) {X = -1; break;}
if(aNext != bNext){
X += 1 << i;
}
carryover = 0;
}
else if(aCurrent == 0 && bCurrent == 1){
if(!carryover) {X = -1; break;}
if(aNext == bNext){
X += 1 << i;
}
carryover = 1;
}
else if(aCurrent == 1 && bCurrent == 0){
if(!carryover) {X = -1; break;}
if(aNext != bNext){
X += 1 << i;
carryover = 1;
}
else {
carryover = 0;
}
}
else if(aCurrent == 1 && bCurrent == 1){
if(carryover) {X = -1; break;}
if(aNext != bNext){
X += 1 << i;
carryover = 1;
}
else {
carryover = 0;
}
}
}
if(X != -1) cout<<"X = "<<X<<endl;
else cout<<"X doesnt exist"<<endl;
return 0;
}
你可以测试一下here。
注意A + X == (A xor X) + ((A and X)<<1)
。所以:
A xor X = A + X - ((A and X)<<1) = B + X
A - B = (A and X)<<1
我们有:
(A - B) and not (A<<1) = 0 (All bits in (A - B) are also set in (A<<1))
(A - B)>>1 = A and X
如果满足条件,对于任何没有在 A 中设置位的整数 Y,(((A - B)>>1) 或 Y) 是一个解。如果你只想要一个解决方案,你可以使用 ((A - B)>>1),其中 Y = 0。否则没有解决方案。
int solve(int a, int b){
int x = (a - b) >> 1;
if ((a ^ x) == b + x)
return x;
else
return ERROR;
}