miércoles, 28 de agosto de 2013

La instrucción goto y etiquetas

El lenguaje C proporciona la instrucción goto como una forma de transferir el control del programa. Por ejemplo considere el siguiente código

/*+++++++++++++++++++++++++++++++++++++++++++++++++
+ Este programa hace uso de la proposicion goto   +
**************************************************/

#include <stdio.h>

int main()

{ /* Abre main */
printf("\nEsta es la primera instruccion del programa.");

/* Se usa goto */
goto instruccion;

printf("\nEsta es la segunda instruccion del programa.");

instruccion:
printf("\nEsta es la tercera instruccion del programa.");
printf("\nEsta es la cuarta instruccion del programa.\n");
return 0;

} /* Cierra main */


Aquí se presenta una instrucción goto seguido del nombre de una etiqueta llamada instruccion. La función de goto es omitir la realización de todas las líneas que hay entre goto y la etiqueta. Una ejecución del programa es la siguiente:

hernandez@miMaquina ~/Programas $ ./a.out 

Esta es la primera instruccion del programa.
Esta es la tercera instruccion del programa.

Esta es la cuarta instruccion del programa.

Observe que la segunda línea printf no se imprime, debido al uso de la etiqueta goto. A partir de donde está la etiqueta, se reinicia la ejecución del programa en el orden en que aparecen las líneas de código. El uso de goto puede ser muy cómodo, pero es muy poco recomendado. La programación estructurada ha venido a ser sinónimo de "programación sin goto". En el pasado los ingenieros y desarrolladores se dieron cuenta de que los programas con goto eran más difíciles de mantener y depurar, debido a que no hay un orden en las instrucciones.

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 encla 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*/

miércoles, 8 de mayo de 2013

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

Un ejemplo usando operadores para manejo de bits

Éste programa usa la función getbits (sección 2.9 de El Lenguaje de Programación C, de Kernighan y Ritchie). La razón para ponerlo aquí es que no es claro a primera vista, al menos para mí, lo que esa función hace. En la sección 2.9 se estudian los operadores binarios y getbits hace uso de &, el and de bits; <<, corrimiento a la izquierda; >>, corrimiento a la derecha y ~, complemento a uno, para hacer lo siguiente:
"regresa el campo de n bits de x (ajustado a la derecha) que principia en la posición p. Se supone que la posición del bit 0 está en el borde derecho y que n y p son valores positivos adecuados. Por ejemplo, getbits(x,4,3) regresa los tres bits que están en la posición 4, 3 y 2 ajustados a la derecha."

No soy el único que encuentra difícil la redacción (la original, en inglés) del libro de Kernighan y Ritchie. He encontrado varias páginas y foros en los que la gente se pregunta qué quisieron decir en tal o caul parte. Afortunadamente, aquí se puede entender sin ambigûedades.
Vamos a suponer que las variables son éstas: x = 179, p = 4 y n = 3. Para hacer ésto más fácil, la representación binaria de 179 es la siguiente:

Representación binaria de 179, en 10 bits.
Lo que hace nuestra función es mostrar dejar únicamente los 3 bits que comienzan a partir de la posición 4 (la posición extrema derecha es la 0). Éstos bits son 1 0 0, y deben aparecer corridos hacia la derecha. Todos los demás bits deben estar establecidos en 0.
El número 179 después de aplicar getbits.
El corazón del programa es, desde luego, la instrucción

return ((x >> (p+1-n)) & ~(~0 << n));

Ésta línea se divide en dos partes, separadas por el operador &. La instrucción x >> (p+1-n) corre hacia la derecha (4+1-3 = 2) bits. Esto es, se eliminan los bits 0 y 1 (ambos con 1), que deja el número binario 0000101100.
~(~0 << n) crea una máscara de bits. ~0 genera el binario 1111111111 y ~0 << n, con n = 3, corre hacia la izquierda el primer bit y llena los espacios con 0. Se produce entonces el número binario 1111111000. Finalmente, ~(~0 << n) crea el binario 0000000111. Esta es la máscara. Aplicando el operador & a 0000101100 y 0000000111 produce 0000000100. Este número es 4. Es precisamente lo que se obtiene al ejecutar el programa
/*++++++++++++++++++++++++++++++++++++++++++++
 * "regresa el campo de n bits de x (ajustado *
 * a la derecha) que principia en la posicion *
 * p. Se supone que la posicion del bit 0     *
 * esta en el borde derecho y que n y p son   *
 * valores positivos adecuados" Kernighan-    *
 * Ritchie                                    *
 *+++++++++++++++++++++++++++++++++++++++++++*/
#include 

///////////////////////////////////////
// FUNCION GETBITS
// ////////////////////////////////////

unsigned getbits(unsigned x, int p, int n)
{ /* Abre getbits*/
 
return ((x >> (p+1-n)) & ~(~0 << n));

} /*Cierra getbits*/

////////////////////////////////////////
//FUNCION MAIN
////////////////////////////////////////

int main()
{ /* Abre main*/

unsigned numero;
int a, b;

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

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

printf("\nIntroduzca el numero de bit a partir del cual se mostraran: ");
scanf("%d", &a);

printf("El numero es: %d\n", getbits(numero,a,b));

return 0;
}/*Cierra main*/
Aquí la ejecución

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

Introduzca un entero sin signo: 179

Introduzca el numero de bits a mostrar: 3

Introduzca el numero de bit a partir del cual se mostraran: 4
El numero es: 4

jueves, 2 de mayo de 2013

De decimal a octal con una función recursiva

Éste programa es una consecuencia natural de la entrada anterior. Es tan simple como cambiar 2 por 8. En realidad, como puede verse, éste procedimiento sirve para convertir de decimal a cualquier base posicional entre 2 y 9. También es posible usarlo para una conversión a sistema hexadecimal.

#include <stdio.h>

/*////////////////////////////////////
 * Funcion Octal                     *
 *///////////////////////////////////*/

void Octal( int x)

{  /* Abre Octal*/
if ( x != 0 )
{ /* Abre if*/
Octal(x/8);

printf("%d\t", x%8);
} /*Cierra if */

else;
 /*printf("0\n");*/

}  /*Cierra Octal*/

/****************************************
 * main                                 *
 ***************************************/
int main()

{  /*Abre main */
 int num; 

 printf("\nIntroduzca un numero entero: ");
 scanf("%d", &num);

 Octal(num);
 printf("\n");

 return 0;
}  /*Cierra main */


Y aquí una ejecución, con el número 100 como entrada

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

Introduzca un numero entero: 100                                                     
1       4       4                   


Related Posts Plugin for WordPress, Blogger...