Geek Answers Handbook

Given XOR and SUM of two numbers. How to find numbers?

Given the XOR and SUM of two numbers. How to find numbers? For example, x = a + b, y = a ^ b; if x, y are given, how to get a, b? And if I can’t, explain the reason.

+1
source share
4 answers

Unable to execute. One example of a counter is 0/100 and 4/96. Both of these amounts to 100 and xor to 100.

Therefore, given the sum of 100 and the result of xor out of 100, you cannot know which of the possibilities generated these two numbers.

For what it's worth, this program only checks capabilities with the number 0..255 :

 #include <stdio.h> static void output (unsigned int a, unsigned int b) { printf ("%u:%u=%u %u\n", a+b, a^b, a, b); } int main (void) { unsigned int limit = 256; unsigned int a, b; output (0, 0); for (b = 1; b != limit; b++) output (0, b); for (a = 1; a != limit; a++) for (b = 1; b != limit; b++) output (a, b); return 0; }

Then you can take this conclusion and massage it to give you all the repetitive possibilities:

 testprog | sed 's/=.*$//' | sort | uniq -c | grep -v ' 1 '

which gives:

  7 100:100 2 100:16 4 100:18 2 100:2 4 100:20 4 100:24 8 100:26 2 100:4 2 100:64 4 100:66 4 100:68 4 100:80 8 100:82 8 100:84 8 100:88 16 100:90

etc.

Even in this reduced set, there are quite a few combinations that generate the same amount / xor, the worst of which is the large number of possibilities that generate the amount / xor 255/255, some of which are:

 255:255=0 255 255:255=1 254 255:255=2 253 255:255=3 252 255:255=4 251 255:255=5 250 255:255=6 249 255:255=7 248 255:255=8 247 255:255=9 246 255:255=10 245 255:255=11 244 255:255=12 243 255:255=13 242 255:255=14 241 255:255=15 240 255:255=16 239 255:255=17 238 255:255=18 237
+8
source

It has already been shown that this is impossible, but here are two more reasons.

For a (rather large) subset of a and b (a & b) == 0 you have a + b == (a ^ b) (because there can be no hyphens) (reverse implication fails). In this case, you can, for each bit that is 1 in total, choose which of a or b this bit has contributed. Obviously, this subset does not cover the entire input, but at least proves that it cannot be done at all.

In addition, there are many pairs (x, y) such that there is no solution for a + b == x && (a ^ b) == y , for example (there are more than just them) all pairs (x, y) , where ((x ^ y) & 1) == 1 (i.e., one is odd and the other is even), since the least significant bit xor and the sum are equal (the least significant bit has no carry). Using a simple counting argument, this should mean that at least some pairs (x, y) must have several solutions: it is obvious that all pairs (a, b) have a pair (x, y) associated with them, therefore, if not all pairs (x, y) , some other pairs (x, y) should be separated.

+3
source

if you have a, b sum = a + b = (a ^ b) + (a & b) * 2 this equation may be useful for you

0
source

Here is the solution to get all such pairs

Logic: let the numbers be a and b, we know that

 s = a + b x = a ^ b

so

 x = (sb) ^ b

Since we know x and know s, so for all ints going from 0 to s, just check if this last equation holds

here is the code for this

 public List<Pair<Integer>> pairs(int s, int x) { List<Pair<Integer>> pairs = new ArrayList<Pair<Integer>>(); for (int i = 0; i <= s; i++) { int calc = (s - i) ^ i; if (calc == x) { pairs.add(new Pair<Integer>(i, s - i)); } } return pairs; }

A pair of pairs is defined as

 class Pair<T> { T a; T b; public String toString() { return a.toString() + "," + b.toString(); } public Pair(T a, T b) { this.a = a; this.b = b; } }

Verification Code:

 public static void main(String[] args) { List<Pair<Integer>> pairs = new Test().pairs(100,100); for (Pair<Integer> p : pairs) { System.out.println(p); } }

Output:

 0,100 4,96 32,68 36,64 64,36 68,32 96,4 100,0
0
source

More articles:


All Articles