Ror / Rol Operation für Int32/Int64

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

Es gibt 7 Antworten in diesem Thema. Der letzte Beitrag () ist von jvbsl.

    Ror / Rol Operation für Int32/Int64

    Hey,

    Ich bin dabei für Int32 und Int64 jeweils eine Ror bzw eine Rol Funktion zu schreiben.
    Das bedeutet nichts anderes als RotateRight bzw RotateLeft und ist anders als normale Shift-Operationen zyklisch, man hat also keinen Informationsverlust.
    Hier ein Bild zur Verdeutlichung:



    Das wäre RotateLeft, RotateRight ist dementsprechend das gleiche in die andere Richtung.

    Hier ist mein Ansatz (der teilweise funktioniert):

    C#-Quellcode

    1. public static int ROL32(int value, int count)
    2. {
    3. return (value << count) | (value >> (32 - count));
    4. }
    5. public static int ROR32(int value, int count)
    6. {
    7. return (value >> count) | (value << (32 - count));
    8. }


    Das Problem ist, nicht für alle Zahlen haut das hin. Insbesondere die negativen Werte und die Maxwerte machen Probleme.
    Eigentlich ergibt das keinen Sinn da man ja nur bits verschiebt. Hier mal mein Unit-Test:

    C#-Quellcode

    1. public class Tests
    2. {
    3. private static readonly Random Random = new Random();
    4. [Theory]
    5. [InlineData(0)]
    6. [InlineData(1)]
    7. [InlineData(-1)]
    8. [InlineData(123456)]
    9. [InlineData(-123456)]
    10. [InlineData(int.MaxValue)]
    11. [InlineData(int.MinValue)]
    12. public void TestRor(int input)
    13. {
    14. int shiftCount = Random.Next(0, 32);
    15. int leftShifted = (input << shiftCount) | (input >> (32 - shiftCount));
    16. int rightShifted = ROR(leftShifted, shiftCount);
    17. Assert.Equal(rightShifted, input);
    18. }
    19. public static int ROR(int value, int count)
    20. {
    21. return (value >> count) | (value << (32 - count));
    22. }
    23. }


    Results (manchmal failen 3, manchmal 4):


    Was habe ich übersehen, weshalb failen manche der Werte?
    C# Developer
    Learning C++
    @Rikudo Ich würde die Probanden vorher nach UInt /ULong konvertieren (und hinterher zurück).
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    1) Nicht-deterministische Unit-Tests sind in den meisten Fällen wertlos

    2) In dem beschriebenen Fall kein Problem, aber falls nicht bekannt zur Info:
    Bei Int32-Shifts werden in C# stets nur die 5 least significant bits des zweiten Operanden verwendet.
    D.h. x << y == x << (y & 0x1F), insbesondere x << y == x für y = 32

    3) Siehe Post von RodFromGermany
    Negative Werte sind anders zu behandeln, weil das MSB immer auf 1 stehen bleiben muss.
    Lass dir die Hex- oder Bin-Werte von negativen Zahlen mal ausgeben, dass weisst du was ich meine.
    Ansonsten siehe Post 2 von RodFromGermany und teste dein Programm erst einmal mit UInt und ULong.
    An manchen Tagen gibt es zu allem Überfluss auch noch Ärger!
    Danke schonmal für eure Tipps @3daycliff @RodFromGermany @Rainman
    Das macht Sinn. Das heißt das meine Implementation quasi ausschließlich für uint zu verwenden ist.
    Wenn ich euch richtig verstanden habe muss ich, um signed int Werte zu unterstützen, das MSB nicht in den Shift mit einbeziehen.

    Folgendes Beispiel:
    Input: -123456 das wäre in Binary: 11111111111111100001110111000000 wobei das Rote bit das MSB darstellt (?)
    Bei einem Left Shift von 15 wäre das dann 10001110111000000111111111111110. D.h. ich rotiere nur die rechten 31 bits und das ganze linke bleibt einfach?

    Wie exclude ich das MSB bei meinen Shifts? @3daycliff kannst du dein Snippet bei 2) etwas genauer erklären ich steig da nicht ganz durch.
    C# Developer
    Learning C++

    Rikudo schrieb:

    Wie exclude ich das MSB bei meinen Shifts?
    Hin mit AND ~MSB, zurück mit OR MSB, natürlich vorher abfragen, wenn nicht gesetzt, kannst Du das OR weglassen.
    MAB ist entsprechend für die Länge Deines Datentyps anzupassen.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Den "klassischen" circular shift den man üblicherweise sieht ist AFAIK immer auf unsigned Integer basierend.
    Wenn du auch vorzeichenbehaftete Integer unterstützen möchtest, musst du eine saubere Definition liefern.

    Durch einen uint-cast wird die Interpretation der Bitfolge ignoriert und es werden - wie in dem Schaubild oben - nur die Bits rotiert.
    Was m.M.n. Sinn ergibt, bedeutet aber halt, dass das Vorzeichen wechseln kann.

    Zu dem Snippet: Ist wie gesagt für deinen Fall nicht relevant.
    In C# gilt bei einem int x << 1 == x << 33 == x << 6625 == x << 1923056609, da vom zweiten Operanden immer nur die 5 least significant Bits (00001) verwendet werden.
    Insbesondere ist halt x << 32 nicht 0 sondern x, da 32 (dec) = 10 0000 (bin) und x nur um 0 0000 Bits "geshiftet" wird.
    github.com/dotnet/coreclr/pull/1830

    Wie du siehst und wie auch bereits benannt eben auf uint... Aber sollte dann eben sogar vom Jitter(zumindest .net Core 64Bit) zu ROL/ROR Maschinencode übersetzt werden...
    Ich wollte auch mal ne total überflüssige Signatur:
    ---Leer---