0

i encountered to this function

void reverseArray(int *a,int n)
{
for(int i=0,j=n-1;i<j;i++,j--)
{
a[i]^=a[j]^=a[i]^=a[j];
}
}

which is reversing a given array but I can't wrap my mind around how does this reverse an array, isn't Xor operator only returns the non-common bits. so what's the logic behind this to reverse the given array.

EmreAkkoc
  • 623
  • 1
  • 11
  • 18
  • Re “the non-common bits”: When you flip the non-common bits in `a[j]`, it makes those bits have the values they have in `a[i]`, so the result equals `a[i]`. Then, from right-to-left, `a[i]^=a[j]` finds the non-common bits (`^`) and stores them (`^=`) in `a[i]`. Then `a[j]^=a[i]^a[j]` flips those bits in `a[j]`, making it equal to the original `a[i]`. Then `a[i]^=a[j]^=a[i]^=a[j]` XORs the non-common bits that were stored in `a[i]` with the original value of `a[i]` (now in `a[j]`), so that flips the non-common bits to make the original `a[j]`, which is stored in `a[i]`. – Eric Postpischil Oct 29 '21 at 13:42
  • 5
    It should be noted, however, the behavior of this statement is not defined by the C standard, because the updates to `a[i]` are not sequenced. – Eric Postpischil Oct 29 '21 at 13:43
  • @EricPostpischil That is correct, I will add that to my answer below. – nielsen Oct 29 '21 at 13:47
  • 2
    Be aware that there are two diametrically opposite ways to answer this question. (1) There was a (perverse) goal that the author of this code was trying to achieve, and we can explain what that goal was, and how it was achieved. But (2) as you yourself have seen firsthand, this code is impossible to understand on first reading. Moreover, it's undefined: it's not even guaranteed to work. So, while this may be a useful example to learn from, it is absolutely *not* something to be admired, emulated, or used in a real, practical program, ever! – Steve Summit Oct 29 '21 at 13:49
  • 1
    See [Question 20.15c](http://c-faq.com/misc/swapnotemp.html) in the [C FAQ list](http://c-faq.com/). – Steve Summit Oct 29 '21 at 13:55
  • 1
    See [What is the difference between two different swapping function?](https://stackoverflow.com/questions/58462258) – Steve Summit Oct 29 '21 at 13:59

2 Answers2

3

a ^= b ^= a ^= b; is a fancy way to swap two numbers, known as XOR swap.

You should prefer a much more readable std::swap, or (in C) a temporary variable.

HolyBlackCat
  • 78,603
  • 9
  • 131
  • 207
2

The purpose of the expression a^=b^=a^=b is to exchange the values of a and b. It becomes more clear if we split it up (where a_0 and b_0 are the original values of a and b):

  1. First assignment, a^=b makes a_1=(a_0^b_0).
  2. Second assignment, b^=a makes b_1=(b_0^a_1)=(b_0^(a_0^b_0))=a_0
  3. Third assignment, a^=b makes a_2=(a_1^b_1)=((a_0^b_0)^a_0)=b_0

Thus we end up with a having the original value of b and vice versa.

While the expression a^=b^=a^=b may work it is actually undefined behavior because the C standard does not specify the order of assignments. Instead, it must be sequenced explicitly: a^=b; b^=a; a^=b;.

nielsen
  • 5,641
  • 10
  • 27