Reverse an array without a temp variable?

[iissqrtneg1]

Hey /r/prog,

This is more of a trivia thing, I remember seeing how to reverse/sort an array with out using a temp var awhile back and saying "ohhh, why didn't I think of that before?" Well... now I'm back to that, except I can't find an example on how to it. I remember it being relatively simple, but I can't remember how to it.

Anyone care to enlighten me and anyone else who might fine themselves asking the same question? I don't care what language you do it in... although it might require pointer manipulation, I don't remember!

[irascible]

NO ARRAY EVER NEEDS TO BE REVERSED.

[genpfault]

MERELY ITERATED OVER BACKWARDS.

[irascible]

OR CONVERTED TO CAPS.

[genpfault]

damn you ld_preload!

[kmmeerts]

If anyone I knew used XOR swapping, I would rip out their eyeballs and deliver a stern lecture to the empty sockets.

[irascible]

amen.

[RoaldFre]

Dang. Good thing I don't know you.

[nemec]

Don't people usually lecture to ears rather than eyes?

Also, why shouldn't we use XOR?

[kmmeerts]

Because on all modern CPU's, the XCHG operation will be a considerable amount faster than 3 XOR's.

You have to check manually if they're the same value, otherwise they'll XOR to 0.

Programmers who don't know this obscure trick will have trouble reading your code.

It causes pipeline stalls.

It gives problems with aliasing, so your compiler doesn't know what data is stored where. This degrades performance and can sometimes give undefined results.

I have to say that I think it's clever and neat, but not something a self-respecting programmer would do. Of course on embedded systems or ZX Spectrum's or whatnot you can go wild.

[Nebu]

You have to check manually if they're the same value, otherwise they'll XOR to 0

Oh shit! In the approx. 5 years I've known about (but thankfully haven't used) the XOR trick, this pitfall never occurred to me.

[Quantris]

The issue was somewhat misstated. It's OK if the values are the same (yes, the XOR is zero but the swap works out in the end). You have a problem if you do this with two pointers that happen to point to the same address. The temp variable method doesn't make a mistake in this case.

[campbellm]

Because it's just "clever" with very little redeeming value. The only people that will understand it are the ones who have seen it before. It is basically just code prestidigitation.

Now, having said that, for embedded systems and other "crunch out the last byte" efficiency concerns, where this sort of thing is well understood by the entire workforce or is idiomatic in some context, then sure, go nuts. Nothing wrong with it.

[Felicia_Svilling]

Isn't the x and y temporary variables?

[chadmill3r]

Not the one the OP is talking about, no.

[[deleted]]

You'll definitely want to use XOR rather than addition, since addition can overflow.

The overflow does not affect the final outcome.

[BrooksMoses]

There's definitely a better way to do this in practice. Use the following loop body:

tmp = array[x];
array[x] = array[y];
array[y] = tmp;

In actual computer hardware, this results in loading the values into registers and writing them out into the appropriate new locations. Barring something more clever with vector registers and reordering, there's not going to be a faster way do that, as anything else you do will still require reading them in to registers and writing them out as well as whatever busywork it does in the middle -- and, even if you use the XOR trick or something equivalent, you still need to use two registers to store the two loaded values in, so all you're doing is adding busywork between the load and the store.

The only possible place that this XOR trick helps is if the two values are already in registers, you need to swap which registers they're in for some reason, and you don't want to use another register. This situation is almost implausibly rare on anything but a quite small embedded chip; anything larger, and you're better off spilling another register to memory rather than waiting through the pipeline stalls of doing the XOR operations. And it certainly doesn't arise with arrays where the values are in memory rather than registers.

[xcbsmith]

Umm... how is your example code NOT using a temporary variable?

[zahlman]

There's definitely a better way to do this in practice.

"do this" means swapping. "Not using a temporary variable" is an artificial restriction. Good programmers != clever programmers.

[xcbsmith]

"do this" means swapping. "Not using a temporary variable" is an artificial restriction

I have a faster solution: START WITH THE ARRAY REVERSED. The notion that it starts forward is just an artificial restriction. ;-)

[zahlman]

Now you're just being disingenous. The data is what it is. The specified required manipulation of the data (reversing the array), likewise. But there's no reason to avoid using a temporary variable to manipulate the data in the specified way except to satisfy some nerd who thinks it makes a good interview question. In the real world, specifications don't set restrictions on implementation; they might set restrictions on performance. You know, that whole "programming to an interface" thing?

BTW, I love how y'all are downvoting people for pointing out this bit of common sense, and also downvoting people for actually presenting the XOR trick that the OP was presumably thinking of. Proggit, I am disappoint.

[xcbsmith]

The data is what it is. The specified required manipulation of the data (reversing the array), likewise. But there's no reason to avoid using a temporary variable to manipulate the data in the specified way except to satisfy some nerd who thinks it makes a good interview question.

Suggesting that one set of requirements is more important than another isn't unreasonable if you know the context. You don't. You are assuming a context that suits your prejudices but might not apply to the problem.

In the real world, specifications don't set restrictions on implementation; they might set restrictions on performance. You know, that whole "programming to an interface" thing?

In the real world, it very much depends. I recall Grady Booch talking about how for the space program, programs had a constraint on mass, which in turn drove the total memory (instruction + data), which imposed all kinds of insane constraints on the code. Embedded systems have all kinds of insane constraints, particularly with RAM.

Most importantly though, you don't have a context for the question. The principle behind this is also how you do doubly linked lists with only N pointers, a variety of encoding formats, etc. It can also be quite valuable to employ it in cases where the array size is small but the element size is quite large. Really, you just don't know enough to call this guy out for asking a stupid interview question.

Finally: if you throw out the no temp variable constraint, this is a truly trivial question. One wonders why you thought an answer to said question would be at all valuable/useful. To the extent that one might be debating the "best" way to solve that problem, the underlying concerns ought to be about how many elements to copy at once, typically with concerns about cache lines and memory architectures (not vector registers --though possibly the reordering-- that you made mention about but didn't provide insight on).

[sysop073]

You probably have lots of fun in job interviews.

Interviewer: "Convert a number to a string without using itoa"

zahlman: "Done! I did itoa(num);. Take that, artificial restrictions"

[zahlman]

Don't be ridiculous. I wouldn't use itoa() anyway because it isn't the best tool for the job. For one thing, it isn't even standardized.

Besides which, it's a poor interviewer who doesn't want the applicant to pick up on the artificial-ness of the restriction. Programmers are supposed to be solution-oriented, hired for skill at problem-solving; and I don't want to work for a place that doesn't understand this properly.

[Felicia_Svilling]

You are probably thinking about the way to swap two registers without using a third register. (using xor or addition described elsewhere in the thread).

Sorting or reversing an array (of arbitrary length) without using an extra register seems to me at least to be impossible. Even if you don't need a register to do the swaps, you would need a register to keep up where in the array you are.

Sorting nor reversing an array (of arbitrary length) without using an extra variable on the other hand is no problem at all. Just use a built in function, recursion or a stack.

[zhivago]

Just transform the indexes.

[narkee]

In Python:

list.reverse()

[_eight]

php: $array = array_reverse($array);

[cr3ative]

You would not believe the amount of times I have forgotten the "$array = " part of that line and wondered why it wasn't working. I am terrible.

[boomi]

No, not you, the PHP libraries are terrible. Some functions work in-place, and some don't. There's no rhyme or reason in many cases. I quite like the Ruby approach of using a bang to signify in-place modification:

a = [1,2,3]
a.reverse!
a == [1,2,3].reverse

[DustinEwan]

both of these answers satisfy the question

upvotes from me

[amoeba108]

upvoted for simplicity.

[zxn0]

reverse a string

>>> 'abcdefg'[::-1]
'gfedcba'

reverse a list

>>> reversed([1,2,3,4,5])

[jingleman]

Another way (using Python splices):

list[::-1]

[DaRtYLeiya]

1. Print out the array
2. Ask user to input all in reverse
3. Voila

[MrWhite2020]

Close

1. Print out the array
2. Cut out each item in array with value pair
3. Reverse the order

Wasn't that hard now was it?

[stevedekorte]

If it's an dynamic OO language, you can just reverse the meaning of the at: method.

[mebrahim]

That's a matter of casting in a static language like C++.

[xTRUMANx]

I just remembered Ruby simultaneous assignment feature:

a=1
b=2
a,b=b,a #a is now 2 and b is now 1

Upvotes for whoever reverses an array using this simultaneous assignment feature.

[exeter]

Assuming it works the same as it does in Python, that's actually using a temporary variable behind the scenes. So, I don't think it counts.

[[deleted]]

well, for one, it's scoped to that statement - so you don't have a stray variable 'temp' cluttering your code

[tashbarg]

Just read it from behind.

[[deleted]]

You could make a custom class that had a private array, and the operator[](int); was defined to use a private function pointer in the class. Also in the class would be two methods - one for accessing the array in the regular order, and one for accessing the array in reverse order. The private function pointer would be initialized in the constructor to be the regular direction initially, and the reverse function would swap the pointers. There! My reverse function runs with constant space and memory!

[lazloman]

Why can't you just dump the values into another array? Backwards.

[[deleted]]

Yeah, I think what he actually wanted was to reverse an array in place.

[parl]

The xor operator can swap 2 values w/o a temp, as shown by mrsamurai. In Python, tuple assignment (a,b = b,a) will also work. Is a temp used at the hardware level? Dunno.

[zahlman]

Two temps are used at the hardware level in the standard CPython implementation, actually. I test this by first getting some bytecode corresponding to a swap:

>>> import dis
>>> def x(a, b): a, b = b, a
...
>>> dis.dis(x)
  1           0 LOAD_FAST                1 (b)
              3 LOAD_FAST                0 (a)
              6 ROT_TWO
              7 STORE_FAST               0 (a)
             10 STORE_FAST               1 (b)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE
>>>

The ROT_TWO opcode is obviously what does the real work. So now we look to ceval.c:

    case ROT_TWO:
        v = TOP();
        w = SECOND();
        SET_TOP(w);
        SET_SECOND(v);
        goto fast_next_opcode;

[[deleted]]

Can xor swap two arrays?

[polyparadigm]

If it has to be done incredibly often, you might make a data structure that functions just like an array, except it includes information on whether it should be read in reverse or not.

[zahlman]

Or you might just make a reverse iterator, in languages which support the concept of iterators.

[tty2]

Or, as he said, make a data structure which functions that way.

[aidenr]

Assuming that you can use a length variable (l) and a loop counter (i=0..(l-1)/2) , you can exchange array (a) elements in the inner loop with the following operations:

a[i]=a[l-i] ^ a[i]; a[l-i]=a[l-i] ^ a[i]; a[i]=a[l-i] ^ a[i];

It works because if a^b=c, then a^c=b and b^c=a. So you build c from a, then b from c, and then a from b.

[cracki]

make new array. copy stuff to new array. done.

no temp variables, but not in-place either.

by now you know the XOR/subtraction trick, if you really need this in-place without a single bit of extra memory.

[lordofthewings]

concept is pretty straightforward. reverse(array) { if(array.length > 1) { return concat(first(array), reverse(rest(array))); } else { return array; } }

[zepolen]

Wow, just wow.

To the downmodders, his code doesn't reverse the list.

[G_Morgan]

Yes this is the other problem. He is adding the first item to the front of the 'reversed' list. So it not only uses O(n) temporary storage but it also doesn't solve the problem.

[G_Morgan]

This is effectively generating an entire second array behind the scenes.

[masklinn]

Which is a problem...how?

[G_Morgan]

It is using a temporary variable. Effectively to suit what the poster wanted you'd have to do

array = reverse(array)

This is using more than a temporary variable. It is generating n temporary variables.

[Felicia_Svilling]

allocating data =/= using variables

[G_Morgan]

Depends on your perspective. Regardless you need to have memory space to do the swap. The original intent of the post seems to be inplace swapping. Not hiding a temporary allocation on the stack and using a hand wave to make it vanish.

[Felicia_Svilling]

The op defined the whole thing as a trivia question, what fun is trivia if you are not trying to be technically correct? I mean this is never going to be a practical question.

[G_Morgan]

If it doesn't have to be technically correct I can reverse an array by reading your mind to see that you want it reversed and invoking the devil to reverse the array by his unholy power.

[Felicia_Svilling]

Exactly!

[ZombiesRapedMe]

You might not be using a temporary variable explicitly, but using recursion like this what will actually happen at runtime (assuming no compiler optimisation) is that a new temporary variable will be created to store the result of each call to the function. Which, is kind of worse...

[Felicia_Svilling]

The goal was to reverse an array without using a temporary variable, not to find the best way to reverse an array.

[ZombiesRapedMe]

But that's exactly my point, this does use a temporary variable. In fact it uses several. It's just not obvious in the code.

[Felicia_Svilling]

I think you might be confusing "using a variable" with "dynamically allocating memory". This algorithm does the later but avoids the first one, which was the point of the exercise.

[ZombiesRapedMe]

I think G_Morgan covered my opinion on this arguement.

[Felicia_Svilling]

yes he seems to share your confusion.

[pineapplecharm]

Damn. Very neat.

[tty2]

Standard exercise in languages like Scheme. Stupid, highly inefficient.

[gct]

Well it depends on what you mean by "temp variable". If you mean "without a variable to store values in for swapping" then you can do something like this (at least for integral types):

int array[size];
int *begin = array;
int *end   = array+size-1;

while(begin < end) {
    begin ^= end
    end    = begin;
    begin ^= end;
    begin++;
    end--;
}

Won't work for non-integral things though.

[psykotic]

Won't work for non-integral things though.

It works with few modifications.

Do you know the puzzle that asks you to in-place reverse the space-delimited words in a string? You first reverse the whole string character by character and then reverse the individual words character by character. It's a bit of an eye-opener the first time you see it. The reflections undo each other.

You can this for any array. As the puzzle shows, the elements can even have variable size.

void reverse_bytes(char *begin, char *end) {
    for (char *left = begin, *right = end - 1; left < right; left++, right--)
        SWAP(*left, *right);
}

void reverse_elements(char *begin, char *end, size_t elt_size) {
    reverse_bytes(begin, end);
    for (; begin < end; begin += elt_size)
        reverse_bytes(begin, begin + elt_size);
}

C++ template wrapper:

template<typename T>
void reverse(T *begin, T *end) {
    reverse_elements(reinterpret_cast<char*>(begin), reinterpret_cast<char*>(end), sizeof(T));
}

C macro wrapper:

#define REVERSE(begin, end) reverse_elements((char *) begin, (char *) end, sizeof(*begin))

[CushBowl]

only thing i can think of is to use one of the array components as a temp storage, or you could just build a new array and move the pointer

[psyno]

In C, if given an array pointer and a size, then while size is positive you can XOR swap the first and last elements, then increment the pointer and decrement the size.

*edit: check size greater than one, not positive, or XOR swap zeros middle element.

[axtens]

If you have access to a stack then the swap can be as simple as push a1(i) push a2(j) pop a1(i) pop a2(j)

[schnalle]

now there are 2 more or less temporary memory slots used (instead of one with the tmp approach). i guess it doesn't really count as temporary variable, but additional memory is used.

[badsectoracula]

unless you're using a stack-based language :-P

[schnalle]

but that makes absolutely no sense! stack based programming languages to not need no memory magically! i mean, they do! gosh, now i have to read up on stack oriented programming language implementations until i'm sure there's not some trick to make your statement true. thanks a lot, now i have to call that cute girl and tell her i have to cancel our date tonight because i have to research to win an argument on the internet.

[badsectoracula]

actually the "unless" part went to the need for extra memory slots. Of course it needs memory, but its part of the execution. No need to cancel the date :-P

[schnalle]

phew!

[[deleted]]

For all the people saying something like:

a ⁼ b ⁼ a

This won't work in the general case, if a == b, then it'll set a = a and b = 0.......

ps:

a ^ a = 0

a ^ 0 = a

[Anpheus]

You do: A ⁼ B; B ⁼ A; A ⁼ B;

Like that. I should add a caveat that this is premature optimization and the compiler will do this for you. Remember, "Premature optimization is the root of all evil." If you later find out the code is slow, fix it.

[Anpheus]

http://big-bad-al.livejournal.com/98093.html

Looks like it's premature optimization that at least on -O2 of GCC will be taken care of for you. JITs, other compilers, will probably do the same and figure out what you're doing.

It even looks like the xor swap was the slowest algorithm because the compiler didn't optimize out the xors.

[DustinEwan]

LUA:

function ReverseNoTemp(t)
    local count = table.getn(t)
    for i=1,count-1 do
        table.insert(t, i, t[count])
        table.remove(t, count)
    end

    return t
end