Four ways to swap the values ​​of two variables without using the third variable

Usually our approach is (especially in the learning stage): define a new variable and use it to complete the exchange. The code is as follows:

int a,b;
a=10; b=15;int t;
t=a; a=b; b=t;

This algorithm is easy to understand and is especially suitable for helping beginners understand the characteristics of computer programs. It is a classic application of assignment statements. In actual software development, this algorithm is simple and clear, does not cause ambiguity, and facilitates communication between programmers. Under normal circumstances, this algorithm (hereinafter referred to as the standard algorithm) should be used when encountering the problem of exchanging variable values.

The biggest disadvantage of the above algorithm is that it requires the use of a temporary variable. So can exchange be achieved without the help of temporary variables? The answer is yes! Here we can use three algorithms to implement: 1) arithmetic operations; 2) pointer address operations; 3) bit operations; 4) stack implementation.

1) Arithmetic operation

int a,b;
a=10;b=12;
a=b-a; //a=2;b=12b=b-a; //a=2;b=10a=b+a; //a=10;b=10

The principle is: treat a and b as points on the number axis, and perform them around the distance between the two points calculate.

The specific process: the first sentence "a=b-a" finds the distance between two points ab, and saves it in a; the second sentence "b=b-a" finds the distance from a to the origin distance (the difference between the distance between b and the origin and the distance between ab and ab), and save it in b; the third sentence "a=b+a" finds the distance between b and the origin (the distance between a and the origin and the distance between ab and ab) distance) and save it in a. Complete the exchange.
Compared with the standard algorithm, this algorithm has three more calculation processes, but does not use temporary variables. (Hereinafter referred to as arithmetic algorithm)

Disadvantage: It can only be used for numeric types, not strings and the like. a+b may overflow (beyond the range of int). Overflow is relative. If + overflows, - will be fine if - comes back. So it doesn't matter if it overflows or not, it's just unsafe.

2) Pointer address operation
Because the operation of the address actually performs integer operations, for example: subtracting two addresses to obtain an integer, indicating that the storage locations of the two variables in the memory are separated. How many bytes; the address is added to an integer, that is, "a+10" represents the address of the 10 class a data units after a with a as the base address. Therefore, in theory, the exchange of addresses can be completed through operations similar to arithmetic algorithms, thereby achieving the purpose of exchanging variables. That is:

int *a,*b; //假设*a=new int(10);*b=new int(20); //&a=0x00001000h,&b=0x00001200ha=(int*)(b-a); //&a=0x00000200h,&b=0x00001200hb=(int*)(b-a); //&a=0x00000200h,&b=0x00001000ha=(int*)(b+int(a)); //&a=0x00001200h,&b=0x00001000h

Through the above operation, the addresses of a and b have really been exchanged, and a points to the value originally pointed to by b, and does b point to the value originally pointed to by a? The above code can be compiled, but the execution results are incredible! Why?

First of all, you must understand that the operating system divides the memory into several areas: system code/data area, application code/data area, stack area, global data area, etc. When compiling the source program, constants, global variables, etc. are placed in the global data area, and local variables and dynamic variables are placed in the stack area. In this way, when the algorithm is executed to "a=(int*)(b-a)", the value of a is not 0x00000200h, but the base address of the memory area where variable a is located. The actual result is: 0x008f0200h, where 0x008f is The base address, 0200, is the displacement of a in the memory area. It is added automatically by the compiler. As a result, future address calculations are incorrect, causing a and b to point to other memory units in the area. Thirdly, negative numbers cannot appear in address operations, that is, when the address of a is greater than the address of b, b-aIs there a way to solve? certainly! The following is the improved algorithm:

if(a<b)
{
a=(int*)(b-a);
b=(int*)(b-(int(a)&0x0000ffff));
a=(int*)(b+(int(a)&0x0000ffff));
}else{
b=(int*)(a-b);
a=(int*)(a-(int(b)&0x0000ffff));
b=(int*)(a+(int(b)&0x0000ffff));
}

The biggest improvement of the algorithm is to use the AND operation "int(a)&0x0000ffff" in the bit operation, because the upper 16 bits of the address are the segment address, and the last 16 bits are the displacement address. After ANDing it with 0x0000ffff, the segment address is masked and only the displacement address is retained. This matches the original algorithm and gets the correct result.

This algorithm also completes the exchange of values ​​without using a third variable. Compared with arithmetic algorithms, it is difficult to understand, but it has its advantage, that is, when exchanging large data types, its execution speed is faster than arithmetic. The algorithm is fast. Because it exchanges addresses, but the variable value has not been moved in memory. (Hereinafter referred to as the address algorithm)

3) Bit operation

int a=10,b=12; //a=1010^b=1100;a=a^b; //a=0110^b=1100;b=a^b; //a=0110^b=1010;a=a^b; //a=1100=12;b=1010;

The realization of this algorithm is determined by the characteristics of the XOR operation. Through the XOR operation, Some bits in the data are flipped, while other bits are unchanged. This means that any number and any given value are XORed twice in a row, and the value remains unchanged.

4) Stack implementation. No further explanation is needed, the stack and related function definitions are omitted.

int exchange(int x,int y) 
{ 
     stack S; 
     push(S,x); 
     push(S,y); 
     x=pop(S); 
     y=pop(S); 
}

The above algorithms all realize the exchange of two variable values ​​without the help of other variables. In comparison, the arithmetic algorithm and the bit algorithm have the same amount of calculation, and the calculation in the address algorithm is more complicated. , but can easily realize the exchange of large types (such as custom classes or structures), while the first two can only exchange integer data (in theory, overloading the "^" operator can also realize the exchange of any structure) ).

The introduction of these three algorithms is not intended to be applied in practice, but to discuss technology and demonstrate the charm of programming. It can be seen from this that small skills in mathematics have considerable influence on programming, and if used properly, they will have unexpected magical effects. From the perspective of actual software development, the standard algorithm is undoubtedly the best and can solve any type of exchange problem.

The above is the detailed content of Four ways to swap the values ​​of two variables without using the third variable. For more information, please follow other related articles on the PHP Chinese website!