Can the xor-swap be extended to more than two variables?

Question

I've been trying to extend the xor-swap to more than two variables, say n variables. But I've gotten nowhere that's better than 3*(n-1).

For two integer variables x1 and x2 you can swap them like this:

swap(x1,x2) {
  x1 = x1 ^ x2;
  x2 = x1 ^ x2;
  x1 = x1 ^ x2;
}

So, assume you have x1 ... xn with values v1 ... vn. Clearly you can "rotate" the values by successively applying swap:

swap(x1,x2);
swap(x2,x3);
swap(x3,x4);
...
swap(xm,xn); // with m = n-1

You will end up with x1 = v2, x2 = v3, ..., xn = v1.

Which costs n-1 swaps, each costing 3 xors, leaving us with (n-1)*3 xors.

Is a faster algorithm using xor and assignment only and no additional variables known?

Answer 1

As a partial result I tried a brute force search for N=3,4,5 and all of these agree with your formula.

Python code:

from collections import *

D=defaultdict(int) # Map from tuple of bitmasks to number of steps to get there
N=5
Q=deque()
Q.append( (tuple(1<<n for n in range(N)), 0) )
goal = (tuple(1<<( (n+1)%N ) for n in range(N)))
while Q:
    masks,ops = Q.popleft()
    if len(D)%10000==0:
        print len(D),len(Q),ops
    ops += 1
    # Choose two to swap
    for a in range(N):
        for b in range(N):
            if a==b:
                continue
            masks2 = list(masks)
            masks2[a] = masks2[a]^masks2[b]
            masks2 = tuple(masks2)
            if masks2 in D:
                continue
            D[masks2] = ops
            if masks2==goal:
                print 'found goal in ',ops
                raise ValueError
            Q.append( (masks2,ops) )