SUM And XOR

April 1, 2016

The naive solution iterates over a and b up to s, which is quadratic. But a little algebra makes an easy linear solution. Given

s = a + b
x = a ^ b

then

x = (s - b) ^ b

Since s and x are known, check all integers b from 0 to s and report those that work:

(define (sum-xor s x)
  (list-of (list (- s b) b)
    (b range 1 s)
    (= x (bitwise-xor (- s b) b))))
> (sum-xor 9 5)
((7 2) (6 3) (3 6) (2 7))

A simple optimization works half-way through the range, generating both a pair and its conjugate whenever it finds a suitable b, but we won’t bother.

We used list comprehensions from the Standard Prelude. You can run the program at http://ideone.com/eDfLxn.

Advertisements

Pages: 1 2

8 Responses to “SUM And XOR”

  1. Marcos said
    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)
    
  2. Ernie said

    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

  3. matthew said

    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;
      }
    }
    
  4. J.Fossy said

    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;
    }

  5. matthew said

    @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/

  6. Chris Judge said

    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;
            }
    
  7. jay said

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: