Thursday, December 29, 2011

Reverse a String using bits

Question: Reverse a string in C using as little additional memory as possible.

Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code.

Method 1 - Normal Reversal of String
void reverseString(char* str)
{
    int i, j;
    char temp;
    i=j=temp=0;

    j=strlen(str)-1;
    for (i=0; i<j; i++, j--)
    {
        temp=str[i];
        str[i]=str[j];
        str[j]=temp;
    }
}

Method 2 - Using xor to swap 2 characters
The second solution is slightly better than the first as it does not need the char space. It uses bitmanipulation (XOR in this case) to swap the chars in place.

void reverseStringBetter(char* str)
{
    int i, j;
    i=j=0;

    j=strlen(str)-1;
    for (i=0; i<j; i++, j--)
    {
        str[i] ^= str[j] ;
        str[j] ^= str[i] ;
        str[i] ^= str[j] ;
    }
}

Basically it is using swapping the 2 variables without using temporary variable.
Even though the second solution uses less space, the first one is probably a better solution in terms of readability and maintainability. The compilers are very advanced now and are able to reduce the swap instructions in the first solution into a single execution step. However, the same might not happen for the second solution so in real life situations, it is better to use the first solution although the second solution seems smarter and better theoretically.

0 comments:

Post a Comment