Mladen Prajdić Blog

Blog about stuff and things and stuff. Mostly about SQL server and .Net

Reverse string in C# and bitwise XOR


why is there no reverse string function in c#?? Is there realy no need for that function??
there are of course a few ways to make your own reverse function. most favorite is definitly the one using recursion with substring. that's preety cool i thought why not... and then i remembered something that i learned in my first year of college... bitwise operations. i knew that there was a handy little way of switching 2 values using something with XOR without using a 3rd variable. i just couldn't remember it... so i went googling... it sure was faster than going through my books :)) and voila... XOR 2 values bitwise 3 times and they're switched.
So i metion this to a friend of mine... a soon to be a computer science graduate... and he looks at me with a blank stare... so i go about explaining it and he goes: huh??
so why are bitwise operation so hard to understand?? are they too hard to grasp???
well for anyone who wants it :) here's the reverse function:

 

public string Reverse(string str)
{
    // convert the string to char array
    char[] charArray = str.ToCharArray();
    int len = str.Length - 1;
    /*
    now this for is a bit unconventional at first glance because there
    are 2 variables that we're changing values of: i++ and len--.
    the order of them is irrelevant. so basicaly we're going with i from 
    start to end of the array. with len we're shortening the array by one
    each time. this is probably understandable.
    */
    for (int i = 0; i < len; i++, len--)
    {
        /*
        now this is the tricky part people that should know about it don't.
        look at the table below to see what's going on exactly here.
        */
        charArray[i] ^= charArray[len];
        charArray[len] ^= charArray[i];
        charArray[i] ^= charArray[len];
    }
    return new string(charArray);
}

OK, so to clear up for those who are stumped at how this works:
let's say we want to switch 2 binary values x1 = 100 and x2 = 111 so that x1 = 111 and x2 = 100.

 

in c# x1 ^= x2 equals to x1 = x1 ^ x2 where ^ is the bitwise XOR.

 

XOR (Exclusive OR) table
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
First operation: x1 = x1 XOR x2
 
x1: 1 0 0
x2: 1 1 1
New x1: 0 1 1
 
Second operation x2 = x2 XOR x1
 
x1: 0 1 1
x2: 1 1 1
New x2: 1 0 0
 
Third operation: x1 = x1 XOR x2
 
x1: 0 1 1
x2: 1 0 0
New x1: 1 1 1

And voila, we now have x1 = 111 and x2 = 100.
and for each pair in array we do this because string chars are in essence binary values :)))
This method is also the quickest way to reverse a string.
Recursive way is almost 4-5 times slower.

EDIT:

Well after Arnold pointed me to this site i came up with this:

 

public string Reverse2(string x)
{
    char[] charArray = new char[x.Length];
    int len = x.Length - 1;
    for (int i = 0; i <= len; i++)
        charArray[i] = x[len-i];
    return new string(charArray);
}

This one is even faster than XOR on small as well as large strings by 50%. Looking at the algorithm is preety evident where the speed is gained:

here there's no copy of the string it's just a new empty array of fixed length
char[] charArray = new char[x.Length];

there are no 3 operations just one. i++ and len-- in XOR function is equalized by i++ and len-i here so the speed is just from 1 operation vs. 3 operations.
for (int i = 0; i <= len; i++) 
    charArray[i] = x[len-i];


Arnold if you have any check for surrogate pairs you can share i'm all ears (eyes). :))


kick it on DotNetKicks.com

Legacy Comments


Xaprb
2006-03-19
re: Reverse string in C# and bitwise XOR
You have a couple of the names reversed. I think it should be

x1: 100
x2: 111
new x1: 011

x2: 111
x1: 011
new x2: 100

x1: 011
x2: 100
new x1: 111

The result is x1 = 111 and x2 = 100. Remember, you started out with x1 = 100 and x2 = 111, so if that's what you end up with, you didn't do anything :-)

Mladen
2006-03-19
re: Reverse string in C# and bitwise XOR
fixed thanx :))

rockmoose
2006-03-20
re: Reverse string in C# and bitwise XOR
Thanks for clearing that up Mladen!
Why don't you link to the sqlteam topic as well :)

cheerio!

mladen
2006-03-20
re: Reverse string in C# and bitwise XOR
which topic?

that wasn't clear for you before?? :)) tsk tsk tsk... :))

rockmoose
2006-03-20
re: Reverse string in C# and bitwise XOR
I might have had to use google ;).
The fun part was the way you used it to reverse a string.
cool.

Jon Hermiz
2006-03-20
re: Reverse string in C# and bitwise XOR
What about applying .Reverse to a char[] ?

char [] A = TextBox1.Text.ToCharArray();
Array.Reverse( A );
string strReversed = new string( A );


mladen
2006-03-21
re: Reverse string in C# and bitwise XOR
tried it.
2-3 times slower.

Jon Hermiz
2006-03-21
re: Reverse string in C# and bitwise XOR
2-3 times slower? How are you measuring something that is based on cpy cycles?
Did you test it on a 500mhz or a 1ghz? You cant really measure something like this in an isolated environment. It still should reverse your string.

mladen
2006-03-21
re: Reverse string in C# and bitwise XOR
well i measure it preety simply :)
i start up my computer. disconnect it from lan.
run each function in for loop with 1+ million iterations that reverse the same string and meause the time.
on my machine 64 bit sempron with 1gb RAM XOR runs it constantly in 4-5 seconds, array reverse runs in 10-13 secs while recursive runs it in around 20-22 secs.

so that seems preety consistent for me...

if you have any other suggestion i'm all ears.

Jon Hermiz
2006-03-21
re: Reverse string in C# and bitwise XOR
If your app really needs to reverse them that fast I guess you've won :-)

mladen
2006-03-21
re: Reverse string in C# and bitwise XOR
lol :))
that's not the point.
the point was to show how it can be done with XOR.

Arnold Fribble
2006-03-21
re: Reverse string in C# and bitwise XOR
Shame it screws up all your UTF-16 surrogate pairs.

Mladen
2006-03-21
re: Reverse string in C# and bitwise XOR
care to elaborate more on that arnold?

Arnold Fribble
2006-03-22
re: Reverse string in C# and bitwise XOR
As I understand it, the 'char' values in a C# string are really UTF-16 code units. For Unicode characters encoded in the BMP that means that each char is a character, but for characters encoded in a supplementary plane, each char is a high or low surrogate. Reversing the order of chars in a string without taking care of surrogates can leave you with an invalid UTF-16 string.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfSystemCharClassTopic.asp

"The Char value type represents a Unicode character, also called a Unicode code point, and is implemented as a 16-bit number ranging in value from hexadecimal 0x0000 to 0xFFFF. A single Char cannot represent a Unicode character that is encoded as a surrogate pair. However, a String, which is a collection of Char objects, can represent a Unicode character encoded as a surrogate pair."

mladen
2006-03-22
re: Reverse string in C# and bitwise XOR
if i understand this correctly neither of the 3 (XOR, recursive, Array.Reverse) reverse functinos would work with surrogates, no?

i wonder if VB's reverse handles that...

Arnold Fribble
2006-03-22
re: Reverse string in C# and bitwise XOR
Yes, sorry, I wasn't commenting particularly on using XOR, just reversing char-by-char.

Arnold Fribble
2006-03-22
re: Reverse string in C# and bitwise XOR
Searching for
c# string reverse surrogate
turns up this page:

http://weblogs.asp.net/justin_rogers/archive/2004/06/10/153175.aspx

mladen
2006-03-22
re: Reverse string in C# and bitwise XOR
cool!

it always amazes me how many different approaches can be used to achieve the same thing.

Gennaro
2006-03-30
re: Reverse string in C# and bitwise XOR
How about:

public void Reverse( ref string theString )
{
char[ ] c = theString.ToCharArray();
Array.Reverse(c);
new string(c);
}

public string Reverse( string theString )
{
char[ ] c = theString.ToCharArray();
Array.Reverse(c);
return new string(c);
}

Mladen
2006-03-30
re: Reverse string in C# and bitwise XOR
look at the 7th comment from the top down. :)

Ozan Kılıçoğlu
2006-04-21
re: Reverse string in C# inplace
I know it's smells like "C" (may be further improved with XOR trick)

unsafe void ReverseInplaceArr( string text ) {

fixed ( char* pChar = text ) {

char swapChar;
int length = text.Length - 1;

for ( int i = 0, j = length; i < j; i++, j-- ) {

swapChar = pChar[i];
pChar[i] = pChar[j];
pChar[j] = swapChar;

}//for

}//fixed

}//Reverse


unsafe void ReverseInplacePtr( string text ) {

fixed ( char* pChar = text ) {

char swapChar;
int length = text.Length - 1;
char* pStart = pChar;
char* pEnd = pChar + length;

while ( pStart < pEnd ) {

swapChar = *pStart;
*pStart = *pEnd;
*pEnd = swapChar;

pStart++;
pEnd--;

}//while

}//fixed

}//Reverse

Ozan Kılıçoğlu
2006-04-21
re: Reverse string in C# and bitwise XOR
Ok... Ok... Justin Rogers already mention that, so previous post a little little redundant redundant.

http://weblogs.asp.net/justin_rogers/archive/2004/06/10/153175.aspx

Maheshkumar.R
2006-04-27
re: Reverse string in C# and bitwise XOR
thanks to all..
I started to out string->integer conversion without using any inbuilt libraries and got succeeded. But in vice versa...I tried and end up with string but in reversed order...
let say,

int v1 =1;
int v2 = 0;
string result = "";

v2 = 2345;
while (v1 > 0)
{
if (v2 ==0)
break;

v1 = v2 % 10;
v2 = v2 / 10;
result += v1;
}

but i dont know, how to proceed after the reversed string to actual form.
Now the result is 5432. I want result as 2345. any idea regarding this....?


Mladen
2006-04-27
re: Reverse string in C# and bitwise XOR
so why don't you do this?

string s = Reverse(v1.ToString());
v2 = (int)s;

Maheshkumar.R
2006-04-28
re: Reverse string in C# and bitwise XOR
ok. let me follow urs.

v2 = (int)s; - Cannot convert type string -> Integer ..??


Mladen
2006-04-28
re: Reverse string in C# and bitwise XOR
well then i guess your reversed string isn't a proper integer :)

you could but a byte array as input parameter and then convert that to whatever you wish to have a general reverse function...

Greg Young
2006-07-21
re: Reverse string in C# and bitwise XOR
public static unsafe string GregsInt32Reverse(string s) {

UInt32 Low;

UInt32 High;



string ret = string.Copy(s);

fixed (char* start = ret) {

UInt32* begin = (UInt32*)start;

UInt32* end = (UInt32*)(start + s.Length - 2);

UInt32* stop = begin + (end - begin) / 2;

while (begin <= stop) {

Low = *begin;

Low = ((Low) << 16)| (Low >> 16);

High = *end;

High = ((High) << 16) | (High >> 16);

*begin = High;

*end = Low;

begin++;

end--;

}

}

return ret;

}


Mladen
2006-07-21
re: Reverse string in C# and bitwise XOR
LOL!

Good one Greg! :)

But i tend to think this is a kind of cheating since you're using unsafe code.

but pointers rule!! :)


Greg Young
2006-07-22
re: Reverse string in C# and bitwise XOR
If I could just get a ROTL generated instead of the SHL OR and SHR I would be set .. that and the JIT puts two useless movs into the inner loop :(


2006-10-02
palidorme in C#
send the code to check that the string is palidrome or not

Mladen
2006-10-02
re: Reverse string in C# and bitwise XOR
Of course.
How soon can you send $850 US for my time?

kuldeep singh
2007-03-03
string palindrom in vc#
sent me a souese code for string palindrom in vc# code.

Mladen
2007-03-03
re: Reverse string in C# and bitwise XOR
sure. no problem.
after you send me $850 for it.

Rune
2007-03-14
re: Reverse string in C# and bitwise XOR
I'll bet that with very largest arrays the bitwise would be faster than using the two arrays especially on mobile devices or other units with small amounts of RAM and Cache. The bitwise is memery neutral whereas the to array uses, well twice the amount of memory. and the beatiful thing about the bit is that u can make it work on unicode as well. correct a unicode char is actually to bytes but say u have 0001 1111 0001 1111 for one char (whatever that might be) and 0000 0000 0010 0000 (space) and use the above alogirthm it still reverse the order of the chars (not the bytes). (try it out if u doubt me). The problem only arises if u do the calculatoin wrong (byte by byte) but that's asking for a reversal of the bytes and hence the result is correct in that case as well

Erik Little
2007-07-05
re: Reverse string in C# and bitwise XOR

Array.Reverse(charArray);

LOL

VB FAN!
2007-07-09
re: Reverse string in C# and bitwise XOR
Guys forget about C, C++, C#.
VB.Net is just a bless from heaven, look ....

If strReverse("ABCD") = "DCBA" Then msg = "VB Rules!" Else msg = "I doubt it!"

I know that the old VB was so stupid compared to C++ but now with VB.Net specially VB.Net 2005 things are absolutely different.

Mladen
2007-07-09
re: Reverse string in C# and bitwise XOR
we won't go into VB vs The Others discussion here :)
but yes VB has some usefull functions that are missing from C#

Boib
2008-01-09
re: Reverse string in C# and bitwise XOR
Tests show:

1. GregsInt32Reverse(string s) is the fastest
2.
public string Reverse2(string x)
{
char[] charArray = new char[x.Length];
int len = x.Length - 1;
for (int i = 0; i <= len; i++)
charArray[i] = x[len-i];
return new string(charArray);
}
the slowest

3.
public string Reverse( string theString )
{
char[ ] c = theString.ToCharArray();
Array.Reverse(c);
return new string(c);
}

is the best: fast enough, and doesn't make your code unsafe

Mladen
2008-01-09
re: Reverse string in C# and bitwise XOR
nope. :)

Carlo
2009-02-12
re: Reverse string in C# and bitwise XOR
Or

char[] charArray = textToReverse.ToCharArray();

Array.Reverse(charArray);

string reversedText = new String(charArray);

binu
2009-09-10
re: Reverse string in C# and bitwise XOR
static void Main(string[] args)
{
string s = "Hello World";
char[] ch=s.ToCharArray();
int len=ch.Length-1;
for (int i = 0; i <= len/2; i++)
{
char temp=ch[i];
ch[i] = ch[len - i];
ch[len - i] = temp;
}

string s2 = new string(ch);
Console.WriteLine(ch);
}

RAJUL
2009-09-18
re: Reverse string in C# and bitwise XOR
Try This .... Don't Waste Time on this simple prb.
public string Reverse(string strUrstring){
string strReverse=String.Empty;
for(int i=0;i<strUrString.Length;i++){
strReverse+=strUrString.SubString(strUrString.Length-1,1);
strUrString=strUrString.SubString(0,strUrString.Length-1);
}
}

Rajul

Sampath
2009-12-15
re: Reverse string in C# and bitwise XOR
string str_in = txtinput.Text.Trim();
string output = "";
for (int i = str_in.Length-1; i >= 0; i--)
{
output = output + str_in.Substring(i,1);
}
txtoutput.Text = output;


Another Way a Easy one

char[] cstr = str_in.ToCharArray();
Array.Reverse(cstr);
txtoutput.Text = reversestring(cstr);

public string reversestring(char[] newq)
{
return new string(newq);
}

Jon H
2010-01-08
re: Reverse string in C# and bitwise XOR
You may want to make this a class extension method.
Also another way to do it is to use StringBuilder class :).

Here's the extension method:

public static class MyExtensionMethodOnString
{
public static string ReverseMyString(this string s)
{
StringBuilder temp = new StringBuilder();

for (int i = (s.Length - 1); i >= 0; i--)
temp.Append(s[i]);

return temp.ToString();
}

}

And client code can use the extension method as long as it is in the same namespace or include the namespace:

class Program
{
static void Main(string[] args)
{
string t = "hello world";
string temp = string.Empty;

temp=t.ReverseMyString();

Console.WriteLine(temp);
Console.ReadLine();
}
}

In this way you can use the extension method on any string object without having to rewrite this code.


Taye
2010-04-28
re: Reverse string in C#
I think this takes O(n)

public static string reverse(string str)
{
StringBuilder strBul = new StringBuilder();
int n = str.Length-1;
while (n>=0)
{

strBul.Append(str[n]);
str = str.Substring(0,n);
n -= 1;

}
return strBul.ToString();
}

Dan Stewart
2010-10-07
re: Reverse string in C# and bitwise XOR
Sorry, couldn't resist getting this down to one line using System.Linq.

"Hello World!".ToCharArray().Reverse().ToList().ForEach( letter => System.Console.Write(letter) );