Most optimized way to reverse a string?

[melwyn]

Hi, Can someone write a function that reverses a string in the most optimized manner? meaning it should use as few variables, loops etc as possible.

[Anonymous]

Why dont you try urself....??

[melwyn]

This is what I got char *start = string; char *left = string; char ch; while (*string++); string -= 2; while (left < string) { ch = *left; *left++ = *string; *string-- = ch; } return(start); Now what do u have???

[Ian Darling]

No temps in reverseString at all, and only one loop which goes halfway along the string. It is an in-place reverse, so it overwrites whats there. If I was feeling really keen I could turn it into a template too :-D #include <iostream> #include <cstdio> using namespace std; void reverseString(char *str, const int &len) {  for(int i=0; i<(len-1)-i; ++i)   str[i] ^= str[(len-1)-i] ^= str[i] ^= str[(len-1)-i]; } int main() {  char str[] = "String to reverse!";  int len = strlen(str);  // in place reverse  cout << str << endl;  reverseString(str, len);  cout << str << endl;  return 0; } -- Ian Darling "The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky

[Mike Dimmick]

So, what's wrong with std::reverse? The compiler's supplied library is usually pretty well optimised for the task in hand. In the general case, forget about trying to eliminate variables, loops etc in your code. The compiler can do that when it optimises - unrolling loops, enregistering variables, removing common terms. Compile your code in release mode for a simple implementation, then see what the compiler did with it. Shortest C++ code is not necessarily shortest or fastest object code. So, the best optimised code is probably

void ReverseString( char* sz, size_t len )
{
char ch;

for ( size_t idx = 0; idx < len / 2; ++idx )
{
ch = sz[idx];
sz[idx] = sz[len - idx - 1];
sz[len - idx - 1] = ch;
}
}

The compiler hoists the division of len by 2 out of the loop (and also converts it to a right-shift by 1). It also converts the sz[len - idx - 1] terms into a pointer and moves it back down from the end. Finally, it uses the dl register (the least significant byte of edx to store ch, which is never stored to main memory. Stick to simple code.

[Obliterator]

My guess would be this is what the lecturer is looking for too ;P -- The Obliterator

[melwyn]

Thank you for your comments. I agree with you that code should be simple, atleast for maintenance purposes.

[n 0]

__inline char *StrRev(char *Source, char *Dest) { char *p = strchr(Source, '\0'), *p2 = Dest; while( --p >= Source ) *p2++ = *p; *p2 = '\0'; return Dest; }; Phil

[melwyn]

Nice. :) Actually the initial problem required the original string to be reversed (which i forgot to mention). I have used your nice logic to modify my function :-) void Reverse(char *src) { char *p = strchr(src, '\0') - 1; while (src < p) { *src ^= *p ^= *src ^= *p; src++; p--; } } -Melwyn