Gibt es eine Möglichkeit, eine zirkuläre Bitverschiebung in C# durchzuführen?
-
09-06-2019 - |
Frage
Ich weiß, dass Folgendes wahr ist
int i = 17; //binary 10001
int j = i << 1; //decimal 34, binary 100010
Wenn Sie jedoch zu weit verschieben, fallen die Teile am Ende ab.Wo dies geschieht, hängt von der Größe der Ganzzahl ab, mit der Sie arbeiten.
Gibt es eine Möglichkeit, eine Verschiebung durchzuführen, sodass sich die Bits auf die andere Seite drehen?Ich suche nach einer einzelnen Operation, nicht nach einer for-Schleife.
Lösung
Wenn Sie die Schriftgröße kennen, können Sie Folgendes tun:
uint i = 17;
uint j = i << 1 | i >> 31;
...Dies würde eine zirkuläre Verschiebung eines 32-Bit-Werts durchführen.
Als Verallgemeinerung zur zirkulären Verschiebung von n Bits nach links auf einer b-Bit-Variablen:
/*some unsigned numeric type*/ input = 17;
var result = input << n | input >> (b - n);
@Der Kommentar zeigt, dass C# das hohe Bit von vorzeichenbehafteten Werten unterschiedlich behandelt.Ich habe einige Informationen dazu gefunden Hier.Ich habe auch das Beispiel geändert, um ein uint zu verwenden.
Andere Tipps
Vor einem Jahr habe ich MD4 für meine Bachelorarbeit implementiert.Hier ist meine Implementierung der zirkulären Bitverschiebung mit einem UInt32.
private UInt32 RotateLeft(UInt32 x, Byte n)
{
return UInt32((x << n) | (x >> (32 - n)));
}
Nur als Referenz zur Vorgehensweise: Diese beiden Funktionen funktionieren perfekt zum Rotieren der Bits eines halben Wortes:
static public uint ShiftRight(uint z_value, int z_shift)
{
return ((z_value >> z_shift) | (z_value << (16 - z_shift))) & 0x0000FFFF;
}
static public uint ShiftLeft(uint z_value, int z_shift)
{
return ((z_value << z_shift) | (z_value >> (16 - z_shift))) & 0x0000FFFF;
}
Es wäre einfach, es auf jede beliebige Größe zu erweitern.
Ich muss zugeben, ich habe gerade nach „C# Bit Rotation“ gesucht und ein gefunden Link zu einer Seite mit einer Java-Klasse, die leicht an C# angepasst werden kann
Ich habe dies auch in Google Book gefunden, einer C++-Funktion mit ähnlichem Verhalten
Die bekannteste Anwendung ist die Lösung des Josephus-Problems (wie in Konkrete Mathematik besprochen, siehe http://oeis.org/A006257).Dies ist im Grunde ein Rätsel ohne offensichtliche Anwendungen.In Dieses Video, habe ich Zusammenhänge zwischen dem Josephus-Problem zweiter Ordnung und vollständig ausgeglichenen Bäumen aufgezeigt.Es handelt sich immer noch nicht um eine Anwendung, aber es geht leicht in die richtige Richtung.