Circular Shift Integer

  • C#
  • .NET (FX) 1.0–2.0

Es gibt 30 Antworten in diesem Thema. Der letzte Beitrag () ist von Rikudo.

    Circular Shift Integer

    18462995

    Hallo Community,

    Ich bin wieder am bisschen mit Bits, Bytes und Zahlen am werkeln und komme nicht (richtig) weiter.
    Ziel ist es ein Circular Shift, bzw eine Rotation eines Int32 durchzuführen.
    Achtung : Ich meine keinen Circular Shift der bits in einer Zahl, sondern die digits selbst.
    Dabei soll als input die Zahl und ein weiterer int für die Anzahl der Verschiebungen nach rechts.

    z.B.

    C#-Quellcode

    1. Input : 18462995;
    2. Rot : 3;


    Der Output richtige hier wäre

    C#-Quellcode

    1. 99518462
    da eben alle Digits dreimal nach rechts verschoben werden, und damit
    keine digits rechts rausgeschoben werden und verloren gehen, werden sie links wieder angehängt.
    Ein sogenannter Circular Shift, - nur eben mit der Zahl selbst statt den Bits.
    Noch ein paar Einschränkungen:
    - Keine Linq Lösungen
    - Kein .ToString()/String Konvertierungs-Lösungen.

    Ich möchte das ganze wenn möglich mit reiner Mathematik ein paar Variablen und paar arithmetischen bzw Bitshift operationen
    erreichen, falls das möglich ist.

    Wie würdet ihr das effizient machen?
    C# Developer
    Learning C++

    Rikudo schrieb:

    Kein .ToString()/String Konvertierungs-Lösungen.
    Es ist immer die Frage, ob es diesen Aufwand wert ist. String-Operationen sind im Framework extrem optimiert und für dein Vorhaben sind lediglich 2 Substring-Aufrufe erforderlich. Außerdem ist es effektiv ein Zweizeiler.

    Arithmetisch wäre folgendes zu tun:
    1. Zahl durch 10^rot teilen, um die vorderen Ziffern zu erhalten.
    2. Größenordnung des Ergebnisses bestimmen (FloorLog10).
    3. Ergebnis wieder mit 10^rot multiplizieren und dieses Ergebnis von der Zahl abziehen, um die hinteren Ziffern zu erhalten.
    4. Die hinteren Ziffern mit der Größenordnung multiplizieren und zu den vorderen Ziffern addieren.
    Zehnerpotenzen lassen sich nicht durch Bitshifting und dergleichen darstellen, heißt da kommen schon einige Operationen zusammen, selbst wenn du Ganzzahlpotenzen effizient implementierst. Es ist sehr wahrscheinlich, dass die Lösung mit ToString schnell genug ist, um den Aufwand nicht zu rechtferigen.

    Artentus schrieb:

    Potenz. Bitoperationen kannst du bei Basis 10 vergessen.

    Also, ich versuche jetzt, entsprechend deiner Step-By Step Anleitung das ganze irgendwie zusammenzubasteln:

    C#-Quellcode

    1. ​private static int RotateInteger(int number, int rot)
    2. {
    3. double a = number / Math.Pow(rot, 10);
    4. double b = Math.Floor(a);
    5. double c = b * (Math.Pow(rot, 10));
    6. int d = number - (int)c;
    7. int f = d * (int)b;
    8. // .. eh wut?
    9. }


    Allerdings blicke ich nicht was jetzt meine vorderen Ziffern sind? ;o
    Die hitneren Ziffern sollte, - falls das soweit passt in

    C#-Quellcode

    1. int d
    stecken, oder?
    C# Developer
    Learning C++

    Immer Ganzzahlarithmetik benutzen, ansonsten ist das mit Sicherheit langsamer. Bedeutet auch, du musst Math.Pow und den FloorLog selber implementieren (Exponentiation by squaring für Potenzen, den FloorLog kenn ich nicht effizient auswendig, @~blaze~ hatte da mal nen Algo).
    Außerdem hast du ohnehin Basis und Exponenten vertauscht.

    In a stünden bei deinem Code jetzt diejenigen Ziffern, die in der Ausgangszahl vorne und in der neuen Zahl hinten stehen.
    Bei dir ist d die andere Hälfte der Zahl. Jedoch stehen diese Ziffern jetzt halt hinten, du musst sie also noch um x Stellen nach vorne verschieben, wobei x die Anzahl der Ziffern in a ist. Diese erhaltst du eben mit dem genannten FloorLog10.

    petaod schrieb:

    Rikudo schrieb:

    double
    Ist die Vorgabe Ganzzahl oder Gleitkomma?

    Rikudo schrieb:

    Math.Pow, Math.Floor
    Wolltest du nicht ohne .Net auskommen?

    Edit: OK, zweiter :(

    Naja, soweit es geht schon alles selbstmachen.
    Aber ne PotenzFunktion selbst zu schreiben is jetzt nicht das schwere das kann ich später immer noch ändern.
    Solange kann ich auch Math.Floor bzw Math.Pow verwenden.
    Ansonsten möchte ich die ganze Arithmetic soweit es geht schon selbst schreiben.
    C# Developer
    Learning C++

    Das Äquivalent zum FloorLog10 wäre Math.Floor(Math.Log10(x)).
    Die Anzahl der Ziffern einer Zahl x berechnet sich aus FloorLog10(x) + 1. Allerdings wird der Zahl 0 auch eine Ziffer angerechnet, das willst du in dem Fall aber nicht, bedeutet, du musst diesen Sonderfall abfragen, falls er auftreten kann.

    @Artentus : Ich bin jetzt soweit:

    C#-Quellcode

    1. ​ private static void RotateInteger(int number, int rot)
    2. {
    3. double a = number / Math.Pow(10, rot);
    4. double b = Math.Floor(a);
    5. double c = b * (Math.Pow(10, rot));
    6. int d = number - (int)c;
    7. int f = d * (int)b;
    8. int g = f + (int)b;
    9. double x = Math.Ceiling(Math.Log10(a) + 1);
    10. // was ist der nächste schritt?
    11. }


    Stimmt das soweit?
    Ja die vorderen Ziffern und die Hinteren sind in den jeweiligen variablen gespeichert, habe ich mitm Debugger geprüft.
    C# Developer
    Learning C++

    @Artentus : Ah, okay, das sieht schonmal recht vernünftig aus. ^^
    Allerdings fällt mir jetzt auch auf was du mit dem 0-Spezialfall meinst.

    C#-Quellcode

    1. ​ private static int RotateInteger(int number, int rot)
    2. {
    3. double a = number / Math.Pow(10, rot);
    4. double b = Math.Floor(a);
    5. double c = b * (Math.Pow(10, rot));
    6. int d = number - (int)c;
    7. double x = Math.Ceiling(Math.Log10(a) + 1);
    8. int res = (int)(b + d * Math.Pow(10, x));
    9. return res;
    10. }


    In folgendem Beispiel :

    C#-Quellcode

    1. ​ static void Main(string[] args)
    2. {
    3. int a = 123487;
    4. int b = RotateInteger(a, 2);
    5. Console.WriteLine(b);
    6. Console.ReadKey();
    7. }


    ist b nämlich 8701234, anstatt 871234.
    Die Frage ist wie ich diesen Fall händeln soll.
    Ich darf die null ja nicht einfach entfernen, den wenn meine Ausgangszahl womölich auch nullen beinhaltet, kommt das zu schwerwiegenden Fehlern.
    C# Developer
    Learning C++

    Artentus schrieb:

    Das ist nicht der Fehler, von dem ich sprach. Der hier entsteht, weil du in Zeile 7 CeilingLog anstatt FloorLog verwendest.

    Okay, hab das korrigiert.
    Irgendwe gehen jedoch bei großen shifts ein paar digits verloren.. ;o
    C# Developer
    Learning C++

    Artentus schrieb:

    Wie groß? Größer als die Anzahl der Ziffern?
    Ich schrieb bereits, dass diese Sonderfälle nicht abgedeckt sind.

    Ja, genau.
    Willst du mir auch erklären wie man einen solcehn Fall abfängt, bzw ihn entsprechend richtig handelt?
    C# Developer
    Learning C++

    Wenn x die Anzahl der Ziffern der Ausgangszahl ist, gilt:
    Jeder Wert größer gleich x kann auf einen Wert zwischen 0 und ausschließlich x abgebildet werden, der das exakt gleiche Ergebnis liefert. Bei einem 10 Zeichen langen String ist z.B. ein Shift um 15 Zeichen äquivalent zu einem Shift um 5 Zeichen. Auszurechnen ist die neue Rotation einfach nach rot = rot mod x.
    Wenn danach rot == 0 kannst du einfach die Ausgangszahl zurückgeben.
    Wenn rot < 0, müsstest du eine LeftShift-Funktion aufrufen, weil negativer RightShift einem LeftShift entspricht.

    Hier mal meine Quick&Dirty-Implementation in C. log10 sollte man noch mit binary search verfeinern.
    n muss hier echt kleiner sein als 10^9.

    C-Quellcode

    1. ​unsigned pow[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    3. unsigned log10(unsigned n) {
    4. for(unsigned i = 0; i < (sizeof(pow) / sizeof(pow[0])); ++i) {
    5. if(n < pow[i]) {
    6. return i;
    7. }
    8. }
    9. return 0;
    10. }
    12. unsigned dshift(unsigned n, unsigned s) {
    13. s = s % 10;
    14. unsigned x = n / pow[s];
    15. return x + (n % pow[s]) * pow[log10(x)];
    16. }

    Deswegen schrieb ich ja, n < 10^9 :P

    Für BigInteger könnte man so etwas machen:

    C#-Quellcode

    1. private List<BigInteger> pow = new List<BigInteger>() {1, 10, 100, 1000};
    3. private void CheckPow(BigInteger n, UInt32 s) {
    4. for(int i = pow.Count - 1; pow[i] < n || i < s; ++i) {
    5. pow.Append(pow[i] * 10);
    6. }
    7. }
    9. public BigInteger DigitShift(BigInteger n, UInt32 s) {
    10. CheckPow(n, s);
    11. // ...
    12. }


    Ob das sinnvoll ist, sei aber mal dahin gestellt.

    Und um beim Standard zu bleiben sollte es auch unsigned long im obigen C-Code sein.

Facebook
Telefonspende