Finding all solutions of the equation x⊕(a-x)=b

xorab.c

// Copyright 2013 Igor Burago
// SPDX-License-Identifier: ISC

#include <limits.h>
#include <stdio.h>

static unsigned
enum_bit(unsigned q, unsigned x, unsigned *xs) {
  if (q == 0) {
    *xs = x;
    return 1;
  }
  unsigned q1 = q & (q - 1);
  unsigned l = q ^ q1;
  unsigned n = enum_bit(q1, x, xs);
  n += enum_bit(q1, x|l, xs+n);
  return n;
}

static unsigned
solve_bit(unsigned a, unsigned b, unsigned *xs) {
  unsigned p = (a - b)/2;
  if (a-p != (p^b)) {
    return 0;
  }
  return enum_bit(b&~p, p, xs);
}

static unsigned
sol_count(unsigned a, unsigned b) {
  unsigned p = (a - b)/2;
  if (a-p != (p^b)) {
    return 0;
  }
  unsigned n = 0;
  for (unsigned q = b&~p; q != 0; q &= q-1) {
    n++;
  }
  return 1<<n;
}

static unsigned
filter_mod(unsigned *xs, unsigned n, unsigned a, unsigned b, unsigned l) {
  unsigned j = 0;
  for (unsigned i = 0; i < n; i++) {
    unsigned x = xs[j] = xs[i];
    j += (((x^(a-x))&l) == (b&l));
  }
  return j;
}

static unsigned
solve_mod(unsigned a, unsigned b, unsigned *xs) {
  unsigned n = 1;
  xs[0] = 0;
  for (unsigned k = 1; k <= a; k <<= 1) {
    unsigned l = (k<<1) - 1;
    n = filter_mod(xs, n, a, b, l);
    for (unsigned i = 0; i < n; i++) {
      xs[n+i] = xs[i] + k;
    }
    n = filter_mod(xs, 2*n, a, b, l);
  }
  n = filter_mod(xs, n, a, b, UINT_MAX);
  return n;
}

extern int
main(int argc, char **argv) {
  if (argc < 3) {
    return 1;
  }

  unsigned a, b;
  if (sscanf(argv[1], "%u", &a) != 1 || a == UINT_MAX) {
    return 1;
  }
  if (sscanf(argv[2], "%u", &b) != 1) {
    return 1;
  }

  unsigned xs[a+1];
  unsigned n = solve_bit(a, b, xs);
	printf("%u solutions found:\n", n);
  for (unsigned i = 0; i < n; i++) {
    printf("  %x\n", xs[i]);
  }

  return 0;
}