Rotazione a destra dei bit in C

Jan 03 2021

Sto lavorando all'esercizio 2-8 in K&R che ci chiede di scrivere una funzione in modo rightrot(int x, int n)tale che tutti i bit di xsiano spostati n volte a destra con i bit che cadono dall'estremità destra che ricompaiono all'estremità sinistra.

Ecco la mia soluzione tentata in cui sposto ogni bit uno per uno:

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 eseguo rightrot(122, 2), mi aspetto di ottenere 94dal momento che 122è 1111010ed 94è 1011110. Invece, capisco 30quale sia 0011110. Chiaramente, il mio metodo per impostare il bit più a sinistra non funziona come mi aspetto. Qualcuno ha notato un errore evidente? Sto solo imparando a catturare bit e simili.

NOTA: ho ottenuto la tecnica per impostare il bit più a sinistra da questo post.

Risposte

7 mch Jan 02 2021 at 23:21

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

~0è -1
~0 >> 1è di nuovo -1, se il bit di segno è 1righthift riempirà i nuovi bit con 1s.
-1 ^ -1è 0.
x = x | 0è x.

La soluzione è che dovresti usare tipi di dati non firmati se vuoi eseguire operazioni bit.

Quindi dovresti usare la riga. x = x | (~0u ^ (~0u >> 1) );
Per evitare altri problemi, anche il parametro xdovrebbe essere unsigned int.

https://ideone.com/7zPTQk