Friday, April 17, 2009

what reversing strings can teach us...

Reversing a string is almost a standard interview question for internships and other jobs requiring programming. What is interesting is that there are many ways to reverse a string, which we will look at below. The answer to which method is the best reveals an interesting lesson in computer science.

Alrighty, so you have your scripting languages that make it mind numbingly easy to reverse a string, in Python the answer is simply mystring[::-1] and voila, string reversed. Probably the most standard way in C++ is to simply make a temp array and iterate through your string, putting each letter from the back to the front in your temp array. This is a satisfactory answer, but it won't win you any brownie points either. The shortest code in C would have to use recursion.

# include

void recurs_string(char * );

/* Definition of the recurs_string() function */

void recurs_string(char *string)

if (*string)

void main(void)
char str[100];
printf("\n Input a string: ");
printf("\n Reverse of the string: %s", str);
printf("\n Reverse string is: ");

(I got this from here, because I am too lazy to write my own)

While recursion may l
ook impressive, it uses a lot of stack, so it really isn't the best way either. The best way to reverse a string is below.

public string Reverse(string str)
// convert the string to char array
char[] charArray = str.ToCharArray();
int len = str.Length - 1;
for (int i = 0; i < len; i++, len--) {
charArray[i] ^= charArray[len];
charArray[len] ^= charArray[i];
charArray[i] ^= charArray[len];
return new string(charArray); }
Now if you are
me when you saw this code you were like "what the heck is '^=' ?" that happens to be the XOR (exclusive OR) operator. XOR is a logic operator that returns a one if only one of the two input s is a one. for example 1 XOR 0 = 1, 0 XOR 1 = 1, but 1 XOR 1 = 0. Why this is useful is that XORing two elements three times performs a bitwise switch of those two elements, lets take a look.

XOR 0111010

= 1011111
XOR 0111010

= 1100101

So you can see, performing XOR operations on two individual characters actually switches there values. This has a practical learning application. Sometimes, the best implementation of a solution can be achieved using low-level logic operations, such as arithmetic shifts, bitwise logic operatiors such as AND, OR, XOR, etc. and binary addition and subtraction. keep this in mind the next time you are trying to optimize your code (and make yourself king of the geeks by writing something that is faster than everybody elses code, and only you can understand.)

Related Posts :

No comments:

Post a Comment