What's wrong with my string reversal function? (C#)

Question

char[] a = { 'o', 'r', 'a', 'n', 'g', 'e' };

for (int i = 0; i < a.Length/2; i++)
{        
  a[i] = (char)(((uint)a[i])|((uint)a[a.Length-(i+1)]));
  a[a.Length-(i+1)] = (char)(((uint)a[i])^((uint)a[a.Length-(i+1)]));
  a[i] = (char)(((uint)a[i])^((uint)a[a.Length-(i+1)]));
}

I know how to implement this using standard .NET functionality and temp vars. I am just curious what specifically I am doing wrong in the above example that causes it not to work when the following works fine:

int a = 5;
int b = 10;

a = a | b;
b = a ^ b;
a = a ^ b;

Isn't the above string version just a series of those?

Answer 1

Hehe, there's no such thing as an OR/XOR/XOR swap - it should be a "triple xor" swap.

int a = 8, b = 10;
a ^= b;
b ^= a;
a ^= b;

I don't see why you want to use it (aside from the novelty value)

Answer 2

The reason it's not working is that you're using a bad example. You can't swap two values by using OR then XOR then XOR. It only worked in your example because 5 and 10 have no bits in common, so the first OR doesn't destroy any information:

a = 0101 #5
b = 1010 #10
# step 1 (OR into a)
a = 1111
b = 1010
# step 2 (XOR into b)
a = 1111
b = 0101
# step 3 (XOR into a)
a = 1010 #10
b = 0101 #5

But it won't work if they have any bits in common - let's try with 13 and 10:

a = 1101 #13
b = 1010 #10
# step 1 (OR into a)
a = 1111
b = 1010
# step 2 (XOR into b)
a = 1111
b = 0101
# step 3 (XOR into a)
a = 1010 #10
b = 0101 #5

Note that we now have the values 5 and 10 still, even though we started with 13 and 10. What you're looking for is a thrice-XOR swap:

a = 1101 #13
b = 1010 #10
# step 1 (XOR into a)
a = 0111
b = 1010
# step 2 (XOR into b)
a = 0111
b = 1101
# step 3 (XOR into a)
a = 1010 # 10
b = 1101 #13

Answer 3

It's destructive (because of the bitwise OR). Why not use a temporary variable in your loop instead of the exclusive ORs:

int tmp = a[i];
a[i] = a[a.Length-(i+1)];
a[a.Length-(i+1)] = tmp;

In answer to your second part, what you were doing in binary is:

a = 0101;
b = 1010;
a = 0101 | 1010 === 1111;
...

When you OR the two values together, you destroy the original numbers. It works with 5 & 10 because none of the bits are common between the two numbers. When you do this with the following:

a = 0110;  // 6 (base ten)
b = 1010;  // 10 (base ten)
a = a | b; // this is now 1110, or 14 (base ten)

You can not recover 6 and 10 again, because OR was an irreversible operation. Exclusive-OR is reversible.

Answer 4

Sorry if this is not the point of your question, but how about just:

 char[] a = { 'o', 'r', 'a', 'n', 'g', 'e' };
 a = Array.Reverse(a)

Am I missing something?

Answer 5

Others have already pointed out the correct solution using XOR operations... This isn't exactly an answer, but I thought I'd point you that the Interlocked.Exchange method is very suitable for this sort of task. (It performs the swap as an atomic operation and therefore works across threads, though that seems irrelevant here.) Nonetheless, I would almost always consider it the simplest/most elegant solution for swapping two variables.

Here's an example of how to use it with the code you posted.

char[] a = { 'o', 'r', 'a', 'n', 'g', 'e' };

for (int i = 0; i < a.Length/2; i++)
{        
    a[a.Length-(i+1)] = Interlocked.Exchange(ref a[a.Length-(i+1)], a[i]);
}

Hope that helps, even if it isn't specifically an answer to your question...

Answer 6

List<char> characters = new List<char>();

characters.AddRange("string".ToCharArray());

characters.Reverse();

string reversed = new string(characters.ToArray());