Una de las cosas nuevas que aprendí en los primeros capítulos de K & R, es la explicación de operaciones Bitwise. Lo cierto es que si bien sabia que existían como
nunca había tenido la necesidad de utilizarlas, nunca les preste atención. Este es un pequeño resumen por si las necesito a futuro.
Operaciones & , | , ~ y ^
- & ( conjunción Lógica o multiplicación Booleana a nivel del bit )
-
Sean a, b dos cadenas de bits del mismo tamaño ( por ejemplo integer ).
La operación
a & b realiza una operación de Conjunción Lógica sobre cada uno de los bits de ambas cadenas,
devolviendo una nueva cadena de bits de tamaño equivalente a a,b con un 1 en la posición donde tanto a como b tenian un 1 y un 0 en cualquier otro caso. Ej:
a = 10010101
b = 00110100
a & b = 00010100
- | ( disyunción Lógica o suma Booleana a nivel del bit )
-
La operación
a | b devuelve un 1 en la posición donde a o b ( o ambos ) tienen un 1 y un 0 cuando ambas tienen cero. Ej:
a = 10010101
b = 00110100
a | b = 10110101
- ~ ( negación Lógica a nivel del bit )
- Sea a una cadena de bits. La operación
~a invierte los 1s y 0s de a. Ej:
a = 10010101
~a = 01101010
- ^ ( Disyunción exclusiva Lógica a nivel del bit )
-
La operación
a ^ b devuelve un 1 en la posición donde a o b ( pero no ambos ) tienen un 1 y un 0 cuando ambas tienen 0 o ambas tienen 1. Ej:
a = 10010101
b = 00110100
a ^ b = 10100001
Operaciones << y >>
- Operación <<
- Sea a una cadena de bits, n un entero,
a << n, devuelve la misma cádena movida n bits a la izquierda ( perdiendose los primeros n bits de la cadena )
y reemplazando las n posiciones a la derecha por 0. Ej:
a = 10010101
a << 2 = 01010100
- Operación >>
- Sea a una cadena de bits, n un entero,
a >> n, devuelve la misma cadena movida n bits a la derecha ( perdiéndose los últimos n bits de la cadena )
y reemplazando las n posiciones a la izquierda por 0. Ej:
a = 10010101
a >> 3 = 00010010
Algunos Usos y Ejemplos
Multiplicación por 2n
Por propiedades de los números binarios, se cumple que agregando n 0s a la derecha es equivalente a multiplicar este mismo número por 2n. Ej:
int function multiplicar_por_exponente_de_2( int a, int power ) {
return a << power;
}
Nota: Hay que cuidar el overflow de los datos considerando el tamaño de ints en nuestro sistema. Pero este no es un post sobre implementaciones de C.
Cociente de dividir por 2n
int function cociente_de_exponente_de_2( int a, int power ) {
return a >> power;
}
Nota: Desde ya que esta función devuelve el cociente pero no el resto.
Cociente y resto de dividir por 2n
unsigned int a, cociente, resto;
a = 757;
cociente = a >> 3;
resto = (~((~0) << 3)) & a
Nota: ~0 devuelve un int del tamaño del sistema con todos sus bits pasados a 1, al moverlo 3 posiciones a la izquierda se tiene todos 1s salvo los 3 últimos bits, al negar esto se obtiene todos 0s salvo los 3 últimos bits que nos sirven para obtener los valores que son el resto de la división.
Representación en cadena binaria de un número
void show_as_binary( int a, char str[]) {
int x, size;
size = (int)sizeof(b) * 8;
for(x=0; x<size; x++) {
//This is necesary for a%2 might return -1 if a < 0.
str[x] = ‘0′ + ((a%2) < 0 ? 1: (a%2) );
a = a >> 1;
}
reverse(str);
}
Representación en Octal de un número
void show_as_octal( int a, char str[]) {
int x, size;
size = (int)sizeof(b) * 8;
for(x=0; x<size && a!=0; x++) {
str[ x ] = ‘0′ + (a%8);
a = a >> 3;
}
str[ x ] = ‘0′;
reverse(str, (x+1));
}
Uso de un int para múltiples flags
Es una práctica común en Unix usar ints para pasar múltiples flags a funciones. Supongamos que necesito 4 flags distintos para una función o para lo que sea. Lo que puedo hacer es lo siguiente:
#define FLAG_A 1;
#define FLAG_B 2;
#define FLAG_C 4;
#define FLAG_D 8;
//Llamar a la función con FLAG_A y FLAG_D
call_function( FLAG_A | FLAG_D );
//Comparar si una variable tiene FLAG_B seteado
if( ( a & FLAG_B ) == FLAG_B ) { ...
//Comparar si una variable no tiene FLAG_C seteado
if( ( ( a | FLAG_C ) != a ) { ...
Lo interesante de esto es que al abstraernos de los ints y pensarlos como cadenas de bits, se pueden hacer operaciones de algebra de boole, donde cada bit toma un valor verdadero o falso, que nos sirve para evaluar colecciones de flags como colecciones de proposiciones booleanas. Ahorrándonos así de pasar un valor como argumento a la función para cada una. Ej:
//Comparar contra FLAG_A, FLAG_B y no FLAG_D
if ( ( ( a & (FLAG_A | FLAG_B) ) == ( FLAG_A | FLAG_B ) ) && ( ( a | FLAG_D ) != a ) ) { ...
Un ejemplo concreto es el uso de los permisos de archivos en linux.
chmod toma un valor en octal que puede representarse así:
0012 = 18 = x
0102 = 28 = w
1002 = 48 = r
De donde surgen sus relativas combinaciones, por ej:
0112 = 38 = wx
1102 = 68 = rw
1112 = 78 = rwx
Bonús. Ejercicios 2.6, 2.7 y 2.8 de K & R
Ej 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.
//Ej 2.6
unsigned setbits(unsigned x, int p, int n, int y) {
unsigned t, z;
if(y < n) {
perror("Error");
} else {
//All 0s except for the space that starts at y and has size n
t = ~(~0<<n)<<(y-n);
//Get the value of x in this position
t = x & t;
//move the distance that p has from y
t = t << (p-y);
//Set that same space to 0s in x, starting on p and with size n
z = ~(~0<<n)<<(p-n);
x = x & (~ z);
//merge them
t = x | t;
}
return t;
}
Ej 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, dejando los otros sin cambio.
//Ej 2.7
unsigned invert(unsigned x, int p, int n) {
unsigned t, z;
//All 0s except for the space that starts at p and has size n
t = ~(~0<<n)<<(p-n);
//Get the inverted value of x in this position
z = (~x & t);
//merge them (first clean up x in the space that starts at p and has size n then merge with z)
t = (~t & x) | z;
return t;
}
Ej 2.8
Escriba una función rightrot( x,n ) que regresa x rotado a la derecha n posiciones de bits.
//Ej 2.8
unsigned rightrot( unsigned a, int n) {
unsigned t, mascara, x;
t = 0;
mascara = 1;
for(x=0; x<n; x++) {
t = t << 1;
t = t | (mascara & a);
a = a >> 1;
}
return t;
}
Octubre 15 2008 :: Apuntes, c :: 