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(char*);
char* StrReverse2(char*);
void StrReverse3(char*);
void StrReverse4(char*);

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(sizeof(char)*(len+1));

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

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

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

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

ptr=malloc(sizeof(char)*(len+1));

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

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

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

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

void StrReverse3(char* 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;
str=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(char *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]

Sathyaish wrote:

[much snippage]

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.

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.

 

[Julian V. Noble]

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

/*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(char *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

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 );
L = L+1;
U = U-1;
repeat


--
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
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]

String reversal by recursion uses O(n^2) time.

Not the way Sathyaish is doing it; that's O(n) right there (even
though it prints out something, rather than reversing the string).

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 );
L = L+1;
U = U-1;
repeat

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.


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]

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(char*);
char* StrReverse2(char*);
void StrReverse3(char*);
void StrReverse4(char*);

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(sizeof(char)*(len+1));

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

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

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

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

ptr=malloc(sizeof(char)*(len+1));

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

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

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

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

void StrReverse3(char* 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;
str=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(char *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

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

 

[pete]

Sathyaish wrote:

void StrReverse3(char* 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;
str=str[j];
str[j]=temp;
}
}

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;
}

 

[Martin Ambuhl]

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

[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]

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

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

aah, the crazily named "stupid XOR trick"

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

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]

aah, the crazily named "stupid XOR trick"


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

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.

 

[Sam Halliday]

That's the opposite of what XOR means.

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]

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!

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]

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.

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]

Your lines are a little long; 75 characters, please.

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.

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.

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.

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.

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.

 

[Dan Pop]

its generally personal preference.

Bullshit: it's basic Usenet netiquette.

on todays modern screens, i find 82 is much better.

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.

if you have a problem with line wrapping, fix it at your end;

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.

most good
email clients are advanced enough to pre-process emails in this fashion.

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.

i just
live with it. lets face it... no matter how anyone formats their mail, it will
annoy somebody.

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

 

[Alan Balmer]

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.

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.

 

[Default User]

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.

Many people still use 80 width screens. Even though I use a windows
reader on a large screen, I still have the courtesy to set my outgoing
width to 72. This provides room for some reasonable quoting without
screwing up other people for no good reason.

Is it your goal to become irrelevant on this newsgroup?




Brian Rodenborn

 

[Sam Halliday]

Dan Pop wrote:
[flame flame flame]

dan, shut up and stop turning every thread into a flamewar. get back on topic...
which was a discussion about the "stupid XOR trick" and reversing of a string.
if it hasn't already ended.

jesus... if this is what you're like to your peers, i'd hate to think what
computer users at DESY think of you... i'm sure you cause more frustration than
you fix.

 

[Ben Pfaff]

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;

Perhaps this is a disagreement over fonts. I haven't often seen
zero used as the null set, but a zero with a slash through it is
common. Which one appears as "0" on your screen depends on your
font.

 

[Sam Halliday]

Perhaps this is a disagreement over fonts. I haven't often seen
zero used as the null set, but a zero with a slash through it is
common. Which one appears as "0" on your screen depends on your
font.

i believe you are correct... and also; it is not really 1 for the identity,
but a "blackboard 1". its a 1 but has 2, very close, vertical lines. i
believe you can get it by using \bbmath{1} in LaTeX. neither seem to be in
the iso-8859-15 character set anyway. maths is always difficult to portray
correctly in plain text.

 

[Keith Thompson]

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.

You'll annoy all of the people some of the time, and some of the
people all of the time -- but if you continue posting 82-column text,
you'll annoy all of the people all of the time.

Ok, that's a slight exaggeration, but trust me on this. Many, perhaps
most, Usenet users use a terminal or emulator configured to display 80
columns, simply because of long tradition. Most, perhaps all, Usenet
client programs do not automatically reformat text to fit the window;
if they did, sample code would become illegible (and I frankly don't
want my newsreader to be smart enough to tell the difference).

If you keep your lines down to 72 to 75 columns, your articles will be
significantly easier to read. Persistently failing to do so is
considered rude. (You might also consider using the occasional upper
case letter, but that's not nearly as annoying as the long lines.)

A quick look at groups.google.com indicates that you're fairly new
here, so I can understand your not knowing all this before -- but now
you do.

Speaking of rudeness, I see you've been the recipient of some abuse in
this thread. I recommend ignoring the abuse, though the technical
points in that response are basically correct.

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.

Since C already has an extremely well-defined meaning for the symbol 1,
it seems ill-advised to use it to refer to something else.