“This is my fourth day of participating in the First Challenge 2022. For more details: First Challenge 2022.”
Hello, I’m Q. We’ve summarized the first two methods above, and today we’ll talk about the last two.
Pointer address operation
We can think of a and B as address values in memory. Suppose a is 0x01FF5E70, b is 0x01FF5E90, and B-a represents how many bytes are stored between the two variables in memory. So we could theoretically swap the values of two variables using arithmetical logic.
The code is as follows (in C) :
// where a and b are pointer variables, store the address of 10 and 20
int *a = new int(10); //a= 0x01FF5e70, which represents the address stored in A
int *b = new int(20); //b= 0x01FF5e90, which represents the address stored in B
// The pointer variable is subtracted to get the number of bytes between addresses 20 and 10, and then converted to a pointer variable
a = (int*)(b-a); //b=0x01ff5e90; a=0x8
b = (int*)(b-a); //b=0x01ff5e70; a=0x8
a=(int*)(b+long(a));//b=0x01ff5e70; a=0x01ff5e90
Copy the code
B – a = 0x01FF5E90-0x01FF5E70 = 0x20, 0x20 converted to decimal is 32 bits, because an int takes up four bits, so this is 0x8.
The above is only the execution process under the theoretical state, if the direct execution is not able to achieve the exchange. Because the above code ignores one problem: after the code is compiled, the variables are stored in memory, and the memory area will have the base address.
A base address can be thought of as the starting point of a block of memory. The data above is all offset from the base address.
Address of a variable = base address of the variable + offset address of the variable
When we do b-a, we get 8, and then when we convert to pointer variable, we automatically add base address to 8, and then the result is not 0x8, so we get an error result.
In addition, address calculation can not appear negative numbers, that is, when the address of A is greater than the address of B, B-A < 0, the system automatically adopts the form of complement to express negative displacement, will also produce errors.
To solve this problem, we only need to ensure that the results obtained by B-A are not affected by the base address, so the following solution is given.
int *a = new int(10);
int *b = new int(20);
cout << a << "` ` ` ` `";
cout << b << "` ` ` ` `";
if(a < b){
a = (int*)(b-a);
cout << a << "` ` ` ` `";
b=(int*)(b-(long(a)&0x0000ffff));
cout << b << "` ` ` ` `";
a=(int*)(b+long(a));
cout << a << "` ` ` ` `";
} else {
b = (int*)(a-b);
cout << b << "` ` ` ` `";
a=(int*)(a-(long(b)&0x0000ffff));
cout << a << "` ` ` ` `";
b=(int*)(a+long(b));
cout << b << "` ` ` ` `";
}
Copy the code
Execution Result:
0x8dbe70`````0x8dbe90`````0x8`````0x8dbe70`````0x8dbe90`````
Copy the code
See this, I don’t know if you really understand. Anyway, the first time I saw it, it was very clear, and the second time I saw it, I didn’t understand it at all, so I have to think about it a little bit.
b=(int*)(b-(long(a)&0x0000ffff)); The neat thing about this instruction is that it uses the sum of bits. After the sum of a and 0x0000FFFF is applied, the base address of B-A is masked and only the offset address, which is the number of bytes we need, is preserved.
This method performs faster than arithmetic algorithms when exchanging large data types. Because it swaps addresses, variable values are never moved in memory.
An operation
Now that we’ve used bits, let’s say we can swap directly by xOR.
A brief introduction to the xOR rule:
- If a and B have different values, the xOR result is 1.
- If a and B have the same value, the xOR result is 0.
The following code
int a=10, b=12;// binary: a=1010; b=1100;
a = a^b;//a=0110; b=1100
b = a^b;//a=0110; b=1010
a = a^b;//a=1100; b=1010
System.out.println("a="+ a +",b="+ b);
Copy the code
The execution result
a=12,b=10
Copy the code
Xor operations can flip some bits of data and leave others unchanged. This means that any number and any given value are xor twice in a row, and the value remains the same.
Simple summary
The above four methods all achieve the exchange of values of two variables without the aid of third-party variables:
- Arithmetic operation and bit operation have the same amount of computation, and can only be used for the exchange of plastic data.
- Address calculation is more complex, it is easy to realize the exchange of large types (such as custom classes or structures);
- Theoretically, overloading the “^” operator can also realize the exchange of any structure;
The above is all the content of today, if you have different opinions or better idea, welcome to contact AH Q, add AH Q can join the technical exchange group to participate in the discussion!