Bit rotazione in C

Question

Il problema: Esercizio 2-8 del linguaggio di programmazione C, "Scrivi una funzione rightrot (x, n) che restituisce il valore dell'intero x, ruotato verso destra di n posizioni."

Ho fatto questo in ogni modo che so come. Ecco il problema che sto avendo. Prendi un dato numero per questo esercizio, diciamo 29, e ruotalo a destra di una posizione.
11101 e diventa 11110 o 30. Diciamo per il ragionamento che il sistema su cui stiamo lavorando ha un numero intero senza segno di 32 bit. Diciamo inoltre che abbiamo il numero 29 memorizzato in una variabile intera senza segno. In memoria il numero avrà 27 zeri prima di esso. Quindi, quando ruotiamo a destra uno dei due utilizzando uno dei numerosi algoritmi, il mio è pubblicato qui sotto, otteniamo il numero 2147483662. Questo ovviamente non è il risultato desiderato.

unsigned int rightrot(unsigned x, int n) { 
    return (x >> n) | (x << (sizeof(x) * CHAR_BIT) - n); 
} 

Tecnicamente, questo è corretto, ma stavo pensando che i 27 zeri che sono di fronte a 11101 erano insignificanti. Ho anche provato un paio di altre soluzioni:

int wordsize(void) { // compute the wordsize on a given machine... 
    unsigned x = ~0; 
    int b; 
    for(b = 0; x; b++) 
     x &= x-1; 
    return x; 
} 

unsigned int rightrot(unsigned x, int n) { 
    unsigned rbit; 
    while(n --) { 
     rbit = x >> 1; 
     x |= (rbit << wordsize() - 1); 
    } 
    return x; 

Questo ultimo e definitivo soluzione è quella in cui ho pensato che ho avuto, vi spiegherò dove non è riuscito una volta che arrivare alla fine. Sono sicuro che si vedrà il mio errore ...

int bitcount(unsigned x) { 
    int b; 
    for(b = 0; x; b++) 
     x &= x-1; 
    return b; 
} 

unsigned int rightrot(unsigned x, int n) { 
    unsigned rbit; 
    int shift = bitcount(x); 
    while(n--) { 
     rbit = x & 1; 
     x >>= 1; 
     x |= (rbit << shift); 
    } 
} 

Questa soluzione dà la risposta previsto di 30 che stavo cercando, ma se si utilizza un numero per x come oh dico 31 (11111), poi ci sono problemi, in particolare il risultato è 47, usando uno per n. Non ci avevo pensato prima, ma se un numero come 8 (1000) viene usato allora mayhem. C'è solo un bit impostato in 8, quindi il cambiamento sarà sicuramente sbagliato. La mia teoria a questo punto è che le prime due soluzioni sono corrette (principalmente) e mi manca solo qualcosa ...

Answer 1

Una rotazione bit a bit è sempre necessariamente all'interno di un numero intero di una determinata larghezza. In questo caso, poiché si presuppone un numero intero a 32 bit, 2147483662 (0b10000000000000000000000000001110) è effettivamente la risposta corretta; non stai facendo nulla di sbagliato!

0b11110 non sarebbe considerato il risultato corretto da nessuna definizione ragionevole, poiché continuare a ruotarlo a destra utilizzando la stessa definizione non restituirebbe mai l'input originale. (Si consideri che un altro rotazione a destra darebbe 0b1111, e continuando a ruotare che non avrebbe alcun effetto.)

Answer 2

È possibile trovare la posizione del primo '1' nel valore a 32 bit utilizzando la ricerca binaria. Quindi nota il bit nella posizione LSB, sposta a destra il valore per il numero richiesto di posizioni e inserisci il bit LSB nella posizione del primo '1'.

Answer 3

int bitcount(unsigned x) { 
    int b; 
    for(b = 0; x; b++) 
     x &= x-1; 
    return b; 
} 

unsigned rightrot(unsigned x,int n) { 
    int b = bitcount(x); 
    unsigned a = (x&~(~0<<n))<<(b-n+1); 
    x>> = n; 
    x| = a; 
} 

Answer 4

A mio parere, lo spirito della sezione del libro che precede immediatamente questo esercizio avrebbe il lettore di fare questo problema senza conoscere nulla sulla dimensione (in bit) degli interi o di qualsiasi altro tipo. Gli esempi nella sezione non richiedono quell'informazione; Non credo che neanche gli esercizi dovrebbero.

Indipendentemente dalla mia convinzione, il libro non aveva ancora introdotto l'operatore sizeof dalla sezione 2.9, quindi l'unico modo per calcolare la dimensione di un tipo è contare i bit "a mano".

Ma non abbiamo bisogno di preoccuparci di tutto questo. Possiamo eseguire la rotazione dei bit in n passi, indipendentemente da quanti bit ci sono nel tipo di dati, ruotando un bit alla volta.

Utilizzare solo le parti della lingua coperte dal libro fino alla sezione 2.9, ecco la mia implementazione (con parametri interi, restituendo un intero, come specificato dall'esercizio): Loop n volte, x >> 1 ogni iterazione; se il vecchio bit basso di x era 1, imposta il nuovo bit più alto.

int rightrot(int x, int n) { 
    int lowbit; 

    while (n-- > 0) { 
     lowbit = x & 1;   /* save low bit */ 
     x = (x >> 1) & (~0u >> 1); /* shift right by one, and clear the high bit (in case of sign extension) */ 
     if (lowbit) 
      x = x | ~(~0u >> 1); /* set the high bit if the low bit was set */ 
    } 

    return x; 
}