Code pondering – Number 1: Swapping two integers

Having done a fair few academic computer science courses and various coding jobs in a past-life I found that it was often thinking about the smallest code snippets carefully that you pick-up the raw building blocks for good, safe and efficient code. I haven’t written much code recently so have been brushing up my basics.

Compilers are now so good and computers so powerful that in practice you can write pretty terrible code and still make a perfectly performant and functional application.

One famous code problem is to swap two numbers without using an additional temporary variable. So you use only the memory already storing the numbers without requiring extra for the temporary variable. Consider….

 

Method 1: Using a temporary variable

int temp;

int a = 6;

int b = 5;

 

temp = a;

a = b;

b = temp;

 

Method 2: Avoiding a temporary variable

int a = 6;

int b = 5;

 

a = a + b;

b = a – b;

a = a – b;

 

OK now let’s think about this harder, which method is better?:

  • Method 2 seems clever and no unnecessary memory used

But:

  • It’s far less readable
  • If you really are just swapping two integers the extra memory for a single integer is negligible
  • the sum (a+b) can larger than the addressable space of an integer so overflow could occur, i.e. (a+b) could wrap around and the algorithm break!
  • If using real or another data type you could pick up machine level errors
  • I suspect many modern compilers would take care of this for you
  • With method 1; a is safely stored in temp should something go wrong
  • Both methods use the same number of copies but the amount of checking required to ensure no overflow occurs on (a+b) and similar really is more trouble than it’s worth and would make the code look messy

So when would you avoid a temporary variable:

  • When you are certain your data is going to be well below half the capacity of the data type (e.g. int) – more relevant if looking at facetted data in real format; i.e. scenarios where you can safely avoid extra checks and code
  • When you don’t care about machine level noise
  • When it isn’t just two pieces of data but a vast array of data perhaps representing a frame buffer or screen

Of course, we can now go on to ponder how this code could be made fail safe…. But it’s amazing how three lines of code make you think a bit harder…. And another discussion is using pointers …

I’d be interested to hear whether people actually use Method 2 (other than those using EDSAC2) and how much can be relied on to be taken away by compilers… and whether people still think hard about such things…

 

 

13 thoughts on “Code pondering – Number 1: Swapping two integers

Add yours

  1. In assembly language programming for optimizing the process, you usually would use the register or a stack for operations like that, which is tantamount to creating a temporary variable. The other advantage of temporary variables is that you can check the success of the operation before moving ahead, in case something unexpected happens and the operation fails along the way. At least that way, you have a higher degree of assurance that the current values of a and b are not going to get lost.

    Liked by 1 person

    1. Well this was kind of the point of the post…. I can imagine scenarios where checking success is more trouble than worth e.g. gaming/video – far better to move on from a frame glitch…. and that is the scenario where you might be dealing with vast arrays e.g. a screen BUT in that scenario I would imagine swapping variables would be inefficient and you’d be looking more at a higher level strategy of pointer manipulation…

      I googled a fair bit an found loads of people showing this off as clever code… and a lot of sites listing it as a sample interview question…. yes it’s cute and shows you can add / subtract BUT I’d be asking the candidate …. so when would you actually do this and why and so far I haven’t come up with an actual scenario I would… maybe something clever in HPC???? So still open to comments….

      Just because you can doesn’t always mean you should….

      Liked by 1 person

      1. You would use method 2 – well, for me – when precision is involved and the stack space for variables and pointers is not under contention. The math operations themselves to emulate a value swap, in itself, produces something really cool:

        A means to check your int values and if they truly swapped: especially for distance, GPS, and fixed numbers the variables are holding. It also allows you to see if the variables aren’t being violated by another public function, etc.

        So, we know:

        int a = 6;
        int b = 5;

        Now, we perform the math:

        a = a + b;
        b = a – b;
        a = a – b;

        Pretty much, if b != | 6 …. something is broken. Likewise with B.

        Just a thought as stacks are stacks. They can be violated.

        Liked by 1 person

    2. Rachel: I salivate to code questions such as these! Efficiency seems to be forgotten as the mainframe eras transitioned their high-level/low-level languages away from say, Algol 55 (based on Backus-Naur), and so forth.

      I love this topic you have raised and I also love Tobais’ response.

      So, to answer your other questions, I really do not use method two as it relies on the compiler to produce more work for the layer in between the kernel and the hardware to perform more OPs: accumulate this, increment, decrement, swap registers, etc. This does not go without saying that I love this clever method as it shows that someone can actually read, understand, and adapt to inherited code, etc — a true professional and an observant individual, right?

      I am guilty of using temporary values, but as Tobais eluded to, for function/loop checking AND I USE THEM IN A MYOPIC FASHION. We have all seen code that is riddled with useless “place-holder” variables and it drives me nuts. My approach, is something to the sort (pardon the mock-code as I am trying to drive home the point)

      int checkSwap 0; // pseudo-boolean value
      int leftHand = 5;
      int rightHand = 6;

      checkSwap = leftHand;
      leftHand = rightHand;
      rightHand = checkSwap;
      checkSwap = 1; // a means to indicate the swap was done

      Naturally, logic would follow but I challenge us to code for this:

      Is there a language or a means with which we can do the swap without actually introducing more code than needed? Can we compile code as so a one-liner can be used to swap the register space for leftHand and rightHand variables?

      I have one answer, but rarely is the language used in seriousness (despite being compiled, etc) and the only hint for the cheap way out is Dartmouth.

      The game is afoot!

      Like

  2. >>When it isn’t just two pieces of data but a vast array of data perhaps representing a frame buffer or screen
    In that case I would suggest to swap the pointers to the “vast array of data”, if pointer already in register it’s one xch operation.

    Liked by 1 person

    1. Exactly! HLLs do this well. Even QBasic has a SWAP function for compiled/interpreted versions, but I may cook up a code to measure stack space and the swap routine as such to see if it differs from Rachel’s first method example!

      Like

    2. A little late responding, but I was trying to think of a good example (which I eluded to in a comment below). You are spot on with the pointer as earlier, BNF-based languages used literal indexing, so…

      MyArray[3] = “Joe”
      MyInt = 3

      If you tried to swap by literal 3, or “3”, the old compilers would blow up as MyInt would try to inherit not just the index for MyArray[3] = “Joe”, but entire array 😉

      Like

    3. well exactly…. I just can’t think of a realistic coding scenario where the “clever” method is of benefit… which makes me wonder why it seems to be on so many interview sites…

      Like

  3. As you already indicate, code readability is far more important (perhaps most important) than saving one variable (which is on stack anyway for local variables)

    Like

  4. Ha! XOR — nice call! What I recall from my Dad’s stack of Burroughs large/medium/other systems, was ALGOL. It had a swap function (much like the Burroughs MCP OS did), but it was even more cool as it was a call by name routine, so it could be used to test recursion! Man… the good old days!

    Like

  5. My youngest son has just started a compsci course at Sheffield and showed me what he’d done on his number square Java assignment a couple of weeks ago. He used method 2 for the swaps and I was interested and a bit surprised, as method 1 just seems so much more natural. Wonder where he got it from?

    Like

    1. well this is it… it’s clever and makes you think… but in practice why and when would you do this? There seem to be all these folks asking this as an interview question and I’m not sure why…. how did offspring tackle the problems with overflow?

      Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: