SUM And XOR
April 1, 2016
I don’t know the origin of it, but today’s exercise must be either a homework problem or an interview question:
Assume there are two positive integers a and b that have sum s and XOR x. Given an s on the range [2, 1012] and x on the range [0, 1012], find a list of possible values of the ordered pairs (a, b). For instance, given s = 9 and x = 5, there are four possible pairs: (2, 7), (7, 2), (3, 6) and (6, 3).
Your task is to write a program that finds the pairs. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
def sums_target(target): a = target - 1 for i in range(1, target): yield i, a a -= 1 def sum_and_xor(sum, xor): for pair in sums_target(sum): a, b = pair if a ^ b == xor: yield a, b for solution in sum_and_xor(9, 5): print(solution)Actually you only have to loop through the range 0 to s/2 since if (a,b) is a solution, then (b,a) is a solution
Hard to resist a nice bit-twiddling challenge: s and x differ just at positions where there is a carry in from the right, and x tells us where the two numbers differ: if the number are the same at a particular bit position, then there is a carry just if they are both 1, if both 0, there can be no carry. If the digits are different at a given position, then because addition and xor are symmetric, we can have 0 and 1 either way round in the original numbers, regardless of the carries. So, the solutions have a certain number of bits fixed, and we can have all possible combinations of the other bits, so we can just count through those combinations: if a is a possible value, we can find the next possible value by setting all fixed bits to 1, incrementing, then setting the fixed bits back to their correct values. Maybe some code is clearer:
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef unsigned int T; int main(int argc, char *argv[]) { T a0 = strtoul(argv[1],NULL,0); T b0 = strtoul(argv[2],NULL,0); T s = a0 + b0; T x = a0 ^ b0; // a and b are different at these positions T carries = (s ^ x) >> 1; // Positions where there is a carry out T fixed = ~x & carries; // a & ~x == b & ~x == fixed, for all solutions T a = fixed; printf("s = %u x = %u\n",s,x); while(true) { T b = a ^ x; if (b < a) break; assert(a+b == s); printf("%u %u\n",a,b); a = (((a | ~x) + 1) & x) | fixed; } }Solutions fast and slow in Racket.
For each x=2^k :
i) a b = a + 2^k
s = a + a + 2^k = 2a + 2^k
a = (s – 2^k)/2
ii) a >= 2^k => b = a – 2^k
s = a + a – 2^k = 2a – 2^k
a = (s + 2^k)/2
This is true for each bit of x => so a = (s +/- all combinations of 2^k of x)/2 or there is no result
//————————————————————————–
#include
//————————————————————————–
int main(int argn, char *argv[]) {
if ( argn != 3 ) {
printf(“usage: %s
\n\n”, argv[0]);return 1; //==========================================================>
}
int s = atoi(argv[1]);
int x = atoi(argv[2]);
printf(“s=%d x=%d\n:\n”, s, x);
int i, j;
int n;
int m;
int b[16];
for ( i = 0, m = 1, n = 0;
i m;
i++, m <<= 1
) {
if ( x & m ) {
b[n] = m;
n++;
}
}
for ( i = 0;
i < (1 << n);
i++
) {
int a = s;
for ( j = 0, m = 1;
j < n;
j++, m <>= 1;
int b = s – a;
if ( (a ^ b) != x ) {
//printf(“a=%d b=%d s=%d x=%d FALSE\n”, a, b, a + b, a ^ b);
printf(“no results (sorry)\n”);
return 1; //========================================================>
}
return 0;
}
@J.Fossy: That looks interesting but it’s all got a bit garbled, you might want to have a look at https://en.support.wordpress.com/code/posting-source-code/
In c#:
static List<Tuple<int, int>> getSumXOR (int s, int x) { List<Tuple<int, int>> t = new List<Tuple<int, int>>(); for (int i = 1; i <= s / 2; i++) { int j = i ^ x; if (s == i + j) { t.Add(new Tuple<int, int>(i, j)); t.Add(new Tuple<int, int>(j, i)); } } return t; }JS:
var coupleSumXOR = function(sum, cant) { var couples = []; var j; var halfway = Math.floor(sum / 2); cant = cant <= halfway ? cant : sum - cant; for (var i = 1; i <= halfway; i++) { if (i !== cant) { j = sum - i; i === j ? couples.push([i,j]) : couples.push([i, j], [j,i]); }; }; return couples; }; console.log(coupleSumXOR(10, 3));thanks for posting problems, good exercise