0
Ejemplos capítulo 18 y 19
Ejemplo 19.1
Siguiendo con el problema de trabajar con enteros grandes, y aprovechando que ya sabemos manejar operadores de bits, veamos otra alternativa a la de los ejemplos del capítulo 9.
Hay una solución intermedia, que consiste en usar codificación BCD. No aprovecha tanto la capacidad de almacenamiento como la forma binaria pura y dificulta un poco más las operaciones para hacer las sumas, pero como contrapartida es mucho más fácil mostrar los resultados.
|
Nota: la codificación BCD (Binary-Coded Decimal) consiste en usar cuatro bits para cada dígito decimal, concretamente, los códigos 0000 al 1001, es decir, del 0 al 9. Como usamos cuatro bits por dígito, en un byte podemos almacenar dos dígitos BCD.
De este modo, en un byte podemos almacenar los números desde 0 a 99.
|
En nuestra cadena de 32 caracteres podemos almacenar 64 dígitos, lo cual no está nada mal.
En este caso, nos vuelve a convenir usar un almacenamiento del tipo Big-Endian, sobre todo por coherencia, ya que cada byte contiene dos dígitos, también hay que decidir uno de los modos de almacenamiento para cada uno, y lo tradicional es Big-Endian.
Una curiosidad de esta codificación es que siempre almacenaremos un número par de dígitos. Para almacenar un número como 123 usaremos dos bytes, uno con el valor 0x01 y otro con 0x23. Deberemos tener esto en cuenta a la hora de trabajar con el acarreo, si es necesario aumentar el número de dígitos. Por ejemplo 999+1 no implica aumentar el número de dígitos, pero 9999+1, sí.
|
// Sumar números enteros sin signo almacenados en formato BCD
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;
const unsigned int cax = 32;
typedef unsigned char numero[cax];
bool Sumar(numero, numero, numero);
void MostrarBCD(numero);
int main() {
numero n1={
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x10,0x00 };
numero n2={
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x00,0x00,0x00,
0x00,0x09,0x98,0x12 };
numero suma;
Sumar(n1, n2, suma);
MostrarBCD(n1);
cout << " + ";
MostrarBCD(n2);
cout << " = ";
MostrarBCD(suma);
cout << endl;
return 0;
}
bool Sumar(numero n1, numero n2, numero r) {
int acarreo = 0;
int c;
for(int i = cax-1; i >= 0; i--) {
// Sumar digito de menor peso:
c = acarreo+(n1[i] & 0x0f) + (n2[i] & 0x0f);
if(c > 9) { c-=10; acarreo=1; }
else acarreo=0;
r[i] = c;
// Sumar digito de mayor peso:
c = acarreo+((n1[i] >> 4) & 0x0f) + ((n2[i] >> 4) & 0x0f);
if(c > 9) { c-=10; acarreo=1; }
else acarreo=0;
r[i] |= (c << 4);
}
return !acarreo;
}
void MostrarBCD(numero n) {
char c;
bool cero=true;
for(unsigned int i = 0; i < cax; i++) {
c = '0' + ((n[i] >> 4) & 0x0f);
if(c != '0') cero=false;
if(!cero) cout << c;
c = '0' + (n[i] & 0x0f);
if(c != '0') cero=false;
if(!cero) cout << c;
}
} |
Ejecutar este código en codepad.
El método para extraer cada uno de los dígitos almacenados en un byte es el siguiente.
Para el de menor peso se usan los cuatro bits de la derecha, de modo que basta con hacer una operación AND de bits con la máscara 00001111, es decir, el valor 0x0f.
| Nota: llamámos máscara a un valor binario que al combinarlo mediante una operación AND con otro, deja sólo los bits que queremos preservar, enmascarando el resto. En el valor usado como máscara, los bits con valor "1" preservan el valor de los bits, y los bits con valor "0" no, ya que cualquier bit AND "0" da como resultado "0" y cualquier bit AND "1" no cambia de valor. |
Para el de mayor peso hacemos una rotación de cuatro bits a la derecha y después, enmascaramos el valor resultante con 0x0f.
En rigor, para este segundo caso no es necesario enmascarar el resultado, ya que las rotaciones de bits a la derecha introducen ceros por la izquierda.
Para volver a "empaquetar" los dós dígitos en un valor byte hacemos el proceso contrario. Rotamos a la izquierda el dígito de mayor peso cuatro bits y lo combinamos con el de menor peso usando el operador de bits OR.
Ejemplo 19.2
Veamos otro ejemplo de aplicación de operadores de bits.
Probablemente hayas oido hablar de algo llamado CRC. Seguramente en mensajes de error Error de CRC, al copiar ficheros, etc.
El CRC es una función que se aplica a un conjunto de datos de longitud indeterminada y produce un valor de longitud fija. Se usa para detectar errores durante la tansmisión o el almacenamiento de datos.
La mecánica es sencilla:
1-El emisor de un mensaje (o fichero) calcula su CRC y lo añade al mensaje.
2-El receptor lee el mesaje (o fichero) y también calcula su CRC.
3-El receptor posee ahora dos valores de CRC, el que ha recibido con el mensaje, y el que ha calculado. Si ambos son iguales significa que el mensaje no ha sido alterado durante la transmisión. Si son diferentes, es que ha habido un error.
El algoritmo para calcular el CRC ite una entrada de tipo stream, es decir, se puede ir calculando el CRC a medida que los datos se generan o se reciben.
Si te interesa la parte teórica del CRC, mira este enlace.
|
El algoritmo consiste en:
- Elegimos el valor del polinomio adecuado, dependerá del tamaño del CRC.
- Partimos de un valor de CRC semilla, normalmente 0xFFFF.
- Bucle: - Para cada bit del valor de entrada (empezando por la izquierda). - Si es "1" el nuevo valor del CRC será el resultado de aplicar la operación OR exclusivo entre el valor
anterior del CRC y el polinomio. - Cerrar el bucle. |
Se suelen usar tres valores diferentes para los polinomios, que han demostrado que restringen al máximo la probabilidad de no detectar errores. Elegirnemos el adecuado en función del tamaño del CRC o de los datos.
-CRC-12: X12+X11+X3+X2+X+1
-CRC-16: X16+X15+X2+1
-CRC-CCITT: X16+X12+X5+1
El CRC-12 se utiliza cuando la longitud del carácter es de 6 bits, mientras que los otros dos se utilizan con caracteres de 8 bits.
|
// Calculo de CRC
// (C) 2009 Con Clase
// Salvador Pozo
#include <iostream>
using namespace std;
const unsigned int CCITT_POLYNOM = 0x1021;
typedef unsigned short int WORD;
typedef unsigned char BYTE;
WORD CalcCRC(WORD uCRC, BYTE bData);
int main() {
WORD uCRC = 0xffff;
char cadena[] = "Cadena de prueba para calculo de CRC";
for(int i = 0; cadena[i]; i++)
uCRC = CalcCRC(uCRC, (BYTE)cadena[i]);
cout << "CRC: " << hex << uCRC << endl;
return 0;
}
WORD CalcCRC(WORD uCRC, BYTE bData) {
int i;
BYTE bD = bData;
for(i = 0; i < 8; i++) {
uCRC <<= 1;
if(bD & 0x0080) uCRC = CCITT_POLYNOM;
bD <<= 1;
}
return uCRC;
} |
Ejecutar este código en codepad.
Este programa ilustra el uso de typedef para la definición de tipos como WORD o BYTE.
En la función CalcCRC se usa aritmética de bits, en desplazamientos y en la función XOR.
Ejemplo 19.3
Retomemos el ejemplo del capítulo 16 sobre la codificación de colores. En esa ocasión usamos una unión para acceder a las componentes de color empaquetadas en un entero largo sin signo. Veamos ahora cómo podemos usar operadores de bits para lo mismo:
|
// Codificación de colores
// aritmética de bits
// (C) 2009 Con Clase
// Salvador Pozo
#include <iostream>
using namespace std;
typedef unsigned long int color ;
typedef unsigned char BYTE;
inline BYTE ObtenerValorRojo(color);
inline BYTE ObtenerValorVerde(color);
inline BYTE ObtenerValorAzul(color);
inline BYTE ObtenerValorAlfa(color);
inline color ModificarValorRojo(color, BYTE);
inline color ModificarValorVerde(color, BYTE);
inline color ModificarValorAzul(color, BYTE);
inline color ModificarValorAlfa(color, BYTE);
int main() {
color c1 = 0x80fedc12;
cout << "Color: " << dec << c1 << " - " << hex << c1 << endl;
cout << "Rojo: " << dec << (int)ObtenerValorRojo(c1) << " - " << hex << (int)ObtenerValorRojo(c1) << endl;
cout << "Verde: " << dec << (int)ObtenerValorVerde(c1) << " - " << hex << (int)ObtenerValorVerde(c1) << endl;
cout << "Azul: " << dec << (int)ObtenerValorAzul(c1) << " - " << hex << (int)ObtenerValorAzul(c1) << endl;
cout << "Alfa: " << dec << (int)ObtenerValorAlfa(c1) << " - " << hex << (int)ObtenerValorAlfa(c1) << endl;
c1 = ModificarValorRojo(c1, 0x42);
c1 = ModificarValorVerde(c1, 0xde);
cout << "Color: " << dec << c1 << " - " << hex << c1 << endl;
cout << "Rojo: " << dec << (int)ObtenerValorRojo(c1) << " - " << hex << (int)ObtenerValorRojo(c1) << endl;
cout << "Verde: " << dec << (int)ObtenerValorVerde(c1) << " - " << hex << (int)ObtenerValorVerde(c1) << endl;
cout << "Azul: " << dec << (int)ObtenerValorAzul(c1) << " - " << hex << (int)ObtenerValorAzul(c1) << endl;
cout << "Alfa: " << dec << (int)ObtenerValorAlfa(c1) << " - " << hex << (int)ObtenerValorAlfa(c1) << endl;
return 0;
}
inline BYTE ObtenerValorRojo(color c) {
return (BYTE)(c);
}
inline BYTE ObtenerValorVerde(color c) {
return (BYTE)(c >> 8);
}
inline BYTE ObtenerValorAzul(color c) {
return (BYTE)(c >> 16);
}
inline BYTE ObtenerValorAlfa(color c) {
return (BYTE)(c >> 24);
}
inline color ModificarValorRojo(color c, BYTE r) {
return (c & 0xffffff00) | (color)r;
}
inline color ModificarValorVerde(color c, BYTE g) {
return (c & 0xffff00ff) | (color)(g << 8);
}
inline color ModificarValorAzul(color c, BYTE b) {
return (c & 0xff00ffff) | (color)(b << 16);
}
inline color ModificarValorAlfa(color c, BYTE a) {
return (c & 0x00ffffff) | (color)(a << 24);
} |
Ejecutar este código en codepad.
Para extraer una de las componentes de color, rotamos a la derecha tantos bits como sean necesarios y retornamos el byte de menor peso. Esto lo podemos hacer, como en este ejemplo, mediante un casting o aplicando la máscara 0x000000ff mediante el operador AND (&).
Para modificar una de las componentes, el proceso es el contrario. Primero eliminamos la componente original, aplicando la máscara adecuada, por ejemplo, para el color verde es 0xffff00ff, después rotamos el valor de la nueva componente a la izquierda tantos bits como sea necesario. Finalmente, unimos ambos valores usando el operador OR (|).
Comentarios