当前位置： 文江博客话题详情

XOR变量交换如何工作？

发布于 2025-01-24 21:22:28 字数 209 浏览 5 评论 0原文

有人可以向我解释XOR交换两个没有温度变量的变量如何工作？

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

我了解它的作用，但是有人可以使我了解它的工作原理吗？

原文

Can someone explain to me how XOR swapping of two variables with no temp variable works?

void xorSwap (int *x, int *y)
{
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

I understand WHAT it does, but can someone walk me through the logic of how it works?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（12）

〆凄凉。 2025-01-31 21:22:28

您可以通过进行替换来查看它的工作方式：

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

替换，

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

因为Xor是完全关联的和交换的：

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

因为x xor x == 0 for任何x，

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

以及x xor 0 == x对于任何X，

y2 = x0
x2 = y0

并且交换完成。

You can see how it works by doing the substitution:

x1 = x0 xor y0
y2 = x1 xor y0
x2 = x1 xor y2

Substituting,

x1 = x0 xor y0
y2 = (x0 xor y0) xor y0
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0)

Because xor is fully associative and commutative:

y2 = x0 xor (y0 xor y0)
x2 = (x0 xor x0) xor (y0 xor y0) xor y0

Since x xor x == 0 for any x,

y2 = x0 xor 0
x2 = 0 xor 0 xor y0

And since x xor 0 == x for any x,

y2 = x0
x2 = y0

And the swap is done.

回复 原文
摘星┃星的人 2025-01-31 21:22:28

其他人已经解释了这一点，现在我想解释为什么 是一个好主意，但是现在不是。

早在我们拥有简单的单个周期或多循环CPU的那一天，使用此技巧来避免昂贵的内存消耗或溢出到堆栈中，便宜了。但是，现在我们拥有带有大量管道的CPU。 P4的管道范围从其管道中的20到31（大约）阶段，在这些阶段中，阅读和写入寄存器之间的任何依赖性都可能导致整个事情停滞不前。 XOR交换在A和B之间具有一些非常沉重的依赖性，实际上完全没有关系，但实际上在管道中拖延了管道。停滞的管道会导致慢速代码路径，如果此交换在您的内部循环中，您将非常缓慢地移动。

在一般实践中，您的编译器可以弄清楚当您与临时变量交换时，您真正想做的事情，并可以将其编译为单个 <> xchg 指令。使用XOR交换使编译器更难猜测您的意图，因此正确优化它的可能性要小得多。更不用说代码维护等。

Other people have explained it, now I want to explain why it was a good idea, BUT now isn't.

Back in the day when we had simple single cycle or multi-cycle CPUs, it was cheaper to use this trick to avoid costly memory dereferences or spilling registers to the stack. However, we now have CPUs with massive pipelines instead. The P4's pipeline ranged from having 20 to 31 (or so) stages in their pipelines, where any dependence between reading and writing to a register could cause the whole thing to stall. The xor swap has some very heavy dependencies between A and B that don't actually matter at all but stall the pipeline in practice. A stalled pipeline causes a slow code path, and if this swap's in your inner loop, you're going to be moving very slowly.

In general practice, your compiler can figure out what you really want to do when you do a swap with a temp variable and can compile it to a single XCHG instruction. Using the xor swap makes it much harder for the compiler to guess your intent and therefore much less likely to optimize it correctly. Not to mention code maintenance, etc.

回复 原文
失而复得 2025-01-31 21:22:28

我喜欢以图形方式而不是数字思考。

假设您从x = 11开始，y = 5
在二进制中（我要使用假设的4位机器），

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

现在是X和Y，XOR是一个反转操作，两次进行操作是一面镜子：

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!

I like to think of it graphically rather than numerically.

Let's say you start with x = 11 and y = 5
In binary (and I'm going to use a hypothetical 4 bit machine), here's x and y

       x: |1|0|1|1|   -> 8 + 2 + 1
       y: |0|1|0|1|   -> 4 + 1

Now to me, XOR is an invert operation and doing it twice is a mirror:

     x^y: |1|1|1|0|
 (x^y)^y: |1|0|1|1|   <- ooh!  Check it out - x came back
 (x^y)^x: |0|1|0|1|   <- ooh!  y came back too!
回复 原文
堇色安年 2025-01-31 21:22:28

这是一个应该更容易掌握的东西：

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

现在，可以将XOR技巧理解为^可以被认为是+>+>+ 或 - 。就像：

x + y - ((x + y) - x) == x

，所以：

x ^ y ^ ((x ^ y) ^ x) == x

Here's one that should be slightly easier to grok:

int x = 10, y = 7;

y = x + y; //x = 10, y = 17
x = y - x; //x = 7, y = 17
y = y - x; //x = 7, y = 10

Now, one can understand the XOR trick a little more easily by understanding that ^ can be thought of as + or -. Just as:

x + y - ((x + y) - x) == x

, so:

x ^ y ^ ((x ^ y) ^ x) == x
回复 原文
Hello爱情风 2025-01-31 21:22:28

它起作用的原因是因为XOR不会丢失信息。如果您可以忽略溢出，则可以使用普通的加法和减法来做同样的事情。例如，如果变量对A，B最初包含值1,2，则可以像这样交换它们：

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

顺便说一句，有一个旧的技巧用于编码单个“指针”中的2条链接列表。
假设您在地址A，B和C处有一个内存块列表。每个块中的第一个单词分别是：

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

如果您可以访问块A B中的“指针”并减去A，依此类推。它的工作也一样。要沿着列表运行，您需要将指针保持在两个连续的块上。当然，您将使用XOR代替加法/减法，因此您不必担心溢出。

如果您想玩一些乐趣，可以将其扩展到“链接的网络”。

The reason WHY it works is because XOR doesn't lose information. You could do the same thing with ordinary addition and subtraction if you could ignore overflow. For example, if the variable pair A,B originally contains the values 1,2, you could swap them like this:

 // A,B  = 1,2
A = A+B // 3,2
B = A-B // 3,1
A = A-B // 2,1

BTW there's an old trick for encoding a 2-way linked list in a single "pointer".
Suppose you have a list of memory blocks at addresses A, B, and C. The first word in each block is , respectively:

 // first word of each block is sum of addresses of prior and next block
 0 + &B   // first word of block A
&A + &C   // first word of block B
&B + 0    // first word of block C

If you have access to block A, it gives you the address of B. To get to C, you take the "pointer" in B and subtract A, and so on. It works just as well backwards. To run along the list, you need to keep pointers to two consecutive blocks. Of course you would use XOR in place of addition/subtration, so you wouldn't have to worry about overflow.

You could extend this to a "linked web" if you wanted to have some fun.

回复 原文
哭了丶谁疼 2025-01-31 21:22:28

大多数人会使用临时变量交换两个变量x和y，例如：

tmp = x
x = y
y = tmp

这是一个简洁的编程技巧，可以交换两个值而不需要临时：

x = x xor y
y = x xor y
x = x xor y

使用XOR交换两个变量

在第1行上，我们将X和Y（使用XOR）组合以获取此“混合动力”，然后将其存储在X中。 XOR是保存信息的好方法，因为您可以再次进行XOR删除信息。

在第2行上。我们将混合动力车与y一起取消，从而取消所有y信息，仅留下x。我们将此结果保存回Y，所以现在它们已交换了。

在最后一行，x仍然具有混合值。我们再次使用y（现在具有X的原始值）将其XOR XOR XOR删除，以从混合动力车中删除X的所有痕迹。这使我们有y，交换已完成！

计算机实际上具有一个隐式的“温度”变量，该变量在将它们写回寄存器之前存储中间结果。例如，如果将3添加到寄存器（以机器语言为pseudocode中）：

ADD 3 A // add 3 to register A

Alu（算术逻辑单元）实际上是执行指令3+a的原因。它采用输入（3，a）并创建结果（3 + a），然后CPU将其存储回A的原始寄存器。因此，在获得最终答案之前，我们将Alu用作临时划痕空间。

我们将Alu的隐式临时数据视为理所当然，但它始终存在。以类似的方式，在x = x xor y的情况下，ALU可以返回XOR的中间结果，此时CPU将其存储到X的原始寄存器中。

由于我们不习惯考虑贫穷，被忽视的Alu，因此XOR交换似乎是神奇的，因为它没有明确的临时变量。一些机器具有1步交换XCHG指令，可以交换两个寄存器。

Most people would swap two variables x and y using a temporary variable, like this:

tmp = x
x = y
y = tmp

Here’s a neat programming trick to swap two values without needing a temp:

x = x xor y
y = x xor y
x = x xor y

More details in Swap two variables using XOR

On line 1 we combine x and y (using XOR) to get this “hybrid” and we store it back in x. XOR is a great way to save information, because you can remove it by doing an XOR again.

On line 2. We XOR the hybrid with y, which cancels out all the y information, leaving us only with x. We save this result back into y, so now they have swapped.

On the last line, x still has the hybrid value. We XOR it yet again with y (now with x’s original value) to remove all traces of x out of the hybrid. This leaves us with y, and the swap is complete!

The computer actually has an implicit “temp” variable that stores intermediate results before writing them back to a register. For example, if you add 3 to a register (in machine-language pseudocode):

ADD 3 A // add 3 to register A

The ALU (Arithmetic Logic Unit) is actually what executes the instruction 3+A. It takes the inputs (3,A) and creates a result (3 + A), which the CPU then stores back into A’s original register. So, we used the ALU as temporary scratch space before we had the final answer.

We take the ALU’s implicit temporary data for granted, but it’s always there. In a similar way, the ALU can return the intermediate result of the XOR in the case of x = x xor y, at which point the CPU stores it into x’s original register.

Because we aren’t used to thinking about the poor, neglected ALU, the XOR swap seems magical because it doesn’t have an explicit temporary variable. Some machines have a 1-step exchange XCHG instruction to swap two registers.

回复 原文
陌路黄昏 2025-01-31 21:22:28

@vonc 正确，它是一个整洁的数学技巧。想象一下4个单词，看看这是否有帮助。

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101

@VonC has it right, it's a neat mathematical trick. Imagine 4 bit words and see if this helps.

word1 ^= word2;
word2 ^= word1;
word1 ^= word2;


word1    word2
0101     1111
after 1st xor
1010     1111
after 2nd xor
1010     0101
after 3rd xor
1111     0101
回复 原文
拥抱没勇气 2025-01-31 21:22:28

基本上XOR方法中有3个步骤：

A'= A Xor B（1）
b'= a'xor b（2）
a“ = a'xor b'（3）

了解 为什么 首先请注意：

  1. XOR才会产生1，只有当它的操作数中之一是1，另一个为零；
  2. Xor是交换性，因此a xor b = b xor a;
  3. XOR是 sosidiative so（a xor b）xor c = a xor（b xor c）;和
  4. a xor a = 0（从

一个步骤（1），A的二进制表示仅在A和B具有相对位的位位置的位置。那就是（AK = 1，BK = 0）或（AK = 0，BK = 1）。现在，当我们在步骤（2）中进行替换时，我们得到：

b'=（a xor b）xor b
= a xor（b xor b），因为xor是关联
= xor 0，因为上面的[4]
= a由于XOR的定义（请参阅 1 上面）

我们可以代替步骤（3）：

a” =（a xor b）xor a
=（b xor a）xor a，因为xor是交换的
= b xor（a xor a），因为xor是关联
= b xor 0，因为[4]上方
= b由于XOR的定义（请参见 1 上面）

更多 ）
更多详细信息此处：
必要且足够的

Basically there are 3 steps in the XOR approach:

a’ = a XOR b (1)
b’ = a’ XOR b (2)
a” = a’ XOR b’ (3)

To understand why this works first note that:

  1. XOR will produce a 1 only if exactly one of it’s operands is 1, and the other is zero;
  2. XOR is commutative so a XOR b = b XOR a;
  3. XOR is associative so (a XOR b) XOR c = a XOR (b XOR c); and
  4. a XOR a = 0 (this should be obvious from the definition in 1 above)

After Step (1), the binary representation of a will have 1-bits only in the bit positions where a and b have opposing bits. That is either (ak=1, bk=0) or (ak=0, bk=1). Now when we do the substitution in Step (2) we get:

b’ = (a XOR b) XOR b
= a XOR (b XOR b) because XOR is associative
= a XOR 0 because of [4] above
= a due to definition of XOR (see 1 above)

Now we can substitute into Step (3):

a” = (a XOR b) XOR a
= (b XOR a) XOR a because XOR is commutative
= b XOR (a XOR a) because XOR is associative
= b XOR 0 because of [4] above
= b due to definition of XOR (see 1 above)

More detailed information here:
Necessary and Sufficient

回复 原文
灼痛 2025-01-31 21:22:28

作为旁注，我几年前以交换整数的形式独立地重新发明了该轮子：（

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

上面以一种难以阅读的方式提到这一点），

完全相同的推理适用于XOR交换：a ^ b ^ b = a和a ^ b ^ a = a。由于Xor是可交换的，因此X ^ X = 0和X ^ 0 = X，因此这很容易看到

= a ^ b ^ b
= a ^ 0
= a

，

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

希望这会有所帮助。这种解释已经给出了...但不是很明显IMO。

As a side note I reinvented this wheel independently several years ago in the form of swapping integers by doing:

a = a + b
b = a - b ( = a + b - b once expanded)
a = a - b ( = a + b - a once expanded).

(This is mentioned above in a difficult to read way),

The exact same reasoning applies to xor swaps: a ^ b ^ b = a and a ^ b ^ a = a. Since xor is commutative, x ^ x = 0 and x ^ 0 = x, this is quite easy to see since

= a ^ b ^ b
= a ^ 0
= a

and

= a ^ b ^ a 
= a ^ a ^ b 
= 0 ^ b 
= b

Hope this helps. This explanation has already been given... but not very clearly imo.

回复 原文
八巷 2025-01-31 21:22:28

我只想添加数学解释，以使答案更加完整。在组理论，xor是 abelian group ，也称为通勤组。这意味着它满足五个要求：封闭，关联性，身份元素，逆元素，交换性。

XOR交换公式：

a = a XOR b
b = a XOR b
a = a XOR b

扩展公式，替换A，B具有先前公式：

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b

交换性指的是“ A Xor B”等于“ B Xor A”：

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b

arsisigiativity均表示“（A XOR B）XOR C”等于Xor（B Xor）（b xor） c）“：

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b)
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b)

XOR中的反元素本身，这意味着任何具有本身的值XOR给出了零：

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0

XOR中的身份元素为零，这意味着任何具有零值的值XOR都不会变化：

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0 
            = a
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0 
            = b XOR 0
            = b

您可以在中获取更多信息 。 组理论。

I just want to add a mathematical explanation to make the answer more complete. In group theory, XOR is an abelian group, also called a commutative group. It means it satisfies five requirements: Closure, Associativity, Identity element, Inverse element, Commutativity.

XOR swap formula:

a = a XOR b
b = a XOR b
a = a XOR b

Expand the formula, substitute a, b with previous formula:

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b

Commutativity means "a XOR b" equal to "b XOR a":

a = a XOR b
b = a XOR b = (a XOR b) XOR b
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b

Associativity means "(a XOR b) XOR c" equal to "a XOR (b XOR c)":

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b)
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b)

The inverse element in XOR is itself, it means that any value XOR with itself gives zero:

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0

The identity element in XOR is zero, it means that any value XOR with zero is left unchanged:

a = a XOR b
b = a XOR b = (a XOR b) XOR b 
            = a XOR (b XOR b) 
            = a XOR 0 
            = a
a = a XOR b = (a XOR b) XOR (a XOR b) XOR b 
            = (b XOR a) XOR (a XOR b) XOR b 
            = b XOR (a XOR a) XOR (b XOR b) 
            = b XOR 0 XOR 0 
            = b XOR 0
            = b

And you can get further information in group theory.

回复 原文
尬尬 2025-01-31 21:22:28

我知道这个问题已经有很长时间了，有很多答案。但是，我有自己的“语言”技巧来理解位于位的魔法。也许对于某人而言，这将很有用。

XOR仅在其操作数中的一个是1而另一个是零时产生1的。因此，XOR是两个数字之间的差异。

  1. 使用*X ^= *y;我们将此差异存储在x中。
  2. 如果我们知道第二个数字和x和y之间的差异，那么我们可以通过*y ^= *x;找到第一个数字，
  3. 如果我们知道x和y之间的差异，并且我们知道 可以通过*x ^= *y;找到第二个

数字

x = First number;
y = Second number;

After *x ^= *y
x = Difference between first and second number
y = Second number

After *y ^= *x
x = Difference between first and second number
y = First Number

After *x ^= *y
x = Second number
y = First number

第一个数字，我们 必须尝试想象我脑海中的很多数字。这就是为什么我的回答中没有数值表示的原因。

I know the question has been asked for quite some time and there are many answers to it. However, I have my own "linguistic" trick for understanding bitwise magic. Perhaps for someone it will be useful.

XOR will only produce 1 if exactly one of its operands is 1 and the other is zero. Therefore XOR is the difference between two numbers.

  1. With *x ^= *y; we store this difference in x.
  2. If we know the second number and the difference between x and y, then we can find out the first number with *y ^= *x;
  3. If we know the difference between x and y, and we know the first number, we can find out the second number with *x ^= *y;

I'm having trouble translating into English, so I'll add a graphical representation:

x = First number;
y = Second number;

After *x ^= *y
x = Difference between first and second number
y = Second number

After *y ^= *x
x = Difference between first and second number
y = First Number

After *x ^= *y
x = Second number
y = First number

I use this so I don't have to try to imagine a lot of numbers in my head. That is why there is no numerical representation in my answer.

回复 原文
你穿错了嫁妆 2025-01-31 21:22:28

其他人已经发布了解释，但我认为如果伴随一个很好的例子，最好理解。

xor真实

表和b = 0101我们能够以这样的方式交换值：

A = 1100
B = 0101


A ^= B;     => A = 1100 XOR 0101
(A = 1001)

B ^= A;     => B = 0101 XOR 1001
(B = 1100)

A ^= B;     => A = 1001 XOR 1100
(A = 0101)


A = 0101
B = 1100

Others have posted explanations but I think it would be better understood if its accompanied with a good example.

XOR Truth Table

If we consider the above truth table and take the values A = 1100 and B = 0101 we are able to swap the values as such:

A = 1100
B = 0101


A ^= B;     => A = 1100 XOR 0101
(A = 1001)

B ^= A;     => B = 0101 XOR 1001
(B = 1100)

A ^= B;     => A = 1001 XOR 1100
(A = 0101)


A = 0101
B = 1100
回复 原文
~没有更多了~

关于作者

墟烟

暂无简介

文章
评论
27 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

alipaysp_snBf0MSZIv

文章 0 评论 0

梦断已成空

文章 0 评论 0

瞎闹

文章 0 评论 0

凯凯我们等你回来

文章 0 评论 0

寄意

文章 0 评论 0

似梦非梦

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文