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

This topic is about an interview question: exchanging the values of two variables. There are only two variables, which seems simple, but a simple question can be accomplished in a variety of ways, including a relatively common implementation and a relatively clever one, although it is a simple question. however, through the interviewer's cognitive ability to the question, we can see the interviewer's level.

Summary of key points:

1 through intermediate variable exchange.

(2) exchange through summation and difference.

3 through XOR exchange.

Through the third variable

First of all, we give the simplest way.

Exchange the values of two variables.

Package chapter2;2.3. Public class Swap {4. Public static void main (String [] args) {5. Int x = 5 int 6. Int y = 10. Swap (x, y); 8. System.out.println (x); 9. System.out.println (y); 10. Value v = new Value (5, 10); 11. Swap (v); 12. System.out.println (v.x); 13. System.out.println (v.y) 14.} 15. / invalid exchange 16. Public static void swap (int x, int y) {17. Int temp = x Ting 18. X = y Ting 19. Y = temp;20.} 21. / / effective exchange 22. Public static void swap (Value value) {23. Int temp = value.x;24. Value.x = value.y;25. Value.y = temp;26. } 27.} 28.29.class Value {30. Int xtter31. Int YTH 32.33. Public Value (int x, int y) {34. This.x = x _ (th) 35. This.y = y36. } 37.}

The running result of the program is as follows:

510105

This program gives both valid swaps (lines 22-26) and invalid swaps (lines 16-20). Because the change of a parameter cannot react to the argument, you cannot use the method of variable exchange, but rather use the way to modify its member variables by reference. This is similar to the pointer effect in C / C++ language.

By way of addition

Through the third temporary variable, the values of the two variables can be successfully exchanged, but sometimes the interview questions are more demanding, that is, temporary variables are not allowed. In this way, it's a little complicated.

Exchange the value of two variables.

Package chapter2;2.3. Public class Swap2 {4. Public static void main (String [] args) {5. Value v1 = new Value (5,10); 6. Swap (v1); 7. System.out.println ("exchange result of v1:"); 8. System.out.println (v1.x); 9. System.out.println (v1.y); 10. Value v2 = new Value (1200000000, 1500000000); 11. Swap (v2); 12. System.out.println ("exchange result of v2:") 13. System.out.println (v2.x); 14. System.out.println (v2.y); 15. Value v3 = new Value (- 1200000000,-1500000000); 16. Swap (v3); 17. System.out.println ("exchange result of v3:"); 18. System.out.println (v3.x); 19. System.out.println (v3.y); 20.} 21.22. Public static void swap (Value v) {23. V.x = v.x + v.ytrex 24. V.y = v.x-v.ytert 25. V.x = v.x-v.ytrest26. } 27.}

The running result of the program is as follows:

Exchange result of v1:

one hundred and five

Exchange result of v2:

15000000001200000000

Exchange result of v3:

-1500000000-1200000000

The core part is the swap method (lines 22-26). The three statements of this method are interpreted as:

V.x = v.x + v.y; / store the sum of v.x and v.y in v.x, v.y = v.x-v.y; / v.x-v.y is the previous v.x value, assigned to v.yv.x = v.x-v.y; / v.x-v.y is the previous v.y value, assigned to v.x

In this way, the values of the two variables are also exchanged without passing temporary variables. Maybe the above method is not easy to understand at the moment, so consider this:

Int z = v.x + v.yscape v.y = z-v.ypoliv.x = z-v.y

It's just that another variable z is used here, and the above uses v.x to store the sum of v.x and v.y, but the effect of swapping is the same.

Notice that lines 10 and 15 of the program, the initial values of v.x and v.y are very large (small), so that when the swap method is executed (in the 10th behavior example):

V.x = v.x + v.y

The hexadecimal sum is as follows:

47868c00 (v.x) + 59682f00 (v.y) result: a0eebb00 (v.x + v.y)

Note that the highest bit of this result is 1, and the result is negative (the decimal value is 1594967296, that is, the sum of v.x and v.y has exceeded the maximum (minimum) value of the int type, and an overflow occurs.

Execute the following statement:

V.y = v.x-v.y

This calculation uses the overflowed value 1594967296 minus v.y (1500000000), and from the int type cut perspective, the result is overflowed again, as shown in hexadecimal:

A0eebb00 (v.x + v.y) 59682f00 (v.y) result: 47868c00 (result v.y)

After two spills, we get our expected value again. Similarly, the third statement of the swap method:

V.x = v.x-v.y

A0eebb00 (v.x + v.y) 47868c00 (v.y)

Result: 59682f00 (result v.x)

There was also an overflow, but the final difference also produced the desired result. It can be seen that when the sum of the two numbers is very large (small), although there is an overflow, but finally get the correct result by mistake. Although the results are correct, this way of addition is not very desirable.

By XOR

The bitwise XOR operator (^) has the property that two integer data x and y have:

(X ^ y ^ y) = x

This means that if one variable x differs from another variable y twice, the result is x. With this, you can swap the value of a variable.

Exchange the value of two variables 3.

1.package chapter2;2.3. Public class Swap3 {4. Public static void main (String [] args) {5. Value v = new Value (5,10); 6. Swap (v); 7. System.out.println (v.x); 8. System.out.println (v.y); 9.} 10.11. Public static void swap (Value v) {12. V.x = v.x ^ v.ytter13. V.y = v.x ^ v.ytter14. V.x = v.x ^ v.ypoli15.} 16.}

The running result of the program is as follows:

one hundred and five

The swap method (lines 11-15) is not complex, with only three statements:

V.x = v.x ^ v.y; (1) v.y = v.x ^ v.y; (2) v.x = v.x ^ v.y; (3)

Look at it this way: after the execution of (1), the value of v.x is the result of v.x (the value before XOR) and v.y. Similar to mathematical substitution, replace v.x (with a value of v.x ^ v.y) into (2), so (2) the assignment operator (the expression on the right side of = is equivalent to:

V.x ^ v.y ^ v.y / / v.x and v.y are values before operation

This value is v.x (the value before the XOR operation), and then assigned to the v.y on the left. At this point, the value of v.y is the value of v.x before XOR. Then replace v.x (the value is v.x ^ v.y) and v.y (the value is the value of v.x before XOR) into the right side of the assignment operator in (3), and the expression after substitution is equivalent to:

V.x ^ v.y ^ v.x / / v.x and v.y are values before operation

. Recommended: http://www.lemonpai.com/1508.html

This value is v.y and then assigned to v.x. At this point, the exchange of the two variables is completed. XOR is preferable to addition because XOR does not involve overflow. In terms of these three ways, the first way is the easiest to understand, and the third way is relatively mature and sophisticated. If it is an individual writing a program, it is recommended to use the simplest way, so that it is not easy to make mistakes, and the code is readable. It is convenient for later maintenance. If you are in the interview process, you can choose the third way to prove your ability.

Summary:

1. One variable x is different from the other variable y twice, and the resulting value is x.

two。 XOR operations can exchange the values of two variables, and this is preferable to adding and swapping.

infer other things from one fact

Since addition (the second way) can exchange the values of two variables, subtraction can certainly be achieved. Write a program that does not use the third temporary variable to subtract and exchange the values of the two variables.

Liang Yong, the author of this article, is from the lemon pie. Please indicate the source.

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.