Existe uma maneira de realizar uma mudança circular de bits em C#?

Question

Eu sei que o seguinte é verdade

int i = 17; //binary 10001
int j = i << 1; //decimal 34, binary 100010

Mas, se você mudar muito, os pedaços cairão no final.Onde isso acontece é uma questão do tamanho do número inteiro com o qual você está trabalhando.

Existe uma maneira de realizar uma mudança para que os bits girem para o outro lado?Estou procurando uma única operação, não um loop for.

Answer 1

Se você souber o tamanho do tipo, poderá fazer algo como:

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

...que executaria uma mudança circular de um valor de 32 bits.

Como uma generalização para o deslocamento circular para a esquerda de n bits, em uma variável de b bit:

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

---

@O comentário, parece que o C # trata a parte alta dos valores assinados de maneira diferente.Encontrei algumas informações sobre isso aqui.Também mudei o exemplo para usar um uint.

Answer 2

Há um ano implementei o MD4 em minha tese de graduação.Aqui está minha implementação de mudança circular de bits usando um UInt32.

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

Answer 3

Apenas como referência de como fazer isso, essas duas funções funcionam perfeitamente para girar os bits de 1/2 palavra:

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;
}

Seria fácil estendê-lo para qualquer tamanho.

Answer 4

Tenho que admitir, acabei de pesquisar por "rotação de bits C#" e encontrei um link para uma página com uma classe Java que seria facilmente adaptada para C#

Também encontrei isso no Google Book, que é uma função C++ com comportamento semelhante

Answer 5

A aplicação mais famosa é a solução para o problema de Josefo (conforme discutido em Matemática Concreta, veja http://oeis.org/A006257).Este é basicamente um quebra-cabeça sem aplicações óbvias.Em esse vídeo, demonstrei conexões entre o problema de Josefo de segunda ordem e árvores completamente balanceadas.Ainda não é um aplicativo, mas está se movendo um pouco na direção certa.