Existe-t-il un moyen d'effectuer un décalage de bits circulaire en C#?

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 passez trop loin, les bits tombent à la fin. Où cela se produit est une question de la taille de l'entier avec lequel vous travaillez.

Existe-t-il un moyen d'effectuer un décalage de sorte que les bits tournent de l'autre côté? Je cherche une seule opération, pas une boucle for.

Answer 1

Si vous connaissez la taille du type, vous pouvez faire quelque chose comme:

uint i = 17; 
uint j = i << 1 | i >> 31; 

... exerceraient un décalage circulaire d'une valeur 32 bits.

Comme une généralisation à décalage circulaire gauche n bits, sur une variable bit b:

/*some unsigned numeric type*/ input = 17; 
var result = input << n | input >> (b - n); 

---

@The commentaire, il semble que C# ne traite le bit de valeurs signées différemment. J'ai trouvé quelques infos sur ce here. J'ai également changé l'exemple pour utiliser un uint.

Answer 2

Je dois admettre, je viens de faire une recherche pour "C# bit rotate" et a trouvé un link to a page with a Java class that would be easily adapted to C#

I also found this in Google Book which is a C++ function with similar behavior

Answer 3

Il y a un an, je l'ai à mettre en œuvre MD4 pour ma thèse de premier cycle. Ici, c'est ma mise en œuvre du décalage bit circulaire utilisant un UInt32.

private UInt32 RotateLeft(UInt32 x, Byte n) 
{ 
     return UInt32((x << n) | (x >> (32 - n))); 
} 

Answer 4

Tout comme référence sur la façon de le faire, ces deux fonctions fonctionnent parfaitement pour faire tourner les bits de 1/2word:

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 le prolonger pour une taille donnée.

Answer 5

L'application la plus célèbre est la solution au problème de Josephus (comme discuté dans Concrete Mathematics, voir http://oeis.org/A006257). C'est fondamentalement un puzzle sans applications évidentes. Dans this video, j'ai démontré des liens entre le problème de Josephus du second ordre et des arbres équilibrés complets. Ce n'est toujours pas une application, mais bouger légèrement dans la bonne direction.