Is it possible to extend xor-swap to more than two variables?

Question

I am trying to extend xor-swap to more than two variables, for example n variables. But nowhere have I become better than 3*(n-1) .

For two integer variables x1 and x2 you can change them as follows:

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

So, suppose you have x1 ... xn with values v1 ... vn . It is clear that you can "rotate" the values ​​by applying swap sequentially:

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

As a result, you get x1 = v2 , x2 = v3 , ..., xn = v1 .

What is the cost of n-1 swaps, each of which costs 3 xors, leaving us with (n-1)*3 xors.

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

Answer 1

As a partial result, I tried brute force search for N = 3,4,5, and all of them are consistent 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) )