algorithm to calculate XOR

You can build an XOR gate from NANDs (diagram here), so you could do it with an if statement with ! (NOT) and && AND (if we use C/C++/PHP as an example here). As for working it out in a constant time, the calculation is the same every iteration, so it will be constant.

A XOR can be built using AND and NOT (and combining them to build a NAND). Can you use AND and NOT?

In C#:

Func<bool, bool, bool> nand = (p, q) => !(p && q);

Func<bool, bool, bool> xor = (p, q) =>
{
    var s1 = nand(p, q);
    var s2a = nand(p, s1);
    var s2b = nand(q, s1);
    return nand(s2a, s2b);
};

I'm mimicking this: http://en.wikipedia.org/wiki/NAND_logic#XOR

In C#, using modulus, sum and multiply. (Limits: I'm using uint, so max 32 bits. It will work for ulong, so max 64 bits)

uint a = 16;
uint b = 5;
uint mult = 1;
uint res = 0;

for (int i = 0; i < 32; i++)
{
    uint i1 = a % 2;
    uint i2 = b % 2;

    if (i1 != i2) {
        res += mult;
    }

    a /= 2;
    b /= 2;
    mult *= 2;
}

Where res is the response.

Modulus can be built on top of division, multiplication and subtraction.

if the two are not equal, then they are xor.

xorBits(bit1,bit2){
     return bit1 != bit2?1:0
}

xorBooleans(boolean1,boolean2){
    return boolean1 != boolean2
}

First, let k be the smallest power of 2 greater than or equal to sqrt(n). k is still O(sqrt(n)) so this won't change the complexity.

To construct the full k by k table, we construct it one row at a time.

We start with the 0th row: this is easy, because 0 xor j = j.

for i in xrange(k):
    result[0][i] = i

Next, we go over the rows in gray-code order. The gray-code is a way of counting every number from 0 to one-less than a power of 2 by changing one bit at a time.

Because of the gray-code property, we're changing the row number by 1 bit, so we have an easy job computing the new row from the old since the xors will only change by 1 bit.

last = 0
for row in graycount(k):
    if row == 0: continue
    bit_to_change = find_changed_bit(last, row)
    for i in xrange(k):
        result[row][i] = flip_bit(result[last][i], bit_to_change))
    last = row

We need some functions to help us here. First a function that finds the first bit that's different.

def find_changed_bit(a, b):
    i = 1
    while True:
        if a % 2 != b % 2: return i
        i *= 2
        a //= 2
        b //= 2

We need a function that changes a bit in O(1) time.

def flip_bit(a, bit):
    thebit = (a // bit) % 2
    if thebit:
        return a - bit
    else:
        return a + bit

Finally, the tricky bit: counting in gray codes. From wikipedia, we can read that an easy gray code can be obtained by computing xor(a, a // 2).

def graycount(a):
    for i in xrange(a):
        yield slow_xor(a, a // 2)

def slow_xor(a, b):
    result = 0
    k = 1
    while a or b:
        result += k * (a % 2 == b % 2)
        a //= 2
        b //= 2
        k *= 2
    return result

Note that the slow_xor is O(number of bits in a and b), but that's ok here since we're not using it in the inner loop of the main function.