This one ought to be simple. The logic is:
1. Get a pointer to the end.
2. Keep a temp pointer
3. Reverse the first and the last pointers
4. increment the pointer which is starting from the start and decrement the pointer from the end.
here goes:
void Reverse( char* pszString ) {
if( !pszString )
return;
char* pEnd = pszString;
while( *++pEnd ) {;}
//this goes beyond the end
--pEnd;
while( pszString < pEnd ) {
pTemp = *pszString;
*pszString++ = *pEnd;
*pEnd-- = pTemp;
}
}
The thing to note is that while testing the above if you call the function as
Reverse( L"myname" ), then it will not work and you will get first chance access violation on account of access denied. The reason is because such strings are stored in the read only area. So you might want to create a string on the heap using the new or the malloc and then call this function. The complexity of the above would be O(n) and no space complexity
By the way the same can be done recursively as well. However recursion will eat up stack. I will update this thread later with a recursive version as well soon.
1. Get a pointer to the end.
2. Keep a temp pointer
3. Reverse the first and the last pointers
4. increment the pointer which is starting from the start and decrement the pointer from the end.
here goes:
void Reverse( char* pszString ) {
if( !pszString )
return;
char* pEnd = pszString;
while( *++pEnd ) {;}
//this goes beyond the end
--pEnd;
while( pszString < pEnd ) {
pTemp = *pszString;
*pszString++ = *pEnd;
*pEnd-- = pTemp;
}
}
The thing to note is that while testing the above if you call the function as
Reverse( L"myname" ), then it will not work and you will get first chance access violation on account of access denied. The reason is because such strings are stored in the read only area. So you might want to create a string on the heap using the new or the malloc and then call this function. The complexity of the above would be O(n) and no space complexity
By the way the same can be done recursively as well. However recursion will eat up stack. I will update this thread later with a recursive version as well soon.
6 comments:
Using something like bstring, you can avoid the walk to the end of the list just to get the end pointer. It has an O(1) strlen.
And while we are optimizing, why not get rid of the temp variable for the swap ? The resulting arithmetic in the loop can make for really tight generated code :)
Thanks for the bstring tip. I looked it up and seems to be promising.
The temp variable can be removed probably by using the XOR based swap, however in the newer processor architectures,the XOR technique may be slower, as the newer CPUs strive to execute instructions simultaneously via instruction pipe-lining, and since the XOR based swap depends on the outcome of the previous operation, hence the CPU will need to execute them sequentially. Resulting in slower performance of the XOR based swap.
That being said, on platforms/architectures where RAM is at a premium (example micro-controllers) XOR based swap may be a better alternative. Anyways for the uninitiated, here is the XOR based algorithm for swapping:
void XORSwap( int* x, int* y ) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
Do you know any other way of swapping?
Better still:
void XORSwap( int* x, int* y ) {
if( x != y ) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
Addition/Subtraction can also be used to swap, but it will still
be sequential.
I didn't quite get your "RAM at a premium" consideration.
My justification for removing the temp variable was to not
eject the callsite from the current pipeline.
An example:
while (something) {
statement1;
Reverse(x);
statement2;
}
We would like the loop to be not "fetched" on every iteration,
and if Reverse is inlined, depending on how many instructions
it generates, it can cause this.
The Addition/subtraction logic is a good one. Good interview question:-)
void swap(int*x, int* y) {
if( *x != *y ) {
*x += *y;
*y = *x - *y;
*x = *x - *y;
}
}
However this might lead to integer overflow, if the sum of x and y becomes greater than INT_MAX, which is 32767.
Post a Comment