13 Replies Latest reply: Jun 5, 2010 2:25 PM by 3004 RSS

    Swapping two numbers in java w/o temporary variables

    843789
      Dear All,

      I wrote the following code, expecting it to swap the two integers x and y. The output is not as expected. Why?

      class A {
           public static void main ( String args[] ) {
                int x = 55;
                int y = 77;
                x ^= y ^= x ^= y;
                System.out.println(x+" "+y);
           }
      }

      // end of file

      The C++ equivalent (given below), works perfectly well.

      #include <iostream.h>

      main()
      {
           int x = 55;
           int y = 77;
           x ^= y ^= x ^= y;
           cout << x << " " << y << endl;
           return 0;
      }

      Can somebody explain, what is wrong in the above Java code?

      Regards,
      Sudheendran T L
        • 1. Re: Swapping two numbers in java w/o temporary variables
          843789
          class A {
          public static void main ( String args[] ) {
          int x = 55;
          int y = 77;
          x ^= y ^= x ^= y;
          System.out.println(x+" "+y);
          }
          }
          • 2. Re: Swapping two numbers in java w/o temporary variables
            3004
            Nothing is wrong with the Java code. That is, it's doing exactly what it's supposed to according to the rules of the Java language. What is wrong is your assumption that Java has the same rules as C++

            When you post code, use code tags to make it readable and prevent parts of it from being taken as markup. Copy/paste your code from your original source in your editor (NOT from your earlier post here). Highlight the code and click the CODE button. Use the Preview tab to see how it will look.

            Also, I hope you're only doing this as an academic exercise. The swap can be made to work in Java, but there's never a reason to do so in real code.
            • 3. Re: Swapping two numbers in java w/o temporary variables
              forumKid2
              There are a few ways to do it:

              With Integers
              int a = 5;
              int b = 10;
              b = a+b;
              a = b-a;
              b = b-a;
              System.out.println(b + " " + a);
              With XOR
                        
              int a = 5;
              int b = 10;
              a = a ^ b;
              b = a ^ b;
              a = a ^ b;
              System.out.println(b + " " + a);
              With Strings
                        
              String a = "abcd";
                        String b = "efg";
                        b = a+b;
                        a = b.substring(a.length());
                        b = b.substring(0, b.length()-a.length());
                        System.out.println(a + " " + b);
              It sounds like an interview question. I personally would introduce a third variable.
              • 4. Re: Swapping two numbers in java w/o temporary variables
                794029
                It comes down to how the bytecodes work, and order of operation.

                Let me do a more simple example (without using Bitwise-math) to explain.


                If i say:
                int x = 10;
                x  +=  x++;
                System.out.println(x);
                What is the answer?:
                a) 10
                b) 11
                c) 20
                d) 21

                (test the code yourself)
                ...
                ...
                ...

                Here is the order of operations that Java does for the above example:
                Line 1:
                int x is set to 10;
                Line 2:
                the right hand side is evaluated to 10;
                Load the current value of x to the left hand side (Lvalue = 10)
                Load the current value of x to the right hand side (Rvalue = 10)
                int x has it's value increased by 1; // x = 11
                The Rvalue is added with the Lvalue (10+10 = 20) and stored on x; // x = 20

                To say it in code, it is doing this:
                int x = 10;
                int Left = 10;
                int Right = 10;
                int x = x+1;  // x = 11
                int x = Left + Right; // x = 20
                Now, in C++ this order of operations isn't even defined (which means different c++ compilers could do it differently).

                Some might add 10+10, and then add 1 at the end. (x=21). Where as others might do it like java does.


                The same sort of thing is happening here.
                int x = 55;
                int y = 77;
                x ^= y ^= x ^= y;
                I think you would like it to mean this:
                int x = 55; // (0011 0111)
                int y = 77; // (0100 1101)
                 x ^= y;    // after this,x is  122 (011 1010)
                 y ^= x;    // after this y is   55  (0011 0111)
                 x ^=y;     // after this x is   77  (0100 1101)
                (do it this way you will get the correct result in java).

                However, even though the operations are done in that order, the values are stored differently when you do it all in 1 line
                  x ^= y ^= x ^= y; 
                Java does the evaluation is almost like this:
                    int x = 55; // (0011 0111)
                    int y = 77;
                    x ^= y ^= x ^= y;  // x= 55; y = 77;
                 //   .. becomes
                   55 ^= 77 ^=55 ^=77;
                 //   and it ends up doing this
                    x = 55 ^77 // x = 122
                    y = 77 ^ (55 ^77)  // y = 55
                    x = 55 ^ (77 ^ (55^77)) // x = 0
                  
                The actual bytecodes for what you are doing (ignoring the print statements) is:
                 0:   bipush  55      // push 55 onto stack
                 2:   istore_1         // store it into variable#1 (x)
                 3:   bipush  77      // push 77 onto stack
                 5:   istore_2         // store it into variable#2 (y)
                 6:   iload_1          // load 55
                 7:   iload_2          // load 77
                 8:   iload_1          // load 55
                 9:   iload_2          // load 77
                 10:  ixor              // integer xOR the previous 2 on stack (77 and 55) = 122
                 11:  dup              // duplicate 122 onto stack
                 12:  istore_1       // store one of the "122's" into x
                 13:  ixor             // integer XOR the previoius 2 on stack (122 and 77) = 55
                 14:  dup             // duplicate 55
                 15:  istore_2       // store one of the "55's" into y
                 16:  ixor             // integer XOR the previous 2 on stack (55 and 55) = 0
                 17:  istore_1      // store 0 into x
                • 5. Re: Swapping two numbers in java w/o temporary variables
                  3004
                  00jt wrote:
                  It comes down to how the bytecodes work, and order of operation.
                  It's not the bytecodes it's the language definition. The bytecode of course reflects and implements the JLS, but the JLS defines what will happen.
                  • 6. Re: Swapping two numbers in java w/o temporary variables
                    794029
                    jverd wrote:
                    00jt wrote:
                    It comes down to how the bytecodes work, and order of operation.
                    It's not the bytecodes it's the language definition. The bytecode of course reflects and implements the JLS, but the JLS defines what will happen.
                    po-ta-to, poh-tah-to

                    I'm saying that the order in which the bytecodes are invoked, (the order of their operation in the class file) is what java is really doing when it computes. Yes, that order is dependent on the JLS.

                    I wrote out the bytecodes so he could see what was happening.

                    I think it is funny how:
                    x += x++;
                    can mean 2 different things in C++ depending on the compiler.
                    Java, as a language, is much more defined in this regard.
                    • 7. Re: Swapping two numbers in java w/o temporary variables
                      3004
                      00jt wrote:
                      jverd wrote:
                      00jt wrote:
                      It comes down to how the bytecodes work, and order of operation.
                      It's not the bytecodes it's the language definition. The bytecode of course reflects and implements the JLS, but the JLS defines what will happen.
                      po-ta-to, poh-tah-to

                      I'm saying that the order in which the bytecodes are invoked, (the order of their operation in the class file) is what java is really doing when it computes. Yes, that order is dependent on the JLS.
                      My point is that you don't even need to bring the bytecodes into it. It can be described completely in terms of the source code.
                      I think it is funny how:
                      x += x++;
                      can mean 2 different things in C++ depending on the compiler.
                      Java, as a language, is much more defined in this regard.
                      Yup. And in C(++++), all that's specified about the relative sizes of, e.g., int, short, long, is that short <= int <= long. So we could have one compiler where short, int, and long are all 2 bytes, another where they're all 8 bytes, another where they are 2, 4, and 8, respectively, and a handful of other permutations.

                      I don't miss that at all.

                      Of course, anybody who writes
                       x += x++
                      in any language needs to be smacked upside the head anyway.
                      • 8. Re: Swapping two numbers in java w/o temporary variables
                        794029
                        >

                        My point is that you don't even need to bring the bytecodes into it. It can be described completely in terms of the source code.
                        I personally like looking at the bytecodes. Maybe too much info for the question i guess.. I just liked that fuller understanding.
                        Of course, anybody who writes
                         x += x++
                        in any language needs to be smacked upside the head anyway.
                        lol, but its my classic fun example.
                        • 9. Re: Swapping two numbers in java w/o temporary variables
                          843789
                          Thanks to all of you who responded so quickly to clarify.
                          Yes, I am doing this for academic purpose only.
                          P.S: 00jt, your insight into the problem is wonderful!
                          • 10. Re: Swapping two numbers in java w/o temporary variables
                            843789
                            Sudheendran wrote:
                            Yes, I am doing this for academic purpose only.
                            Then compare the bytecode outputs from the standard swap (using a temporary variable), and the "smart" XOR way. I wouldn't be surprised if the standard swap turns out to be the faster.
                            • 11. Re: Swapping two numbers in java w/o temporary variables
                              3004
                              wastrel wrote:
                              Sudheendran wrote:
                              Yes, I am doing this for academic purpose only.
                              Then compare the bytecode outputs from the standard swap (using a temporary variable), and the "smart" XOR way. I wouldn't be surprised if the standard swap turns out to be the faster.
                              The bytecode won't necessarily tell you which one will run faster. Both the translation of bytecode to natively executable code and hotspot's optimizations could overwhelm the very small difference in the bytecode.

                              And of course, we wouldn't choose one idiom over the other based on execution speed in a situation like this anyway
                              • 12. Re: Swapping two numbers in java w/o temporary variables
                                843789
                                jverd wrote:
                                The bytecode won't necessarily tell you which one will run faster.
                                It will for sure. Unless they're equally fast of course.
                                Both the translation of bytecode to natively executable code and hotspot's optimizations could overwhelm the very small difference in the bytecode.
                                That's unlikely. But if you want to be sure you can always run a benchmark.
                                And of course, we wouldn't choose one idiom over the other based on execution speed in a situation like this anyway
                                That was my point.
                                • 13. Re: Swapping two numbers in java w/o temporary variables
                                  3004
                                  wastrel wrote:
                                  jverd wrote:
                                  The bytecode won't necessarily tell you which one will run faster.
                                  It will for sure.
                                  No, it won't, for the reasons I mentioned

                                  >
                                  Both the translation of bytecode to natively executable code and hotspot's optimizations could overwhelm the very small difference in the bytecode.
                                  That's unlikely.
                                  I got a difference of 6 bytecode instructions. Those instruction will be run through hotspot, turned in to native instructions, and executed on the underlying hardware (which is probably a highly pipelined RISC processor that's much more sophisticated than the JVM). By the time all that has happened, I don't think it's all that unlikely that the difference will bear little resemblance to the 6 bytcode op delta we're looking at here.

                                  The point being: Simply looking at the bytecode doesn't tell you as much about the actual execution as people often assume.
                                  And of course, we wouldn't choose one idiom over the other based on execution speed in a situation like this anyway
                                  That was my point.
                                  It seemed to be the opposite of your point.