I want some Moore

Blog about stuff and things and stuff. Mostly about SQL server and .Net
posts - 219, comments - 2287, trackbacks - 33

My Links

Advertisement

News

Hi! My name is 
Mladen Prajdić  I'm from Slovenia and I'm currently working as a .Net (C#) and SQL Server developer.

I also speak at local user group meetings and conferences like SQLBits and NT Conference
Welcome to my blog.
SQL Server MVP

My Books

SQL Server MVP Deep Dives 2
The Red Gate Guide to SQL Server Team based Development Free e-book

My Blog Feed via Email
Follow MladenPrajdic on Twitter


Users Online: who's online

Article Categories

Archives

Post Categories

Cool software

Other Blogs

Other stuff

SQL stuff

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

Print | posted on Sunday, March 19, 2006 6:04 PM | Filed Under [ .Net ]

Feedback

Gravatar

# 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 :-)
3/19/2006 7:29 PM | Xaprb
Gravatar

# re: Reverse string in C# and bitwise XOR

fixed thanx :))
3/19/2006 7:47 PM | Mladen
Gravatar

# Reverse string in C#

3/19/2006 5:10 PM | Anatoly Lubarsky
Gravatar

# 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!
3/20/2006 4:48 PM | rockmoose
Gravatar

# re: Reverse string in C# and bitwise XOR

which topic?

that wasn't clear for you before?? :)) tsk tsk tsk... :))
3/20/2006 4:50 PM | mladen
Gravatar

# 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.
3/20/2006 7:09 PM | rockmoose
Gravatar

# 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 );

3/20/2006 9:17 PM | Jon Hermiz
Gravatar

# re: Reverse string in C# and bitwise XOR

tried it.
2-3 times slower.
3/21/2006 11:20 AM | mladen
Gravatar

# 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.
3/21/2006 2:42 PM | Jon Hermiz
Gravatar

# 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.
3/21/2006 4:08 PM | mladen
Gravatar

# re: Reverse string in C# and bitwise XOR

If your app really needs to reverse them that fast I guess you've won :-)
3/21/2006 4:57 PM | Jon Hermiz
Gravatar

# 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.
3/21/2006 5:02 PM | mladen
Gravatar

# re: Reverse string in C# and bitwise XOR

Shame it screws up all your UTF-16 surrogate pairs.
3/21/2006 6:06 PM | Arnold Fribble
Gravatar

# re: Reverse string in C# and bitwise XOR

care to elaborate more on that arnold?
3/21/2006 8:22 PM | Mladen
Gravatar

# 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."
3/22/2006 11:03 AM | Arnold Fribble
Gravatar

# 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...
3/22/2006 11:41 AM | mladen
Gravatar

# re: Reverse string in C# and bitwise XOR

Yes, sorry, I wasn't commenting particularly on using XOR, just reversing char-by-char.
3/22/2006 12:10 PM | Arnold Fribble
Gravatar

# 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
3/22/2006 12:14 PM | Arnold Fribble
Gravatar

# 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.
3/22/2006 12:27 PM | mladen
Gravatar

# 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);
}
3/30/2006 11:19 AM | Gennaro
Gravatar

# re: Reverse string in C# and bitwise XOR

look at the 7th comment from the top down. :)
3/30/2006 12:11 PM | Mladen
Gravatar

# 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
4/21/2006 9:57 PM | Ozan Kılıçoğlu
Gravatar

# 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
4/21/2006 10:20 PM | Ozan Kılıçoğlu
Gravatar

# 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....?

4/27/2006 4:34 PM | Maheshkumar.R
Gravatar

# re: Reverse string in C# and bitwise XOR

so why don't you do this?

string s = Reverse(v1.ToString());
v2 = (int)s;
4/27/2006 11:05 PM | Mladen
Gravatar

# re: Reverse string in C# and bitwise XOR

ok. let me follow urs.

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

4/28/2006 5:48 AM | Maheshkumar.R
Gravatar

# 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...
4/28/2006 3:01 PM | Mladen
Gravatar

# Interesting Finds

5/17/2006 10:44 AM | Jason Haley
Gravatar

# More on string reversal!

In the last installment, I showed a potentially fastest method using Array.Reverse.After finding and...
7/17/2006 10:20 PM | Adam Machanic
Gravatar

# Performance : String Reverse

I can never stay away from a performance challenge. While the others focus on the loop let's focus somewhere else!
7/21/2006 1:05 AM | Greg Young [MVP]
Gravatar

# 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;

}

7/21/2006 8:12 AM | Greg Young
Gravatar

# 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!! :)

7/21/2006 10:42 AM | Mladen
Gravatar

# 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 :(
7/22/2006 4:56 AM | Greg Young
Gravatar

# palidorme in C#

send the code to check that the string is palidrome or not
10/2/2006 10:15 AM |
Gravatar

# re: Reverse string in C# and bitwise XOR

Of course.
How soon can you send $850 US for my time?
10/2/2006 3:00 PM | Mladen
Gravatar

# More on string reversal!

In the last installment, I showed a potentially fastest method using Array.Reverse. After finding and
1/8/2007 2:24 PM | Adam Machanic
Gravatar

# string palindrom in vc#

sent me a souese code for string palindrom in vc# code.
3/3/2007 12:37 PM | kuldeep singh
Gravatar

# re: Reverse string in C# and bitwise XOR

sure. no problem.
after you send me $850 for it.
3/3/2007 1:59 PM | Mladen
Gravatar

# 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
3/14/2007 3:43 PM | Rune
Gravatar

# re: Reverse string in C# and bitwise XOR


Array.Reverse(charArray);

LOL
7/5/2007 10:12 PM | Erik Little
Gravatar

# 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.
7/9/2007 3:05 AM | VB FAN!
Gravatar

# 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#
7/9/2007 10:22 AM | Mladen
Gravatar

# 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
1/9/2008 12:02 PM | Boib
Gravatar

# re: Reverse string in C# and bitwise XOR

nope. :)
1/9/2008 12:03 PM | Mladen
Gravatar

# re: Reverse string in C# and bitwise XOR

Or

char[] charArray = textToReverse.ToCharArray();

Array.Reverse(charArray);

string reversedText = new String(charArray);
2/12/2009 9:57 PM | Carlo
Gravatar

# 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);
}
9/10/2009 12:11 PM | binu
Gravatar

# 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
9/18/2009 12:12 PM | RAJUL
Gravatar

# 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);
}
12/15/2009 2:10 PM | Sampath
Gravatar

# 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.

1/8/2010 3:19 PM | Jon H
Gravatar

# 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();
}
4/28/2010 6:33 AM | Taye
Gravatar

# 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) );
10/7/2010 1:03 AM | Dan Stewart
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET