Rotation droite des bits en C

Jan 03 2021

Je travaille sur l'exercice 2-8 dans K&R qui nous demande d'écrire une fonction rightrot(int x, int n)telle que tous les bits de xsont décalés n fois vers la droite avec les bits qui tombent de l'extrémité droite réapparaissant à l'extrémité gauche.

Voici ma tentative de solution dans laquelle je décale chaque bit un par un:

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

Quand j'exécute rightrot(122, 2), je m'attends à obtenir 94depuis 122est 1111010et 94est 1011110. Au lieu de cela, je comprends 30ce qui se trouve être 0011110. De toute évidence, ma méthode pour définir le bit le plus à gauche ne fonctionne pas comme je m'y attendais. Quelqu'un a-t-il repéré une erreur évidente? J'apprends juste à capturer des bits et autres.

REMARQUE: j'ai obtenu la technique pour définir le bit le plus à gauche de ce post.

Réponses

7 mch Jan 02 2021 at 23:21

Analysons (~0 ^ (~0 >> 1) ):

~0C'est -1
~0 >> 1encore une fois -1, si le bit de signe est 1droit, remplira les nouveaux bits avec 1s.
-1 ^ -1est 0.
x = x | 0est x.

La solution est que vous devez utiliser des types de données non signés si vous souhaitez effectuer des opérations sur bits.

Vous devez donc utiliser la ligne x = x | (~0u ^ (~0u >> 1) );
Pour éviter d'autres problèmes, le paramètre xdoit également être unsigned int.

https://ideone.com/7zPTQk