异或交换可以扩展到两个以上的变量吗？ [英] Can the xor-swap be extended to more than two variables?

问题描述

我一直在尝试将异或交换扩展到两个以上的变量，例如 n 变量。但我无处比 3 *（n-1）更好。

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

对于两个整数变量 x1 和 x2 您可以像这样交换它们：

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;
}

因此，假设您有 x1 ... xn 值 v1 ... vn 。显然，您可以通过依次应用交换来旋转值：

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

您最终将得到 x1 = v2 ， x2 = v3 ，...， xn = v1 。

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

交换费用为 n-1 ，每次交换费用为 3 美元，给我们留下（n-1）* 3 异或。

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?

推荐答案

作为部分结果，我尝试了蛮力搜索N = 3,4,5，所有

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

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

这篇关于异或交换可以扩展到两个以上的变量吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！