reverse a string with 0 terminator in one pass

[joecook]

dbtouch wrote:
In other words, under the more-or-less strict interpretation of the
terms you used in the statement of your problem, it has no solution. You
need to clarify what is really needed.

I disagree. I think the solution is obvious. Here is an example of
reversing a string using no auxillary memory at all (no recursion, no
temporaries). I use the Null terminator location as my swap space.

In fact, I do have a loop temporary, but you could easily conceive
this could be eliminated using templates, and a compile time constant
size (this doesn't not violate any of the conditions set forth).

Also, this is only the half that works for even-length strings. I'll
leave the odd lengths as an exercise to the reader.

I only "walk" through the string one time

void reverse(char* input, int size) // size does not include the null
terminator
{
// Walk through the first half.
for(int i=0; i<size/2; ++i)
{
input[size-1] = input;
intput = input[size-i-1];
}
// Walk through the rest
for(int i=size/2+1; i<size; ++i)
{
input = input[i+1];
}
input[size] = "\0"; // restore the null terminator
}

int main()
{
char a[] = "Hello!";
reverse(a,6);
}

Joe Cook

 

[joecook]

  input[size] = "\0"; // restore the null terminator

Oops, make that '\0';

Also, there is a way to do this same algorithm without a compile time
constant, and also no loop variables, but it's a bit a longer to type
out...

joe Cook

 

[joecook]

  input[size] = "\0"; // restore the null terminator

Oops, make that '\0';

Also, there is a way to do this same algorithm without a compile time
constant, and also no loop variables, but it's a bit a longer to type
out...

The OP specifically stated that getting the length (actually strlen, but
he clearly meant "getting the length") counted as a pass.  If you start
with the length as a given, you're cheating.

Fine Fine, just change the "reverse" definition to a template
template<std::size_t size>
void reverse(char (&input)[size])
{
....
}

Using the compiler to tell you the size certainly can't be considered
"a pass", or this is really getting to be a silly question. Next
we'll be asked to write a program telling us if a passed string is of
finite length.

Joe Cook

 

[Sana]

dbtouch wrote:
In other words, under the more-or-less strict interpretation of the
terms you used in the statement of your problem, it has no solution. You
need to clarify what is really needed.

I disagree.  I think the solution is obvious.  Here is an example of
reversing a string using no auxillary memory at all (no recursion, no
temporaries).  I use the Null terminator location as my swap space.
In fact, I do have a loop temporary [...] and a compile time constant
size (this doesn't not violate any of the conditions set forth)

I disagree. The presence of the compile time "size" variable violates
the initial conditions. The OP does not know the length of the string
at compile time. That is why he mentions "to reverse a string with 0
terminator in one pass without using auxillary memory" and "if you use
strlen, it will be considered as one pass" which implies that the
length of the string is given by the position of the '\0' character.

 

[dbtouch]

How do you find out the length?

dbtouch wrote:
In other words, under the more-or-less strict interpretation of the
terms you used in the statement of your problem, it has no solution. You
need to clarify what is really needed.

I disagree.  I think the solution is obvious.  Here is an example of
reversing a string using no auxillary memory at all (no recursion, no
temporaries).  I use the Null terminator location as my swap space.

In fact, I do have a loop temporary, but you could easily conceive
this could be eliminated using templates, and a compile time constant
size (this doesn't not violate any of the conditions set forth).

Also, this is only the half that works for even-length strings.  I'll
leave the odd lengths as an exercise to the reader.

I only "walk" through the string one time

void reverse(char* input, int size) // size does not include the null
terminator
{
  // Walk through the first half.
  for(int i=0; i<size/2; ++i)
  {
  input[size-1] = input;
  intput = input[size-i-1];
  }
   // Walk through the rest
  for(int i=size/2+1; i<size; ++i)
  {
  input = input[i+1];
  }
  input[size] = "\0"; // restore the null terminator

}

int main()
{
char a[] = "Hello!";
reverse(a,6);

}

Joe Cook

 

[James Kanze]

template<std::size_t size>
void reverse(char (&input)[size])
Using the compiler to tell you the size certainly can't be considered
"a pass", or this is really getting to be a silly question.

The point was that you don't know the length ahead of time.
He also didn't have a character array, only a char*.

That's an easy one, unless you need the answer in finite time.

It's easier than that, it can be done in constant time:

bool
hasFiniteLength( char const* string )
{
return true ;
}

This will fail, of course, the day machines start having
infinite memory, but for the moment, we're safe.

 

[Pascal J. Bourguignon]

Using the compiler to tell you the size certainly can't be considered
"a pass", or this is really getting to be a silly question.

Of course, it is considered a pass. The specifications didn't says
that passes computed in the programmer brain ("hello!",6), or by the
compiler were allowed, they said that only one pass was to be used.

Indeed, it is a silly question.

 

[Pascal J. Bourguignon]

template<std::size_t size>
void reverse(char (&input)[size])
Using the compiler to tell you the size certainly can't be considered
"a pass", or this is really getting to be a silly question.

The point was that you don't know the length ahead of time.
He also didn't have a character array, only a char*.

That's an easy one, unless you need the answer in finite time.

It's easier than that, it can be done in constant time:

bool
hasFiniteLength( char const* string )
{
return true ;
}

This will fail, of course, the day machines start having
infinite memory, but for the moment, we're safe.

Once again, it depends on how you define the length of string. For
char* strings, the length is the distance between strings and the
first null byte. If there is no null byte in the memory (improbable,
but possible), strlen could loop forever, unless it's specifically
programmed to detect loop over. In anycase, this could be considered
as an infinite length string.

 

[Pascal J. Bourguignon]

(e-mail address removed) wrote:
template<std::size_t size>
void reverse(char (&input)[size])
Using the compiler to tell you the size certainly can't be considered
"a pass", or this is really getting to be a silly question.
The point was that you don't know the length ahead of time.
He also didn't have a character array, only a char*.
Next we'll be asked to write a program telling us if a
passed string is of finite length.
That's an easy one, unless you need the answer in finite time.
It's easier than that, it can be done in constant time:

bool
hasFiniteLength( char const* string )
{
return true ;
}

This will fail, of course, the day machines start having
infinite memory, but for the moment, we're safe.

Once again, it depends on how you define the length of string. For
char* strings, the length is the distance between strings and the
first null byte. If there is no null byte in the memory (improbable,
but possible), strlen could loop forever, unless it's specifically
programmed to detect loop over. In anycase, this could be considered
as an infinite length string.

How could that code be written in standard C++? If it covers the
whole address space, it eventually must dereference null.

Good point!

Using pointers, it cannot be done in standard C, or standard C++, but
it can be done on most implementations.

 

[James Kanze]

(e-mail address removed) wrote:
template<std::size_t size>
void reverse(char (&input)[size])
Using the compiler to tell you the size certainly can't
be considered "a pass", or this is really getting to be a
silly question.
The point was that you don't know the length ahead of time.
He also didn't have a character array, only a char*.
Next we'll be asked to write a program telling us if a
passed string is of finite length.
That's an easy one, unless you need the answer in finite time.

It's easier than that, it can be done in constant time:
bool
hasFiniteLength( char const* string )
{
return true ;
}
This will fail, of course, the day machines start having
infinite memory, but for the moment, we're safe.

Once again, it depends on how you define the length of string.

Or rather, how you define a string. In the C standard, a string
is a '\0' terminated sequence of characters. If the pointer you
pass doesn't point to a '\0' terminated sequence of characters,
you haven't fulfilled a very essential pre-condtion: pass a
string to the function. Most (all?) of the functions in the C
standard which takes such strings have undefined behavior if you
violate the pre-condition.

For char* strings, the length is the distance between strings
and the first null byte. If there is no null byte in the
memory (improbable, but possible),

Then you haven't passed a string, and the behavior is undefined.
Returning true is a valid undefined behavior (as is crashing).

strlen could loop forever, unless it's specifically programmed
to detect loop over. In anycase, this could be considered as
an infinite length string.

Not according to the C standard.

(And of course, there should be a lot of smileys on this and on
my comment to which Pascal is replying. It seemed obvious
enough to me that I was being facetious in my original posting,
but maybe not.)

 

[James Kanze]

(e-mail address removed) wrote:
template<std::size_t size>
void reverse(char (&input)[size])
Using the compiler to tell you the size certainly can't be considered
"a pass", or this is really getting to be a silly question.
The point was that you don't know the length ahead of time.
He also didn't have a character array, only a char*.
Next we'll be asked to write a program telling us if a
passed string is of finite length.
That's an easy one, unless you need the answer in finite time.
It's easier than that, it can be done in constant time:
bool
hasFiniteLength( char const* string )
{
return true ;
}
This will fail, of course, the day machines start having
infinite memory, but for the moment, we're safe.

Once again, it depends on how you define the length of
string. For char* strings, the length is the distance
between strings and the first null byte. If there is no
null byte in the memory (improbable, but possible), strlen
could loop forever, unless it's specifically programmed to
detect loop over. In anycase, this could be considered as
an infinite length string.

How could that code be written in standard C++? If it covers
the whole address space, it eventually must dereference null.

Could you cite something in the standard to support that.

(Seriously, I've used implementations where you could increment
a pointer forever without ever encountering a null pointer. And
the architecture in question, the Intel 80x86, is still used,
widely enough that I wouldn't consider it exotic, even if it is
strange and ugly.)

 

[James Kanze]

Are you saying that repeatedly incrementing the lower 16 bits
of a pointer value never gets you into the next segment?

Or the lower 32 bits on an 80386, with 48 bit pointers.

Doesn't the operation "increment a pointer" include
incrementing the segment register?

No. Why should it. You're only allowed to increment within a
single object (array), or to one past the end. Depending on the
compilation model, the maximum object size was designed to fit
into a single segment. Note that this also affects comparisons
for inequality. The compiler only compares the offset, not the
segment.

 

[Jerry Coffin]

Hi, C++ programmers

I have been thinking solution for this problem: to reverse a string
with 0 terminator in one pass without using auxillary memory. My
initial thought is to use recursion, but I have not succeeded finding
an answer. Notice that if you use strlen, it will be considered as one
pass. Could you give me some clues?

Precisely as stated, it's impossible. Recursion only hides the auxillary
memory; it doesn't really eliminate it (in fact, it normally increases
it since it requires storage not only for the items in the string
itself, but also for the same number of return addresses -- in a typical
case of 8-bit characters and 32-bit addresses, this will quintuple the
auxillary memory requirements).

As to saying it's impossible, the reason is simple: to avoid using
auxillary memory, each character must be swapped directly from its
source to its destination -- but with a zero-terminated string, the
destination can only be determined by traversing to the end of the
string.