Wie kann man in C# einen Ulong reversen?
Hallo Community,
ich suche nach einer Methode oder Ausführung die Bits in einem Ulong zu reversen, aus 00100110 sollte bspw. 01100100 werden.
Ich habe schon gesucht, jedoch nichts brauchbares speziell für Ulongs bzw. Uint64s gefunden. Und eine fertige Methode wie in Java gibt es ja in C# nicht.
2 Antworten
Dultus variante ist ein holpriger und langsamer Weg.
- ein ulong wird in einen String konvertiert
- der String wird in ein CharArray gecasted
- die einzelnen Arrayelemente werden einzeln rückwärts in ein neues Array koppiert
- dieses wieder in einen String gecasted
- und einem neuen String zugewiesen
- welcher wieder in eine Zahl konvertiert wird
Von der Schreibweise her billig, aber für eine Zahl die schlechteste Option, welche man sich vorstellen kann.
Die Reihenfolge der Bits lässt sich mit wenigen BitOperationen umdrehen.
//drehe die Anordnung der Bits um (das Höchste Bit steht Rechts das niedrigste Links)
public static ulong ReverseBitOrder(ulong Num){
ulong result=0;
for (int i=0;i < 64; ++i){
ulong currendBitValue=Num & ((ulong)1 << i); //isoliere den Wert des aktuellen Bits mit eine AND-Operation AND-Wert=1 um i-Stellen nach links verschoben
currendBitValue<<=63-i; //aktuellen BitWert an das linke Ende verschieben (spart einen aufwendigen If-Else-Vergleich ob das Bit 1 oder 0 ist! und ob anschließend 18446744073709551615 oder 0 nach rechts verschoben wird)
result|=(currendBitValue>>i); //BitWert um i-Stellen nach rechts schieben und mit OR zu result hinzufügen
}
return result;
}
Das sieht erstmal ziemlich kompliziert aus, wird aber vom Compiler mit superschnellem AssemblerCode honoriert. Es werden keine Speicheroperationen oder Funktionsaufrufe benötigt jede Bitoperation kommt mit einem Prozessortakt aus. (auf 64Bit-Systemen).
demo.cs
using System;
class Prog{
//um zu verfolgen was Unterwegs passiert entferne die Auskommentierungen
public static ulong ReverseBitOrder(ulong Num){
ulong result=0;
for (int i=0;i < 64; ++i){
ulong currendBitValue=Num & ((ulong)1 << i);
// Console.WriteLine("Bit {0:d2} = {1}", i+1, currendBitValue>>i);
currendBitValue<<=63-i;
result|=(currendBitValue>>i);
// Console.WriteLine("{0} = {1}" , result , Convert.ToString((long) result, 2).PadLeft(64, '0'));
}
return result;
}
public static void Main(string[] args){
//mit Du siehst, dass die 64-Bitfolge wirklich umgedreht wird
ulong foo=Convert.ToUInt64("1000000000000000000000000000000000000000000000000000000011110000", 2);
Console.WriteLine("{0} = {1}" , foo , Convert.ToString((long) foo, 2).PadLeft(64, '0'));
ulong oof=ReverseBitOrder(foo);
Console.WriteLine( "{0} = {1}" , oof , Convert.ToString((long) oof, 2).PadLeft(64, '0'));
Console.WriteLine("Taste drücken...");
Console.ReadKey();
}
}
Irgendwie hatte mich der lesbar gehaltene Code doch an der Ehre gekratzt.
Da ist doch noch etwas optimierbar, ab es wird weniger Lesefreundlich:
using System;
using System.Diagnostics;
class Prog{
public static ulong ReverseBitOrder(ulong Num){
ulong result=0;
for (int i=0;i < 64; ++i){
result|=(((Num & (ulong)1 << i)<<63-i)>>i); //bringt etwa 10% mehr Speed. ...aber schlechter nachzuvollziehen
}
return result;
}
public static void Main(string[] args){
ulong foo=Convert.ToUInt64("1000000000000000000000000000000000000000000000000000000011110000", 2);
Console.WriteLine("{0} = {1}" , foo , Convert.ToString((long) foo, 2).PadLeft(64, '0'));
Stopwatch stopWatch = Stopwatch.StartNew();
ulong oof=ReverseBitOrder(foo);
stopWatch.Stop();
Console.WriteLine( "{0} = {1}" , oof , Convert.ToString((long) oof, 2).PadLeft(64, '0'));
// ein wenig Zeitakrobatik
Console.WriteLine( "Executiontime : {0} Nanoseconds", (1000000000L / Stopwatch.Frequency) * stopWatch.ElapsedTicks); // 1 Tick sind beim Hirescounter 100 Nanosekunden
//eigentlich Quatsch, auf modernen Computen und WindowsSystemen immer Hires (100 Nanosec/Tick)
if (Stopwatch.IsHighResolution){Console.WriteLine("Operations timed using the system's high-resolution performance counter.");}
else{ Console.WriteLine("Operations timed using the DateTime class.");}
Console.WriteLine("Taste drücken...");
Console.ReadKey();
}
}
Wenn Du richtig viel Speed nötig hast, verzichte auf den hübschen aber mit jeder Menge Overhead verbundenen Methodenaufruf. die Schleife funktioniert auch als Inlinecode. Das ist bis zu 80 mal schneller !
using System;
using System.Diagnostics;
class Prog{
public static void Main(string[] args){
ulong foo=Convert.ToUInt64("1000000000000000000000000000000000000000000000000000000011110000", 2);
Console.WriteLine("{0} = {1}" , foo , Convert.ToString((long) foo, 2).PadLeft(64, '0'));
Stopwatch stopWatch = Stopwatch.StartNew();
ulong oof=0;
for (int i=0;i < 64; ++i){ oof|=(((foo & (ulong)1 << i)<<63-i)>>i); } //als Inlinecode fällt der Overhead für Funktionsafruf weg...ca. 80mal schneller !
stopWatch.Stop();
Console.WriteLine( "{0} = {1}" , oof , Convert.ToString((long) oof, 2).PadLeft(64, '0'));
Console.WriteLine( "Executiontime : {0} Nanoseconds", (1000000000L / Stopwatch.Frequency) * stopWatch.ElapsedTicks);
Console.WriteLine("Taste drücken...");
Console.ReadKey();
}
}
ulong val = 38; // 00100110
string binaryString = Convert.ToString((ulong)val, 2);
string reversedBinaryString = new string(binaryString.Reverse().ToArray());
ulong reversedValue = Convert.ToUInt64(reversedBinaryString, 2); // 01100100
Linq ist dein Freund. ;-)
VG
in der zweiten zeile würde aber eine übergroße Zahl abgeschnitten ... weil long halt kleiner als ulong ist.
Hups, da hast du recht. Habe ich mich glatt vertippt. danke
Ich hab es so übernommen und in eine Methode gepackt. Ich hoffe sie ist schnell genug, es geht um einen Schachcomputer. Danke dafür^^
Gerne! :-)
Theoretisch wäre es mit einer normalen Schleife performanter, weil Linq immer ein wenig Overhead hat, aber es ist okay.
Das geht viel Effizienter mit ein Paar Bitoperationen AND, OR, SHL, SHR und Addition...
1'000'000 mal die Methode ausgeführt in 250ms... das ist wirklich ne gute Leistung!
Danke für die Hilfe!