Existe-t-il un moyen d'effectuer un décalage de bits circulaire en C# ?
-
09-06-2019 - |
Question
Je sais que ce qui suit est vrai
int i = 17; //binary 10001
int j = i << 1; //decimal 34, binary 100010
Mais si vous vous déplacez trop loin, les morceaux tombent au bout.L'endroit où cela se produit dépend de la taille de l'entier avec lequel vous travaillez.
Existe-t-il un moyen d'effectuer un décalage pour que les bits tournent de l'autre côté ?Je recherche une seule opération, pas une boucle for.
La solution
Si vous connaissez la taille du caractère, vous pouvez faire quelque chose comme :
uint i = 17;
uint j = i << 1 | i >> 31;
...qui effectuerait un décalage circulaire d'une valeur de 32 bits.
En généralisation au décalage circulaire vers la gauche de n bits, sur une variable b bits :
/*some unsigned numeric type*/ input = 17;
var result = input << n | input >> (b - n);
@Le commentaire, il semble que C# traite différemment le bit élevé des valeurs signées.J'ai trouvé des infos à ce sujet ici.J'ai également modifié l'exemple pour utiliser un uint.
Autres conseils
Il y a un an, je dois implémenter MD4 pour ma thèse de premier cycle.Voici mon implémentation du décalage de bits circulaire à l'aide d'un UInt32.
private UInt32 RotateLeft(UInt32 x, Byte n)
{
return UInt32((x << n) | (x >> (32 - n)));
}
Juste à titre de référence sur la façon de procéder, ces deux fonctions fonctionnent parfaitement pour faire tourner les bits d'un demi-mot :
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;
}
Il serait facile de l'étendre pour n'importe quelle taille donnée.
Je dois admettre que je viens de faire une recherche sur "C# bit rotate" et j'ai trouvé un lien vers une page avec une classe Java qui serait facilement adaptable en C#
J'ai aussi trouvé ceci dans Google Book qui est une fonction C++ avec un comportement similaire
L'application la plus célèbre est la solution au problème de Josèphe (tel que discuté dans Mathématiques concrètes, voir http://oeis.org/A006257).Il s’agit essentiellement d’un casse-tête sans applications évidentes.Dans cette vidéo, j'ai démontré les liens entre le problème de Josèphe de second ordre et les arbres équilibrés complets.Ce n'est pas encore une application, mais cela va légèrement dans la bonne direction.