Circular Shift Integer

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

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

    entweder ich versteh das Problem nicht, oder es ist vorher noch niemand auf die idee gekommen:

    C#-Quellcode

    1. (input << rotate) | (input >> (32-rotate))

    Man verschiebe den input um 32-rotationen nach rechts und erhält somit die bits, die nach links über den rand geschoben werden angefangen beim niederwertigsten bit und verodert einfach mit der tatsächlichen rotation
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---

    ich hab mal 3dcliffs nach c# übertragen:

    C#-Quellcode

    1. uint[] Pow10 = new uint[] { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, uint.MaxValue };
    3. uint FloorLog10(uint n) {
    4. for (uint i = 0; ; ++i) if (n < Pow10[i]) return i;
    5. }
    7. uint RotateShift10(uint value, int shift) {
    8. if (shift < 0) shift = 9 + shift; // für negative shifts
    9. uint x = value / Pow10[shift];
    10. return x + (value % Pow10[shift]) * Pow10[FloorLog10(x)];
    11. }
    Und Benamung, weil Nomen est Omen!


    Es ergeben sich aber weitere Probleme: wenn etwa eine 0 an die erste Stelle rotiert wird, sinds auf einmal weniger Stellen, und also der Vorgang irreversibel.
    Daraus folgt: Der Algo ist prinzipiell falsch, und es muss immer eine feste Anzahl Stellen rotieren, und in uint sind max. 9 Stellen möglich.


    Beiträge zusammengefügt
    -Artentus

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Artentus“ ()

    ErfinderDesRades schrieb:

    wenn etwa eine 0 an die erste Stelle rotiert wird, sinds auf einmal weniger Stellen
    Dem ist aber beizukommen, indem man beim ToString-Aufruf für die Darstellung der Zahl genau so viele Stellen ausgeben lässt, wie es auch zu Beginn waren.
    Allerdings sind das immer mehr Gründe, einfach in einen String zu konvertieren und dann die Ziffern zu shiften. Stellen Zählen erfordert immer entweder FloorLog10 oder ToString und dann nehm ich doch lieber das letztere, wenn ich es gleich als Teil des Algos verwenden kann.

    ErfinderDesRades schrieb:

    ich hab mal 3dcliffs nach c# übertragen:

    C#-Quellcode

    1. uint[] Pow10 = new uint[] { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, uint.MaxValue };
    3. uint FloorLog10(uint n) {
    4. for (uint i = 0; ; ++i) if (n < Pow10[i]) return i;
    5. }
    7. uint RotateShift10(uint value, int shift) {
    8. if (shift < 0) shift = 9 + shift; // für negative shifts
    9. uint x = value / Pow10[shift];
    10. return x + (value % Pow10[shift]) * Pow10[FloorLog10(x)];
    11. }
    Und Benamung, weil Nomen est Omen!


    Es ergeben sich aber weitere Probleme: wenn etwa eine 0 an die erste Stelle rotiert wird, sinds auf einmal weniger Stellen, und also der Vorgang irreversibel.
    Daraus folgt: Der Algo ist prinzipiell falsch, und es muss immer eine feste Anzahl Stellen rotieren, und in uint sind max. 9 Stellen möglich.


    Beiträge zusammengefügt
    -Artentus

    Sofern die Zahl aber keine 0 enthält sollten die Rotationsachse problemlos funktionieren, oder?
    C# Developer
    Learning C++

    jo - aber was noch auftreten kann ist, dass die Rotation bei großen Zahlen einen Overflow herbeiführt, also wenn 1000000009 zu 9100000000 rotiert machts auch peng.

    Aber wie wolltest du das denn auch bewerkstelligen, dass die Zahl keine 0 enthält, das wird doch mindestens nochmal so'n Heckmeck, dagegen abzusichern.

    ErfinderDesRades schrieb:

    jo - aber was noch auftreten kann ist, dass die Rotation bei großen Zahlen einen Overflow herbeiführt, also wenn 1000000009 zu 9100000000 rotiert machts auch peng.

    Habs noch n bisschen verfeinert :

    C#-Quellcode

    1. ​static uint[] Pow10 = new uint[] { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, uint.MaxValue };
    3. static uint RotateShift10(uint value, int shift)
    4. {
    5. int r = (int)Math.Floor(Math.Log10(value) + 1);
    6. while (r < shift)
    7. shift = shift - r;
    8. if (shift < 0) shift = 9 + shift;
    9. uint x = value / Pow10[shift];
    10. uint i = 0;
    11. while (true)
    12. {
    13. if (x < Pow10[i])
    14. return x + (value % Pow10[shift]) * Pow10[i];
    15. i += 1;
    16. }
    17. }


    Für den von dir genannten Fall hab ich allerdings keine Lösung, is aber auch unwahrscheinlich, da ich ehr mit kleineren Zahlen hantiere ;)
    C# Developer
    Learning C++

    Okay, hier ist nochmal mein Finaler Algorithmus, diverse Math-Operationen wurden durch Bitwise Oeprationen ersetzt, und auch fälle mit negativem/positivem shift
    bzw einem Shift der länger ist als die Zahl selbst werden behandelt.

    ACHTUNG : Es wird davon ausgegangen das die Zahl keine 0-en enthällt.

    C#-Quellcode

    1. ​static uint RotateShift2(uint v, int b)
    2. {
    3. int n = 0;
    4. uint c = v;
    5. while (c != 0)
    6. {
    7. c /= 10;
    8. n++;
    9. }
    10. b %= n;
    11. if (b < 0)
    12. {
    13. b += n;
    14. }
    15. long e = 1L;
    16. long f = 10L;
    17. for (int i = b; i > 0; i >>= 1)
    18. {
    19. if ((i & 1) == 1)
    20. e *= f;
    21. f *= f;
    22. }
    23. uint x = (uint)e;
    24. long z = 1L;
    25. long p = 10L;
    26. for (int j = n - b; j > 0; j >>= 1)
    27. {
    28. if ((j & 1) == 1)
    29. z *= p;
    30. p *= p;
    31. }
    32. uint w = (uint)z;
    33. return v % x * w + v / x;
    34. }
    C# Developer
    Learning C++

    Was machst Du eigentlich, dass Du so auf Performance drücken musst, dass Du so ein Monstrum von Code der super simplen ToString-Variante vorziehst?
    Bei meinem Test ist Deine Variante nur knapp doppelt so schnell.

    Deine Variante

    C#-Quellcode

    1. StopWatch.Start();
    2. for (int Index = 0; Index < NumberOfNumbers; Index++)
    3. {
    5. uint v = Numbers[Index];
    6. int b = Shifts[Index];
    7. int n = 0;
    8. uint c = v;
    9. while (c != 0)
    10. {
    11. c /= 10;
    12. n++;
    13. }
    14. b %= n;
    15. if (b < 0)
    16. {
    17. b += n;
    18. }
    19. long e = 1L;
    20. long f = 10L;
    21. for (int i = b; i > 0; i >>= 1)
    22. {
    23. if ((i & 1) == 1)
    24. e *= f;
    25. f *= f;
    26. }
    27. uint x = (uint)e;
    28. long z = 1L;
    29. long p = 10L;
    30. for (int j = n - b; j > 0; j >>= 1)
    31. {
    32. if ((j & 1) == 1)
    33. z *= p;
    34. p *= p;
    35. }
    36. uint w = (uint)z;
    37. uint Result = v % x * w + v / x;
    38. }
    39. StopWatch.Stop();



    ToString-Variante

    C#-Quellcode

    1. StopWatch.Start();
    2. for (int Index = 0; Index < NumberOfNumbers; Index++)
    3. {
    5. uint Number = Numbers[Index];
    6. int Shift = Shifts[Index];
    7. if (Shift == 0)
    8. {
    9. uint Result = 0;
    10. }
    11. else
    12. {
    13. string StringRepresentation = Number.ToString();
    14. int RemainingLength = StringRepresentation.Length - Shift;
    15. uint Result = uint.Parse(StringRepresentation.Substring(RemainingLength) + StringRepresentation.Substring(0, RemainingLength));
    16. }
    17. }
    18. StopWatch.Stop();



    2240999 Ticks pro Sekunde
    10000000 Zahlen
    Komplizierter Algorithmus: 3476647 Ticks, 1.5 s gesamt, 0.15 µs pro Zahl
    ToString: 7426528 Ticks, 3.3 s gesamt, 0.33 µs pro Zahl

    Also warum versuchst Du, Performance auf Kosten der Lesbarkeit rauszuschlagen?
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    @Niko Ortner : Schlichtweg aus dem Grund das mich das rumbasteln mit Algorithmen bits bytes und zahlen interessiert ziehe ich die Komplexe Variante vor.
    Auch wenn man das ganze per Strings leserlicher machen kann, so finde ich doch gern alternativen:)
    Zudem kann man meinen finalen Algo vllt sogar noch ein bisschen weiter optimieren, die letzten zwei loops sind redundant, allerdings weiß ich nicht wie ich das ganze mit einem loop ohne outlining lösen soll da die Werte ja geändert werden.
    Muss da nochmal ein bisschen weiter rum basteln.
    Wer weitere Optimierungsideen hat kann sie mir gerne mitteilen :)
    C# Developer
    Learning C++