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

xorab.c

/* Copyright 2013 Igor Burago. Distributed under the ISC License terms. */

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

typedef unsigned uint;

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

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

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

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

uint
solve_mod(uint a, uint b, uint *xs) {
	uint n = 1;
	xs[0] = 0;
	for (uint k = 1; k <= a; k <<= 1) {
		uint l = (k<<1) - 1;
		n = filter_mod(xs, n, a, b, l);
		for (uint 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;
}

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

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

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

	return 0;
}