异或交换可以扩展到两个以上的变量吗？

我一直在尝试将异或交换扩展到两个以上的变量，例如n变量。但我没有得到比这更好的地方3*(n-1).

对于两个整型变量x1 and x2你可以像这样交换它们：

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

所以，假设你有x1 ... xn有价值观v1 ... vn。显然，您可以通过连续应用交换来“旋转”值：

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

你最终会得到x1 = v2, x2 = v3, ..., xn = v1.

哪些费用n-1互换，每次成本3异或，留给我们(n-1)*3 xors.

是否存在仅使用异或和赋值并且没有已知其他变量的更快算法？

作为部分结果，我尝试对 N=3,4,5 进行强力搜索，所有这些都符合您的公式。

Python代码：

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) )