Rotación de bits en C

Question

El problema: Ejercicio 2-8 de The C Programming Language, "Escribir una función rightrot (x, n) que devuelve el valor del entero x, rotado a la derecha por n posiciones."

He hecho esto de todas las maneras que sé cómo. Aquí está el problema que estoy teniendo. Tome un número determinado para este ejercicio, digamos 29, y gírelo a la derecha en una posición.
11101 y se convierte en 11110 o 30. Digamos por el argumento de que el sistema en el que estamos trabajando tiene un tamaño de tipo entero sin signo de 32 bits. Digamos además que tenemos el número 29 almacenado en una variable entera sin signo. En la memoria, el número tendrá 27 ceros por delante. Entonces, cuando giramos 29 a la derecha usando uno de varios algoritmos que muestro a continuación, obtenemos el número 2147483662. Evidentemente, este no es el resultado deseado.

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

Técnicamente, esto es correcto, pero yo estaba pensando que los 27 ceros que están frente a 11101 fueron insignificantes. También he intentado un par de otras soluciones:

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; 

Esta última y definitiva solución es aquel en el que pensé que lo tenía, voy a explicar donde fracasó una vez que llegar a la final. Estoy seguro de que se pueden ver mi error ...

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

Esta solución da la respuesta esperada de 30 que yo estaba buscando, pero si se utiliza un número para x como oh digo 31 (11111), a continuación, hay problemas, específicamente el resultado es 47, usando uno para n. No pensé en esto antes, pero si se usa un número como 8 (1000), entonces el caos. Solo hay un bit establecido en 8, por lo que el cambio seguramente será incorrecto. Mi teoría en este momento es que las dos primeras soluciones son correctas (principalmente) y me falta algo ...

Answer 1

Una rotación en modo bit siempre es necesariamente dentro de un número entero de un ancho determinado. En este caso, como supondrá un entero de 32 bits, 2147483662 (0b10000000000000000000000000001110) es la respuesta correcta; no estás haciendo nada mal!

0b11110 no se consideraría el resultado correcto con una definición razonable, ya que seguir girando hacia la derecha con la misma definición nunca devolvería la entrada original. (Tenga en cuenta que otro giro a derechas daría 0b1111, y continuando a girar que no tendría ningún efecto.)

Answer 2

Puede encontrar la ubicación del primer '1' en el valor de 32 bits mediante la búsqueda binaria. A continuación, tenga en cuenta el bit en la ubicación LSB, cambie el valor a la derecha por el número requerido de lugares, y coloque el bit LSB en la ubicación del primer '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

En mi opinión, el espíritu de la sección del libro que precede inmediatamente a este ejercicio tendría el lector hacer este problema sin saber nada sobre el tamaño (en bits) de números enteros, o cualquier otro tipo. Los ejemplos en la sección no requieren esa información; No creo que los ejercicios tampoco.

Independientemente de mi creencia, el libro aún no había introducido el operador sizeof en la sección 2.9, por lo que la única forma de determinar el tamaño de un tipo es contar los bits "a mano".

Pero no necesitamos molestarnos con todo eso. Podemos hacer rotación de bits en n pasos, independientemente de cuántos bits haya en el tipo de datos, girando bit por bit.

Utilizando solamente las partes del lenguaje que cubre el libro en la sección 2.9, aquí está mi implementación (con parámetros enteros, que devuelve un número entero, según lo especificado por el ejercicio): Loop n veces, x >> 1 cada iteración; si el antiguo bit bajo de x era 1, configure el nuevo bit 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; 
}