lunes, 22 de julio de 2013

Kernighan_Ritchie_2_7.c (Inversión de bits)

______________________________________________________________________________________________________________________
2.7 Escriba una función invert(x, p,n) que regresa x con los n bits que principian en la posición p invertidos (esto es, 1 cambiado a 0 y viceversa), dejando los otros sin cambio.
______________________________________________________________________________________________________________________
Solución:
Primero, hay que dejar claro de lo que se trata éste programa. Para ésto, vamos a suponer que se recibe como entrada el número 90, y se quiere invertir los 3 bits que empiezan a partir del tercero. Lo que éste programa hace, se muestra en la siguiente figura:
Éste programa invierte los bits en rojo.
Se observa que hay sustitución de 1 por 0 a partir del tercer bit (el primero es el 0), por lo cual, el número se transforma en 42.

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 *                                                                  + 
 * Este programa recibe un entero sin signo e  invierte los n bits  + 
 * de dicho entero a   partir de la posicion p.                     +
 *                                                                  + 
 * Recibe x, que en binario es:                                     + 
 *                                                                  + 
 * |x|x|x|x|x|x|x|x|                                                + 
 * en donde x es 1 o 0                                              + 
 *                                                                  + 
 * tambien se recibe p (la posicion a partir de la cual se invertiran
 * los bits)  y n, el numero de bits a invertir. Por ejemplo, si se *
 * recibe x = 30, n = 2, p = 2.                                     *
 *             p                                                    *
 *   30 = |1|1|1|1|0|                                               * 
 *           2 1                                                    *
 *           n                                                      *
 *                                                                  *
 * Este programa inviert (cambia 1 por 0 y viceversa) los n bits    *
 * desde p. (la cuenta es hacia la izquierda, el primer bit es el 0 *
 * Así que para este caso el numero quedaria como:                  *
 *                                                                  *
 *        |1|0|0|1|0| = 18                                          *
 *                                                                  *
 * +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*******************************************************************+
 *                         ALGORITMO                                +
 * El problema se dividira en 2 partes principales                  +
 *                                                                  *
 * 1) Obtener el numero binario                                     *
 *                           p                                      *
 *    |0|0|0|0|...|0|x|x|...|x|0|...|0|                             *
 *                   p + n                                          *
 *                                                                  *
 *   donde los bits marcados con x son el complemento a 1 (inverso) *
 *   del numero entre 0 y p                                         *
 *                                                                  *
 * 2) Obtener el numero binario                                     *
 *                 p+n     n                                        *
 *    |x|x|x|...|x|0|0|...|0|x|....|x|                              *
 *                                                                  * 
 *    donde los bits marcados con x tienen el mismo valor que el    *
 *    numero original.                                              *
 *                                                                  *
 * El numero deseado se obtiene uniendo los que aparecen en 1) y 2) *
 * mediante el operador binario |                                   *
 * +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
#include <stdio.h>

///////////////////////////////////////////////////////////////////////////
//UNSIGNED
/////////////////////////////////////////////////////////////////////////// 
unsigned invert(unsigned x,int p,int n)

{ /* Abre invert */
return (((~(~0 << p + n) & (~0 << p)) & ~x) | ((( ~0 << p+n) | ~(~0 <<p)) & x) ); 
} /* Cierra invert */

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

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

printf("\nPor favor introduzca un entero sin signo: \n");
scanf("%d", &numero);

printf("\nPor favor introduzca el numero de bits a invertir: \n");
scanf("%d", &b);

printf("\nPor favor introduzca el bit a partir del cual se hara la inversion: \n");
scanf("%d", &a);

printf("\nEl numero, despues de invertir los %d bits a partir de la posicion ", a);
printf("%d es: %d\n", b, invert(numero, b,a));

return 0;
}  /* Cierra main*/

Related Posts Plugin for WordPress, Blogger...