Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to find a solution for A xor X = B + X

Tags:

c++

xor

Given integer A and B, find integer X so that:

  • A,B < 2*1e18
  • A xor X = B + X

I highly doubt it is possible to solve this equation using maths. This is a coding problem I came across 3 years ago and even now I can't solve this myself.

My code so far: (this is the brute force solution)

#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; } 
like image 405
AAaAa Avatar asked Mar 31 '20 14:03

AAaAa


People also ask

How do you find the numbers if their XOR is given?

A Simple solution is to traverse each element and check if there's another number whose XOR with it is equal to x. This solution takes O(n2) time. An efficient solution to this problem takes O(n) time. The idea is based on the fact that arr[i] ^ arr[j] is equal to x if and only if arr[i] ^ x is equal to arr[j].

How do you find 2 numbers from XOR?

A simple solution is to generate all possible pairs with given XOR. To generate all pairs, we can follow below rules. If X[i] is 1, then both a[i] and b[i] should be different, we have two cases. If X[i] is 0, then both a[i] and b[i] should be same.

What is a XOR B XOR C?

So the following boolean expression: a'b'c + a'bc' + ab'c' + abc. Can be simplified to: a XOR b XOR c. By the definition of XOR: XOR = 1 iff an odd number of ones from each term.

How do you do XOR sum?

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element. For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4 , and the XOR sum of [3] is equal to 3 .


Video Answer


1 Answers

Note that A + X == (A xor X) + ((A and X)<<1). So:

A xor X = A + X - ((A and X)<<1) = B + X A - B = (A and X)<<1 

And we have:

(A - B) and not (A<<1) = 0    (All bits in (A - B) are also set in (A<<1)) (A - B)>>1 = A and X 

If the condition is met, for any integer Y that doesn't have bits that are set in A, (((A - B)>>1) or Y) is a solution. If you want just one solution, you could use ((A - B)>>1), where Y = 0. Otherwise there is no solution.

int solve(int a, int b){     int x = (a - b) >> 1;     if ((a ^ x) == b + x)         return x;     else         return ERROR; } 
like image 165
user23013 Avatar answered Sep 22 '22 21:09

user23013