In-place swap

Write a function to swap a number in place without temporary variables.

My initial thoughts:
Before swap, ‘a’ points to number a and ‘b’ points to number b.

  1. ‘a’ points to ‘a’ – ‘b’, which is a - b.
  2. ‘b’ points to ‘b’ + ‘a’, which is b + (a - b) = a.
  3. ‘a’ points to ‘b’ – ‘a’, which is a - (a - b) = b.

My initial codes:

void swap(int & a, int & b) {
	a = a - b;
	b = b + a;
	a = b - a;
}

Solution:

void swap(int & a, int & b) {
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}

Comments:
^ is the exclusive-OR operator:

  • 0^0=0
  • 0^1=1
  • 1^0=1
  • 1^1=0

Hence, we have:

  1. a=a^b: ‘a’ will save all the bits that a differs from b: if the bit that ‘a’ and ‘b’ differ, it gets 1, otherwise 0.
  2. b=a^b: ‘b’ will compare to the difference between a and b: for the bit that ‘b’ and ‘a’ differ, it means a have 1 at this position and the result of a^b will assign that bit to 1; for the bit that ‘b’ and ‘a’ agree, it means a have 0 at this position and the result of a^b will assign that bit to 0.
  3. a=a^b: Same logic.
Advertisements

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

%d bloggers like this: