Shulou(Shulou.com)06/03 Report--

This article mainly explains "Why don't exchange XOR for two numbers". Interested friends might as well take a look at it. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "Why not exchange XOR for two numbers"?

Preface

There are many ways to exchange two.

The most classic is achieved with the help of a temporary variable, or through "XOR".

And, of course, the elegant a, b = b, an in Python.

Python's exchange without temporary variables is actually an ingenious use of the "operation stack", which is a feature skill at the language level and is outside the scope of our discussion.

Today, let's talk about why I suggest using temporary variables to implement the exchange instead of using "XOR."

Although this does not seem "high-end".

Strange "technique"

If you are a person who occasionally goes to LeetCode to do exercises, you may have seen some solutions.

They do not adopt the conventional practice of "using a temporary variable" when it comes to the exchange of two numbers.

Instead, it is implemented using the following "XOR":

A = a ^ b, b = a ^ b, a = a ^ b

This kind of "skill" has appeared in both official solutions and netizens.

When you don't understand this practice, it's very likely that just because of these lines of code, you don't bother to look at the idea of the whole solution.

But in fact, this is only a simple function of "two-number exchange".

After I got a preliminary understanding of the principle of this practice, there was a feeling that mathematicians came to do algorithm problems, which did skillfully use mathematical principles to exchange two numbers without the help of temporary variables.

But is it really more efficient for computers than with variables?

Does "XOR" mean efficient?

A piece of code that solves variables and a piece of "XOR" code may have the intuitive impression that it would be more efficient without the "XOR" of variables:

Public static void main (String [] args) {int a = 1; int b = 99; / / with the help of temporary variables int c = a; a = b; b = c; / / "XOR" a = a ^ b; b = a ^ b; a = a ^ b;}

Indeed, opening one more temporary variable requires adding a variable to the local variable table of the "stack frame", but that's it.

Even if we exchange not two numbers, but two large objects, the exchange through temporary variables will only add one more pointer variable, and will not create one more object on the heap.

How much will it affect if there is one more temporary variable? We try to analyze qualitatively in terms of memory and CPU (execution time).

From the perspective of memory

Because the added variable is only a variable in the local variable table of the "stack frame".

So it adds about 4 bytes of memory.

This memory is basically negligible relative to the entire "stack frame" size.

From CPU's point of view

Usually a variable has a creation cost and a destruction cost.

Since this temporary variable is only a record on the local variable table of the "stack frame" and will be destroyed as a whole with the pop-up of the "stack frame", there is no additional destruction cost in the first place.

As for the creation of variables, because this variable is only assigned on the stack, the whole creation process is almost nanosecond, with almost no impact on the execution time, that is, the creation cost is completely negligible.

"preliminary conclusion"

Based on the above general analysis, it may be concluded that the efficiency of the XOR scheme is roughly the same as that of the temporary variable scheme, or that the XOR scheme is slightly more efficient than the temporary variable scheme.

But in fact, the real situation is almost the opposite of our "preliminary analysis". "

The real situation

Let's come to the conclusion that a scheme with temporary variables is much faster than using XOR.

Why is XOR slower? Because in the scheme with temporary variables, only two memory reads and writes are involved, while in the XOR scheme, in addition to performing three XOR operations, we also need to do six reads and three writes (theoretically).

Compilation and comparison

To answer this question essentially, we need to analyze the assembly instructions compiled by the code of the two schemes.

For the following scenarios using variable exchange:

Int c = a * a = b * b = c

The compilation is as follows:

Movl b,% eax; load b from memory into register eax (read) movl a,% edx; load a from memory into register edx (read) movl% eax, a; store the contents of eax into memory a (write) xorl% eax,% eax; set eax to 0: set the return value movl% edx, b Save the contents of edx to memory b (write)

The corresponding assembly instruction is still relatively clear: the variables to participate in the operation must first be loaded into the register from memory, so to swap the two variables simply need to store them in memory in the opposite order.

You can see that this "scheme with temporary variables actually contains only four instructions to exchange data between memory and registers, two reads and two writes."

Let's take a look at the use of XOR:

A ^ = b / b ^ = a / a ^ = b

The compilation is as follows:

Movl b,% eax; load b from memory into register eax (read) movl a,% ecx; load a from memory into register ecx (read) movl% eax,% edx; save the value of eax to edx (write) xorl% ecx,% edx; ecx and edx XOR xorl% edx,% eax; edx and eax XOR xorl% eax,% edx Eax and edx XOR movl% eax, b; store the value of eax in memory b (write) xorl% eax,% eax; set eax to 0: set the return value movl% edx, a; store the value of edx in memory a (write)

Three simple lines of XOR need to be converted into so many assembly instructions.

At this point, I believe you have a deeper understanding of "Why not exchange XOR for two numbers". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.