Rotazione a destra dei bit in C
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 x
siano 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 94
dal momento che 122
è 1111010
ed 94
è 1011110
. Invece, capisco 30
quale 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
Analizziamo (~0 ^ (~0 >> 1) )
:
~0
è -1
~0 >> 1
è di nuovo -1
, se il bit di segno è 1
righthift riempirà i nuovi bit con 1
s.
-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 x
dovrebbe essere unsigned int
.
https://ideone.com/7zPTQk