Rotação direita de bits em C

Question

Estou trabalhando no exercício 2-8 em K&R, que nos pede para escrever uma função de rightrot(int x, int n)forma que todos os bits de xsejam deslocados n vezes para a direita, com os bits que caem da extremidade direita reaparecendo na extremidade esquerda.

Aqui está minha tentativa de solução em que eu mudo cada bit um por um:

int rightrot(int x, int n)
{
    int i, rmb;

    for(i = 0; i < n; ++i)
    {
        // get right-most bit
        rmb = x & 1;

        // shift 1 to right
        x = x >> 1;

        // if right-most bit is set, set left-most bit
        if (rmb == 1)
            x = x | (~0 ^ (~0 >> 1) );
    }

    return x;
}

Quando eu executar rightrot(122, 2), espero obter 94desde 122is 1111010e 94is 1011110. Em vez disso, eu entendo o 30que é 0011110. Claramente, meu método para definir o bit mais à esquerda não está funcionando como eu esperava. Alguém identificou um erro óbvio? Estou apenas aprendendo a capturar bits e coisas do gênero.

NOTA: eu peguei a técnica para definir o bit mais à esquerda deste post.

Answer 1

Vamos analisar (~0 ^ (~0 >> 1) ):

~0is -1
~0 >> 1is novamente -1, se o bit de sinal for 1rightshift preencherá os novos bits com 1s.
-1 ^ -1é 0.
x = x | 0é x.

A solução é que você deve usar tipos de dados não assinados se quiser fazer operações de bits.

Portanto, você deve usar a linha x = x | (~0u ^ (~0u >> 1) );
Para evitar outros problemas, o parâmetro xtambém deve ser unsigned int.

https://ideone.com/7zPTQk