473,574 Members | 2,529 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Highly efficient string reversal code

Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!

int reverse(char* reverseme){
int retval=-1;
if(retval!=NULL ){
int len=strlen(retv al){
if(len>0){
int half=len>>1;
for(;retval<hal f;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];
reverseme[len-(retval+1)]=reverseme[retval];
reverseme[retval]^=reverseme[len-(retval+1)];
}
}
}
return retval;
}

-Phil/CERisE
Sep 22 '08
144 4906
Jens Stueckelberger <JS************ *@nowhere.orgwr ites:
On Mon, 22 Sep 2008 11:42:37 -0700, dominantubergee k wrote:
>Hello, I'm a highly experienced expert C programmer and I've written
this code to reverse a string in place. I think you could all learn
something from it!

Boy, that last sure is going to endear you to people here!
Suggesting people show new programmers pointers at work in a debugger
endears you to some of the dustier c.l.c dweller ... :-;
Sep 22 '08 #11

<dj******@csclu b.uwaterloo.ca. invalidwrote in message
news:gb******** **@rumours.uwat erloo.ca...
Since the subject has come up, here's one I've been waiting for an
excuse to post:
--------
typedef struct l{char a;struct l*b;}l;
static void x(char*a,l*b) {if(b){(-1)[a]=b->a;x(--a,b->b);}}
static void y(char*a,l*b,l* c)
{if(b){l*d=b->b;b->b=c;y(a,d,b);} else{x(a,c);}}
static void z(char*a,l*b) {if(*a){l
c;c.a=*a;c.b=b; z(a+1,&c);}else {y(a,b,0);}}
void reverse(char *s) { z(s,0); }
--------
Unlike the one that started the thread, this has actually been tested
and verified to work.

It also uses advanced implementation techniques that allow programs
with certain properties (especially in languages with properties that
make those program properties easy to detect and exploit) to be
compiled to highly efficient code.

Somebody who spends enough time untangling it might even learn
something useful from it (for sufficiently, but not comically, loose
values of "useful").
I tested your reverse function against the simplest reverse function of my
own I could knock up. Mine was 6 to 20 times faster that yours, to reverse a
77-character string one million times on my machine.

So if there is a point to your version, I haven't quite grasped it.

void myreverse(char *s) {
int i,j;
char c;

if (s==NULL) return;

j=strlen(s)-1;
i=0;

while (i<j) {
c=s[i];
s[i]=s[j];
s[j]=c;
++i;
--j;
}

}

--
Bartc

Sep 22 '08 #12
do************* *@ymail.com wrote:
>
Hello, I'm a highly experienced expert C programmer and I've
written this code to reverse a string in place. I think you could
all learn something from it!

int reverse(char* reverseme){
int retval=-1;
if(retval!=NULL ){
int len=strlen(retv al){
if(len>0){
int half=len>>1;
for(;retval<hal f;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];
reverseme[len-(retval+1)]=reverseme[retval];
reverseme[retval]^=reverseme[len-(retval+1)];
}
}
}
return retval;
}
This is so horrible and faulty that I have to attach the
following. Don't forget to #include <strings.h>. Note that it
returns strlen.

/* =============== ======== */
/* reverse string in place */
size_t revstring(char *stg)
{
char *last, temp;
size_t lgh;

lgh = strlen(stg);
if (lgh 1) {
last = stg + lgh; /* points to '\0' */
while (last-- stg) {
temp = *stg; *stg++ = *last; *last = temp;
}
}
return lgh;
} /* revstring */

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.
Sep 22 '08 #13
In article <9D************ ******@text.new s.virginmedia.c om>,
Bartc <bc@freeuk.comw rote:
>
<dj******@cscl ub.uwaterloo.ca .invalidwrote in message
news:gb******* ***@rumours.uwa terloo.ca...
>Since the subject has come up, here's one I've been waiting for an
excuse to post:
[...]
>I tested your reverse function against the simplest reverse function of my
own I could knock up. Mine was 6 to 20 times faster that yours, to reverse a
77-character string one million times on my machine.

So if there is a point to your version, I haven't quite grasped it.
I'd rather give my version to somebody who's posting an obvious
homework problem than yours.

Once you untangle it, it also demonstrates a few code-structure ideas
that are quite useful to have wrapped your brain around (not that
reversing a string in C is really a _good_ way to illustrate those),
and I like to think it provides a nifty example of how to build working
approximations to some high-level abstractions that C doesn't provide
natively.
dave
(specifically NOT claiming that "nifty" implies "useful in production code".)

--
Dave Vandervies dj3vande at eskimo dot com

None of my copies of K&R have a "screen". Should I apply for a refund?
--Chris Dollin in comp.lang.c
Sep 22 '08 #14
CBFalconer <cb********@yah oo.comwrites:
do************* *@ymail.com wrote:
>>
Hello, I'm a highly experienced expert C programmer and I've
written this code to reverse a string in place. I think you could
all learn something from it!

int reverse(char* reverseme){
int retval=-1;
if(retval!=NULL ){
int len=strlen(retv al){
if(len>0){
int half=len>>1;
for(;retval<hal f;retval++){
reverseme[retval]^=reverseme[len-(retval+1)];
reverseme[len-(retval+1)]=reverseme[retval];
reverseme[retval]^=reverseme[len-(retval+1)];
}
}
}
return retval;
}

This is so horrible and faulty that I have to attach the
following. Don't forget to #include <strings.h>. Note that it
returns strlen.

/* =============== ======== */
/* reverse string in place */
size_t revstring(char *stg)
{
char *last, temp;
size_t lgh;

lgh = strlen(stg);
if (lgh 1) {
last = stg + lgh; /* points to '\0' */
while (last-- stg) {
temp = *stg; *stg++ = *last; *last = temp;
}
}
return lgh;
} /* revstring */
You know I really had to look hard at this to understand it. Horrible
variables names almost purposely made "no standard" as far as C around
the world goes for such a function. Unnecessary length
check. Unnecessary size_t. Multiple assignments on one line
making perusal with a debugger almost impossible.

Much nicer IMO:

#include <string.h>

char * my_strrev(char *s){
char t;
char *e = s+strlen(s)-1;
while(e>s){
t = *s;
*s++ = *e;
*e-- = t;
}
}

I'm sure it breaks some sort of ISO magic, but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.
Sep 22 '08 #15
CBFalconer <cb********@yah oo.comwrites:
<snip code>
This is so horrible and faulty that I have to attach the
following. Don't forget to #include <strings.h>.
I'd include <string.hinstea d. I haven't seen strings.h for decades.

--
Ben.
Sep 22 '08 #16
Richard<rg****@ gmail.comwrites :
<snip>
Much nicer IMO:

#include <string.h>

char * my_strrev(char *s){
char t;
char *e = s+strlen(s)-1;
while(e>s){
t = *s;
*s++ = *e;
*e-- = t;
}
}

I'm sure it breaks some sort of ISO magic,
Not "magic" but it has undefined behaviour on empty strings.
but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.
Testing it would not reveal the issue.

--
Ben.
Sep 22 '08 #17
Ben Bacarisse <be********@bsb .me.ukwrites:
Richard<rg****@ gmail.comwrites :
<snip>
>Much nicer IMO:

#include <string.h>

char * my_strrev(char *s){
char t;
char *e = s+strlen(s)-1;
while(e>s){
t = *s;
*s++ = *e;
*e-- = t;
}
}

I'm sure it breaks some sort of ISO magic,

Not "magic" but it has undefined behaviour on empty strings.
>but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.

Testing it would not reveal the issue.
Why wouldn't it? (and I acknowledge the correction btw).

Had I run this through a debugger with s as an empty string (I must
admit I had assumed s had to be non null and a non empty string but fair
enough point you raise) I would spot it in about 1 second when e is
calculated.

But correction (still no null check):
#include <stdio.h>
#include <string.h>

char * my_strrev(char *s){
char t;
char *e = s+strlen(s);
while(e-->s){
t = *s;
*s++ = *e;
*e = t;
}
}

int main() {
char s1[]="hello";
my_strrev(s1);
printf("%s\n",s 1);
char s2[]="";
my_strrev(s2);
printf("%s\n",s 2);
char s3[]="c.l.c";
my_strrev(s3);
printf("%s\n",s 3);
}

Is that now defined? or, after a 14 hour day, am I talking rubbish here?

Can e not be decremented to a value "smaller" than s?

Sep 22 '08 #18
Richard wrote:
#include <string.h>

char * my_strrev(char *s){
char t;
char *e = s+strlen(s)-1;
while(e>s){
t = *s;
*s++ = *e;
*e-- = t;
}
}

I'm sure it breaks some sort of ISO magic, but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.
It's undefined when attempting to reverse a zero length string.

--
pete
Sep 22 '08 #19
pete <pf*****@mindsp ring.comwrites:
Richard wrote:
>#include <string.h>

char * my_strrev(char *s){
char t;
char *e = s+strlen(s)-1;
while(e>s){
t = *s;
*s++ = *e;
*e-- = t;
}
}

I'm sure it breaks some sort of ISO magic, but it seems more concise and
readable to me. No I didnt test it, but I guess the idea should be self
evident.

It's undefined when attempting to reverse a zero length string.
Yes, I acknowledged that in my reply to Ben. Careless of me.
Sep 22 '08 #20

This thread has been closed and replies have been disabled. Please start a new discussion.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.