Kernighan_Ritchie_2.6 (Desplazamiento y sustitución de bits)

_______________________________________________________________________________________
2.6 Escriba una función setbits(x,p,n,y) que regresa x con los n bits que principian en la posición p iguales a los n bits más a la derecha de y, dejando los otros bits sin cambio.
_______________________________________________________________________________________
Solución:
Lo primero, igual que en este ejemplo, es entender bien el enunciado. Para ésto, vamos a visualizar la representación binaria de un par de números enteros positivos, digamos el 51 y el 42. Para estos números bastan seis bits. Vamos a suponer que el número de bits del primer entero (51) que vamos a cambiar por otros tantos del segundo (42) serán 3 (la variable n de setbits), y que además queremos cambiarlos a partir de la posición 1 (variable p ). Es importante recordar que la posición extrema derecha de un byte es el bit 0. Una vez establecido ésto, lo que el programa quiere es lo que se muestra en la siguiente figura:

La función setbits elimina los bits rojos y los sustituye por los azules.

La función setbits intercambia los 3 bits a partir del primero en la representación binaria de 51, con los tres primeros de la representación binaria de 42. El resultado es el número 53. Una vez entendida esta gráfica, es muy fácil entender la línea única de la función:

return (~((~0 << p) & ~(~0 <<(p+n))) & x ) | (~(~0 << p+n) & (y << p));

Esta línea, a pesar de parecer muy poco intuitiva, surge de una análisis simple.
1) Hacer 0 los bits entre p y p+n en el primer número. Ésto se logra creando una máscara que contenga 1s en todas las entradas, salvo en dichos bits. Esa máscara se crea con (~((~0 << p) & ~(~0 <<(p+n))) & x ). 2) Correr los bits del segundo número hasta la posición p. Ésto es, (y << p). 3) Hacer 0 los bits del segundo número, salvo en los intervalos 0-p y p+n hasta el último. Esto se logra con la máscara (~(~0 << p+n) & (y << p)). 4) Usar el operador | para lograr la unión de los bits distintos de 0 en de ambos números.
En los comentarios del programa se presenta éste mismo procedimiento como explicación del algoritmo.

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*
* Este programa recibe dos enteros sin signo. Regresa otro entero sin    *
* signo, el que se obtiene al cambiar n bits del primero, a partir de la *
* posicion p, con los n bits mas a la derecha del segundo.               *
*                                                                        *
* Lo que recibe: 4 enteros positivos.                                    *
* Lo que regresa: 1 entero positivo.                                     *
*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*                               ALGORITMO:                               *
*Establecer a o los n bits del primer numero, a partir de la posicion p  *
*                                                                        *
*                                              p                         *
*      | x | x | x | x | x | x | 0 | 0 | ... | 0 | x | x | x |           *
*                              -     n   --------                        *
*                                                                        * 
*Mover los bits del segundo numero p posiciones a la izquierda           *
*                                                                        *
*Establecer a 0 todos los bits (antes de la posicion p y despues de la n)*
*del segundo numero                                                      *
*                                                                        *
*                                  n             p                       *
*      | 0 | 0 | 0 | 0 | ... | 0 | x | x | ... | x | 0 | 0 | 0 |         *
*                                                                        *
*Con el operador o inclusivo | (puede ser el ^ o exclusivo) obtener el   *
*numero buscado.                                                         *
*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

#include 

///////////////////////////////////////////////////////////////////////
//setbits
///////////////////////////////////////////////////////////////////////

unsigned setbits( unsigned x, int p, int n, unsigned y)
{ /* Abre setbits */
 return (~((~0 << p) & ~(~0 <<(p+n))) & x ) | (~(~0 << p+n) & (y << p));
} /*Cierra setbits */

///////////////////////////////////////////////////////////////////////
//MAIN
///////////////////////////////////////////////////////////////////////

int main()
{  /* Abre main */
unsigned numero1, numero2;
int a, b;

printf("\nIntroduzca un entero sin signo: ");
scanf("%d", &numero1);

printf("\nIntroduzca un segundo entero sin signo: ");
scanf("%d", &numero2);

printf("\nIntroduzca el numero de bits a cambiar: ");
scanf("%d", &a);

printf("\nIntroduzca el bit a partir del cual se hara el cambio: ");
scanf("%d", &b);

printf("\nEl numero resultante es: %d\n", setbits(numero1, b, a, numero2));  

return 0; 
}  /* Cierra main */

ÉSte programa no tiene la precaución de verificar que los valores sean válidos. Por ejemplo, se podría introducir un valor de p mayor que el número total de bits. Ésto se puede evitar colocando algunos condicionales en la función main. No he querido colocarlos para no complicar el código. Es fácil hacerlo.
Aquí una ejecución, usando los números presentados anteriormente.

[hernandez@localhost Programas]$ ./a.out 

Introduzca un entero sin signo: 51

Introduzca un segundo entero sin signo: 42

Introduzca el numero de bits a cambiar: 3

Introduzca el bit a partir del cual se hara el cambio: 1

El numero resultante es: 53

__________________________________________________________________________________________
Esta entrada es parte de los problemas resueltos del libro El Lenguaje de Programación C de B. Kernighan y D. Ritchie
Entrada Anterior