Reverse a string

[Sathyaish]

This one question is asked modally in most Microsoft interviews. I
started to contemplate various implementations for it. This was what I
got.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


char* StrReverse(char *);
char* StrReverse1(cha r*);
char* StrReverse2(cha r*);
void StrReverse3(cha r*);
void StrReverse4(cha r*);

int main(void)
{

char str[50];
int temp=0;

printf("Enter a string: ");
scanf("%s", str);
printf("The reverse of the string is: %s\n", StrReverse(str) );
printf("The reverse of the string is: %s\n", StrReverse1(str ));
printf("The reverse of the string is: %s\n", StrReverse2(str ));

StrReverse3(str );
printf("The reverse of the string is: %s\n", str);

//Get back the original string
StrReverse3(str );

//Reverse it again
printf("The reverse of the string is: ");
StrReverse4(str );
printf("\n");

scanf("%d", &temp);

}


char* StrReverse(char * str)
{
char *temp, *ptr;
int len, i;

temp=str;
for(len=0; *temp !='\0';temp++, len++);

ptr=malloc(size of(char)*(len+1 ));

for(i=len-1; i>=0; i--)
ptr[len-i-1]=str[i];

ptr[len]='\0';
return ptr;
}

char* StrReverse1(cha r* str)
{
char *temp, *ptr;
int len, i;

temp=str;
for(len=0; *temp !='\0';temp++, len++);

ptr=malloc(size of(char)*(len+1 ));

for(i=len-1; i>=0; i--)
*(ptr+len-i-1)=*(str+i);

*(ptr+len)='\0' ;
return ptr;
}

char* StrReverse2(cha r* str)
{
int i, j, len;
char temp;
char *ptr=NULL;
i=j=len=temp=0;

len=strlen(str) ;
ptr=malloc(size of(char)*(len+1 ));
ptr=strcpy(ptr, str);
for (i=0, j=len-1; i<=j; i++, j--)
{
temp=ptr[i];
ptr[i]=ptr[j];
ptr[j]=temp;
}
return ptr;
}

void StrReverse3(cha r* str)
{
int i, j, len;
char temp;
i=j=len=temp=0;

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



/*A coooooooooool way of reversing a string by recursion. I found it
at this web address

http://www.geocities.com/cyberkabila/datastructure/datastructuresright_reversestring.htm

*/

void StrReverse4(cha r *str)
{
if(*str)
{
StrReverse4(str +1);
putchar(*str);
}
}

Then, I read one guy saying a string could be reversed in one single
sweep with the exclusive OR operator. Since then I've been itching to
know how. If someone can please share with me, the code to reverse a
string with the XOR operator, I'll be grateful.

Regards,
Sathyaish

[Richard Harnden]

Re: Reverse a string

Sathyaish wrote:

[much snippage][color=blue]
>
> Then, I read one guy saying a string could be reversed in one single
> sweep with the exclusive OR operator. Since then I've been itching to
> know how. If someone can please share with me, the code to reverse a
> string with the XOR operator, I'll be grateful.
>[/color]

You can swap to chars, a and b, with:

*a ^= *b;
*b ^= *a;
*a ^= *b;

Worry about what happens in the middle of the string, when a and b have
the same address.

--
rh

[Julian V. Noble]

Re: Reverse a string

Sathyaish wrote:[color=blue]
>
> This one question is asked modally in most Microsoft interviews. I
> started to contemplate various implementations for it. This was what I
> got.
>[/color]
[color=blue]
>
> /*A coooooooooool way of reversing a string by recursion. I found it
> at this web address
> http://www.geocities.com/cyberkabila...ersestring.htm
> */
>
> void StrReverse4(cha r *str)
> {
> if(*str)
> {
> StrReverse4(str +1);
> putchar(*str);
> }
> }
>
> Then, I read one guy saying a string could be reversed in one single
> sweep with the exclusive OR operator. Since then I've been itching to
> know how. If someone can please share with me, the code to reverse a
> string with the XOR operator, I'll be grateful.
>
> Regards,
> Sathyaish[/color]

String reversal by recursion uses O(n^2) time. You can do it in O(n)
time by keeping pointers L and U to the ends. In pseudocode,

while L<U
swap( s[L], s[U] );
L = L+1;
U = U-1;
repeat


--
Julian V. Noble
Professor Emeritus of Physics
jvn@lessspamfor mother.virginia .edu
^^^^^^^^^^^^^^^ ^^^

http://galileo.phys.virginia.edu/~jvn/

"For there was never yet philosopher that could endure the toothache
patiently." -- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.

[Arthur J. O'Dwyer]

Re: Reverse a string


On Wed, 21 Jul 2004, Julian V. Noble wrote:[color=blue]
>
> Sathyaish wrote:[color=green]
> > /*A coooooooooool way of reversing a string by recursion. I found it
> > at this web address
> > http://www.geocities.com/cyberkabila...ersestring.htm
> > */
> >
> > void StrReverse4(cha r *str)
> > {
> > if(*str)
> > {
> > StrReverse4(str +1);
> > putchar(*str);
> > }
> > }[/color]
>
> String reversal by recursion uses O(n^2) time.[/color]

Not the way Sathyaish is doing it; that's O(n) right there (even
though it prints out something, rather than reversing the string).
[color=blue]
> You can do it in O(n)
> time by keeping pointers L and U to the ends. In pseudocode,
>
> while L<U
> swap( s[L], s[U] );
> L = L+1;
> U = U-1;
> repeat[/color]

Or, transforming the loop into tail-recursion,

void revmem(char *s, int L, int U)
{
if (L < U) {
swap(s[L], s[U-1]);
revmem(s, L+1, U-1);
}
}

(Note the change in meaning of U. :)

[color=blue][color=green]
> > Then, I read one guy saying a string could be reversed in one single
> > sweep with the exclusive OR operator. Since then I've been itching to
> > know how. If someone can please share with me, the code to reverse a
> > string with the XOR operator, I'll be grateful.[/color][/color]

The guy was probably thinking of the old chestnut

x ^= y ^= x ^= y;

which is not only invalid C code, but doesn't work if &x == &y.
And that just swaps two values (assuming it does what the guy obviously
expected it to do); while swapping is a big part of string reversal,
it's not exactly the same thing. And it has nothing to do with
"sweeps."

-Arthur

[Wayne Rasmussen]

Re: Reverse a string



Sathyaish wrote:
[color=blue]
> This one question is asked modally in most Microsoft interviews. I
> started to contemplate various implementations for it. This was what I
> got.
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> char* StrReverse(char *);
> char* StrReverse1(cha r*);
> char* StrReverse2(cha r*);
> void StrReverse3(cha r*);
> void StrReverse4(cha r*);
>
> int main(void)
> {
>
> char str[50];
> int temp=0;
>
> printf("Enter a string: ");
> scanf("%s", str);
> printf("The reverse of the string is: %s\n", StrReverse(str) );
> printf("The reverse of the string is: %s\n", StrReverse1(str ));
> printf("The reverse of the string is: %s\n", StrReverse2(str ));
>
> StrReverse3(str );
> printf("The reverse of the string is: %s\n", str);
>
> //Get back the original string
> StrReverse3(str );
>
> //Reverse it again
> printf("The reverse of the string is: ");
> StrReverse4(str );
> printf("\n");
>
> scanf("%d", &temp);
>
> }
>
> char* StrReverse(char * str)
> {
> char *temp, *ptr;
> int len, i;
>
> temp=str;
> for(len=0; *temp !='\0';temp++, len++);
>
> ptr=malloc(size of(char)*(len+1 ));
>
> for(i=len-1; i>=0; i--)
> ptr[len-i-1]=str[i];
>
> ptr[len]='\0';
> return ptr;
> }
>
> char* StrReverse1(cha r* str)
> {
> char *temp, *ptr;
> int len, i;
>
> temp=str;
> for(len=0; *temp !='\0';temp++, len++);
>
> ptr=malloc(size of(char)*(len+1 ));
>
> for(i=len-1; i>=0; i--)
> *(ptr+len-i-1)=*(str+i);
>
> *(ptr+len)='\0' ;
> return ptr;
> }
>
> char* StrReverse2(cha r* str)
> {
> int i, j, len;
> char temp;
> char *ptr=NULL;
> i=j=len=temp=0;
>
> len=strlen(str) ;
> ptr=malloc(size of(char)*(len+1 ));
> ptr=strcpy(ptr, str);
> for (i=0, j=len-1; i<=j; i++, j--)
> {
> temp=ptr[i];
> ptr[i]=ptr[j];
> ptr[j]=temp;
> }
> return ptr;
> }
>
> void StrReverse3(cha r* str)
> {
> int i, j, len;
> char temp;
> i=j=len=temp=0;
>
> len=strlen(str) ;
> for (i=0, j=len-1; i<=j; i++, j--)
> {
> temp=str[i];
> str[i]=str[j];
> str[j]=temp;
> }
> }
>
> /*A coooooooooool way of reversing a string by recursion. I found it
> at this web address
> http://www.geocities.com/cyberkabila...ersestring.htm
> */
>
> void StrReverse4(cha r *str)
> {
> if(*str)
> {
> StrReverse4(str +1);
> putchar(*str);
> }
> }
>
> Then, I read one guy saying a string could be reversed in one single
> sweep with the exclusive OR operator. Since then I've been itching to
> know how. If someone can please share with me, the code to reverse a
> string with the XOR operator, I'll be grateful.
>
> Regards,
> Sathyaish[/color]

What's wrong with the good old push/pop stack method of string reversal?

[pete]

Re: Reverse a string

Sathyaish wrote:
[color=blue]
> void StrReverse3(cha r* str)
> {
> int i, j, len;
> char temp;
> i=j=len=temp=0;
>
> len=strlen(str) ;
> for (i=0, j=len-1; i<=j; i++, j--)
> {
> temp=str[i];
> str[i]=str[j];
> str[j]=temp;
> }
> }[/color]

Here's a pointier version of the same algorithm:

char *str_rev(char *s)
{
char *p, *q, swap;

if (*s != '\0') {
q = p = s;
q += strlen(q);
while (--q > p) {
swap = *q;
*q = *p;
*p++ = swap;
}
}
return s;
}

--
pete

[Martin Ambuhl]

Re: Reverse a string

Richard Harnden wrote:
[color=blue]
> You can swap to chars, a and b, with:[/color]

[stupid XOR trick removed]
NEVER post this crap in answer to a question unless the question is
"What is the most frequent stupidity posted to a C newsgroup."

[Sam Halliday]

Re: Reverse a string

Richard Harnden wrote:[color=blue]
> You can swap to chars, a and b, with:
>
> *a ^= *b;
> *b ^= *a;
> *a ^= *b;[/color]

aah, the crazily named "stupid XOR trick"
[color=blue]
> Worry about what happens in the middle of the string, when a and b have
> the same address.[/color]

theoretically, it should just waste a few cpu cycles, but do nothing. if you
abstract yourself from C for a second and think about XOR as being an
associative (i think it is also commutative) binary operation (in the
mathematical sense) with the identity element 1. and using the following rule:

x XOR x = 1

then you can look at your code in the following manner. let a_1, b_1 be the
initial registers a and b. let a_2. b_2 be their final states. by following the
code through, we have the following equalities (brackets not needed due to
associativity, but left in for clarity with the order of the code):

b_2 = (a_1 XOR b_1) XOR b_1
a_2 = ((a_1 XOR b_1) XOR b_1) XOR (a_1 XOR b_1)

using the rule, we get

b_2 = a_1
a_2 = b_1

there is no theoretical reason why you cannot have (a_1 = b_1). in fact, i'd be
very worried if this broke, as it means the C XOR operator is not associative!

this method, although IMHO a cute little trick (and not stupid like most people
say) is actually slower than the more obvious way on most modern optimising
compilers) try the following code:

int a, b;
#ifndef STUPID_XOR
int tmp;
tmp = a;
a = b;
b = tmp;
#else
a ^= b;
b ^= a;
a ^= b;
#endif

and see what your C compiler outputs in assembly to see what i mean. or you
could just make up a simple C program to time a million string reverses using
each algorithm. on my G4 PPC, the "stupid XOR trick" takes about 140% as long as
the obvious solution, with the following assembly created for each:

obvious solution:
stwu 1,-48(1)
stw 31,44(1)
mr 31,1
lwz 0,8(31)
stw 0,16(31)
lwz 0,12(31)
stw 0,8(31)
lwz 0,16(31)
stw 0,12(31)
lwz 11,0(1)
lwz 31,-4(11)
mr 1,11
blr

"stupid XOR trick":
stwu 1,-32(1)
stw 31,28(1)
mr 31,1
lwz 9,8(31)
lwz 0,12(31)
xor 0,9,0
stw 0,8(31)
lwz 9,12(31)
lwz 0,8(31)
xor 0,9,0
stw 0,12(31)
lwz 9,8(31)
lwz 0,12(31)
xor 0,9,0
stw 0,8(31)
lwz 11,0(1)
lwz 31,-4(11)
mr 1,11
blr

[pete]

Re: Reverse a string

Sam Halliday wrote:[color=blue]
>
> Richard Harnden wrote:[color=green]
> > You can swap to chars, a and b, with:
> >
> > *a ^= *b;
> > *b ^= *a;
> > *a ^= *b;[/color]
>
> aah, the crazily named "stupid XOR trick"
>[color=green]
> > Worry about what happens in the middle of the string,
> > when a and b have the same address.[/color]
>
> theoretically, it should just waste a few cpu cycles,
> but do nothing. if you abstract yourself from C for a
> second and think about XOR as being an
> associative (i think it is also commutative) binary operation (in the
> mathematical sense) with the identity element 1.
> and using the following rule:
>
> x XOR x = 1[/color]

That's the opposite of what XOR means.

The result of an XOR operation is 1,
when the operands are logically different and

the result of an XOR operation is 0,
when the operands are logically the same.

--
pete

[Sam Halliday]

Re: Reverse a string

pete wrote:[color=blue]
> Sam Halliday wrote:[color=green]
> >
> > Richard Harnden wrote:[color=darkred]
> > > You can swap to chars, a and b, with:
> > >
> > > *a ^= *b;
> > > *b ^= *a;
> > > *a ^= *b;[/color]
> >
> > aah, the crazily named "stupid XOR trick"
> >[color=darkred]
> > > Worry about what happens in the middle of the string,
> > > when a and b have the same address.[/color]
> >
> > theoretically, it should just waste a few cpu cycles,
> > but do nothing. if you abstract yourself from C for a
> > second and think about XOR as being an
> > associative (i think it is also commutative) binary operation (in the
> > mathematical sense) with the identity element 1.
> > and using the following rule:
> >
> > x XOR x = 1[/color]
>
> That's the opposite of what XOR means.[/color]

no is not... here 1 means "the identity"; the identity acted on anything does
nothing. everything i wrote is abstrated to mathematics. in fact you do not even
need to know *what* XOR does to understand why the "stupid CXOR trick" works.

[Sam Halliday]

Re: Reverse a string

Sam Halliday wrote:[color=blue]
> there is no theoretical reason why you cannot have (a_1 = b_1). in fact, i'd
> be very worried if this broke, as it means the C XOR operator is not
> associative![/color]

hold on... brain freeze. there is no reason why you cannot have (a_1 = b_1), but
the problem is when they share the same address (&a_1 = &b_1). in that case,
things would break and we would be left with the identity 1... which is all
zeros.

[Arthur J. O'Dwyer]

Re: Reverse a string


On Thu, 22 Jul 2004, Sam Halliday wrote:[color=blue]
>
> Sam Halliday wrote:[color=green]
> > there is no theoretical reason why you cannot have (a_1 = b_1). in fact, i'd
> > be very worried if this broke, as it means the C XOR operator is not
> > associative![/color]
>
> hold on... brain freeze. there is no reason why you cannot have (a_1 = b_1),
> but the problem is when they share the same address (&a_1 = &b_1). in that
> case, things would break and we would be left with the identity 1... which
> is all zeros.[/color]

Your lines are a little long; 75 characters, please. And I hope you're
not going to keep using your own personal terminology in which "the
identity 1" is "all zeros." That's just going to confuse and annoy
people. Better use the term "1" to mean "the number 1," which to a
computer person is about as far from "zero" as you can get.

A programmer would have said,

x XOR x = 0

which is absolutely correct, no matter if we're talking bits or
bytes or long-leggedy beasties. x XOR x is always zero.

-Arthur,
one-bit mind

[Sam Halliday]

Re: Reverse a string

Arthur J. O'Dwyer wrote:[color=blue]
> Your lines are a little long; 75 characters, please.[/color]

its generally personal preference. on todays modern screens, i find 82 is much
better. if you have a problem with line wrapping, fix it at your end; most good
email clients are advanced enough to pre-process emails in this fashion. i just
live with it. lets face it... no matter how anyone formats their mail, it will
annoy somebody.
[color=blue]
> And I hope you're
> not going to keep using your own personal terminology in which "the
> identity 1" is "all zeros." That's just going to confuse and annoy
> people.[/color]

yes, perhaps i should have used 'i' to mean the identity. in mathematics, it is
quite common to use 1 to mean the identity. 0 would generally be the null set;
and it is good practise to separate them as they are not always the same. it is
hardly "my own personal terminology"... perhaps foreign to most programmers,
admittedly.
[color=blue]
> Better use the term "1" to mean "the number 1," which to a
> computer person is about as far from "zero" as you can get.
>
> A programmer would have said,
>
> x XOR x = 0
>
> which is absolutely correct, no matter if we're talking bits or
> bytes or long-leggedy beasties. x XOR x is always zero.[/color]

my point was that you can understand why the "stupid XOR trick" works without
even needing to know what XOR does... just a little about its algebra. in doing
that, it is best to abstract away from 1s and 0s altogether. but, i still should
have used a symbol rather than 1 (or 0) to represent the identity.

[Alan Balmer]

Re: Reverse a string

On Thu, 22 Jul 2004 15:19:21 +0100, Sam Halliday <email@example. com>
wrote:
[color=blue]
>Arthur J. O'Dwyer wrote:[color=green]
>> Your lines are a little long; 75 characters, please.[/color]
>
>its generally personal preference. on todays modern screens, i find 82 is much
>better. if you have a problem with line wrapping, fix it at your end; most good
>email clients are advanced enough to pre-process emails in this fashion. i just
>live with it. lets face it... no matter how anyone formats their mail, it will
>annoy somebody.[/color]

Not likely. If you follow the conventions, no one will object. While
we're critiquing you posting style, please get a keyboard with a
working shift key.

--
Al Balmer
Balmer Consulting
removebalmercon sultingthis@att .net

[Dan Pop]

Re: Reverse a string

In <20040722151921 .78978932@noss> Sam Halliday <email@example. com> writes:
[color=blue]
>Arthur J. O'Dwyer wrote:[color=green]
>> Your lines are a little long; 75 characters, please.[/color]
>
>its generally personal preference.[/color]

Bullshit: it's basic Usenet netiquette.
[color=blue]
>on todays modern screens, i find 82 is much better.[/color]

And someone with a larger screen than yours might find 150 much better.
The point is that most alphanumeric terminals are still 80 columns and
some people are still using them, for reasons of their own.
[color=blue]
>if you have a problem with line wrapping, fix it at your end;[/color]

A text line that doesn't fit on a terminal line can't be fixed at the
receiver end: there is no way to compress it to fit. And posts with
wrapped around lines are ugly and less readable.
[color=blue]
>most good
>email clients are advanced enough to pre-process emails in this fashion.[/color]

In your stupidity, you have failed to realise that this is not a mailing
list. What email clients do or don't is entirely irrelevant to Usenet.

The last thing you'd want a Usenet client to do is to reformat a
"paragraph" containing C source code.
[color=blue]
>i just
>live with it. lets face it... no matter how anyone formats their mail, it will
>annoy somebody.[/color]

It doesn't matter, as long as the lines do not exceed 72-75 characters and
are not ludicrously narrow. And, again, we're not talking about mail,
but this aspect seems to be above your understanding capabilities.

If your badly formatted posts don't have some other redeeming quality
(and they don't, unless you consider a combination of arrogance and
stupidity as redeeming quality ;-) most people will start ignoring you
completely.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de