Números binarios en C++

ATENCIÓN ACTUALIZACIÓN (2014-12-13): El estándar de C++ de 2014 incluye la posibilidad de usar literales binarios directamente con la notación 0b1001.


En C++ (y en C y en otros muchos lenguajes de programación) hay tres formas de escribir números enteros literales.

1. En base 10 (decimal) cuando escribo algo como 1042348
2. En base 16 (hexadecimal) cuando prefijo 0x como en 0x3FFF
3. En base 8 (octal) cuando prefijo sólo 0 como en 0663

Cuando se programa en bajo nivel muchas veces es más directo escribir directamente en base 2 (binario), ¿pero cómo? Me he topado con la siguiente macro que lo consigue

#define Ob(x)  ((unsigned)Ob_(0 ## x ## uL))
#define Ob_(x) (x & 1 | x >> 2 & 2 | x >> 4 & 4 | x >> 6 & 8 |  \
 x >> 8 & 16 | x >> 10 & 32 | x >> 12 & 64 | x >> 14 & 128)

El truco se basa en dos pasos, el primero Ob (no es un cero, es una o) pone delante un 0 (que sí es un cero) y detrás un "uL". El "uL" es la forma que tenemos de decirle al C++ que el número es sin signo y largo. El cero, por otra parte, sí que es importante ya que nos va a convertir el número a octal. Lo que tenemos entonces es un número binario interpretado como un número octal. ¿Cómo afecta eso a su valor?

Un número binario se expresa de la siguiente forma [$$ n=\cdots + d_3 2^3 + d_2 2^2 + d_1 2^1 + d_0 2^0 $$] donde los [$d_i$] son los dígitos. Los dígitos serán o cero o uno. Al escribir el número binario como octal lo que hacemos es  [$$ n=\cdots + d_3 8^3 + d_2 8^2 + d_1 8^1 + d_0 8^0 $$] pero aún con los dígitos en binario. Así que lo único que necesitamos es leer los bits de tres en tres ya que [$8=2^3$].  Justamente eso es lo que hace Ob_.

Por ejemplo:
Ob(1001) //Como binario es 9 en decimal
Ob_(01001uL) //Como octal es 513 en decimal y 1_000_000_001 en binario
9 //Tomando un bit de cada 3 en el 513 

Clasificación de los bugs

Leyendo a Walter Bright me he encontrado con la palabreja "heisenbug" que según él es un tipo de bug. Ya me imaginaba yo que tendría que haber una taxonomía de los bugs. El resumen de lo que he encontrado es este:

• Bohrbug: Error sistemático que se da siempre cuando las condiciones lo propician.
• Mandelbug: Error sistemático tan complejo que no parece sistemático, pero lo es.
• Heisenbug: Error sistemático que desaparece cuando intentamos depurarlo. Ya sea por que estamos usando el depurador y cambia la estructura de la memoria, porque el código está compilado en modo de depuración o por otras razones.
• Schrödinbug: Error oculto que, una vez descubierto, todo el mundo se tropieza con él.
• Estadístico: Error que no se detecta en una única ejecución del programa, sino que hay que hacer una estadística de los resultados hasta darnos cuenta que no son como deberían ser. (Esto me recuerda a la minería de datos en los MMORPG)
• Alfa bug: Error que ves una vez y no vuelves a ver. Lo que ocurría antiguamente cuando un rayo cósmico le daba a una celda de memoria.

Supongo que luego están los errores de condiciones de carrera, que aparecen cuando les da la gana si no se han sincronizado bien las hebras. Ya inventarán una palabreja para eso algún día.

El lío de las composiciones

La composición en las relaciones

Una relación [$\le$] entre [$A$] y [$B$] es un subconjunto del conjunto cartesiano.[$$\le \subseteq A\times B$$]Cuando dos elementos [$a\in A$] y [$b\in B$] están relacionados escribimos [$$ a \le b \Leftrightarrow (a,b)\in \le$$] La composición de dos relaciones [$\le_1$] entre [$A$] y [$B$]; y [$\le_2$] entre [$B$] y [$C$] es [$\le_1 \circ \le_2$] definida así [$$ a \le_1\circ \le_2 c \Leftrightarrow \exists b\in B.a\le_1 b\le_2 c $$] Es interesante ver el parecido natural entre [$$  a \le_1\circ \le_2 c$$] y [$$ a\le_1 b\le_2 c $$] como si el [$\circ$] representase un elemento indefinido a buscar.

La composición en las funciones

Una función [$f:A\to B$] no es más que una relación en la cual [$$\forall a\in A.\exists ! b\in B. a f b $$] Para los que no lo hayan visto nunca [$\exists !$] significa "existe un único".
Bien, los problemas empiezan porque si existe un único [$b$] lo natural es representarlo por [$f$] y [$a$]. La forma de hacerlo es esta: [$$f(a)=b \Leftrightarrow a f b$$] ¿Por qué es problemático? Porque si pienso que una función es una relación y defino la composición de funciones como una composición de relaciones obtenemos [$$ (f\circ g)(a)=g(f(a)) $$] Invirtiéndose el orden de [$f$] y [$g$], lo que lía muchísimo. Así que lo que se hace es definir al revés la composición de funciones. [$$ (f\circ g)(a)=f(g(a)) $$] Por lo que deja de ser igual que la composición de relaciones.

Soluciones

Las que se me ocurren así a bote pronto son:

1. Usar una notación postfija para las funciones [$(a)f$] en vez de [$f(a)$]. De esta manera [$ (a)(f\circ g)  =((a)f)g$] y el orden coincide con la composición de relaciones.
2. Invertir una de las dos composiciones. O bien [$ (f\circ g)(a)=g(f(a)) $] o bien [$ a \le_2\circ \le_1 c \Leftrightarrow \exists b\in B.a\le_1 b\le_2 c $]. Hagas lo que hagas, estás invirtiendo el orden natural de la notación y vas a liarte (el elemento [$a$] va primero a [$f$] y a [$\le_1$] que están lejos de él).
3. Usar dos notaciones. Por ejemplo, usar [$\le_1 ; \le_2 = \le_2 \circ \le_1$] y [$ f \circ g = g ; f $]. Esta solución la suele usar alguno que otro autor.
4. Definir las funciones al revés, [$\forall a\in A.\exists ! b\in B. b f a $] de forma que   [$b=f(a) \Leftrightarrow b f a$]. Claro que también así vamos en contra de unos cuantos siglos de historia y habría que darle la vuelta a muchas definiciones como relaciones inyectivas.

Exponenciando la derivación

Realmente para definir la exponencial (o cualquier otra función analítica) mediante una serie de potencias hacen falta pocas cosas.

• Una operación de multiplicación por escalar
• Una operación de suma
• Una operación de potencia

Con estas tres operaciones podemos definir
[$$ e^x = \sum_{k=0}^\infty \frac{x^k}{k!} $$]
Los operadores lineales cumplen todas estas condiciones tomando la potencia como composición iterada.
[$$f^0=Id;  f^{n+1}=f\circ f^n$$]
Un caso clásico es cuando las operaciones lineales están representadas por matrices.
Otro de estos operadores lineales es la derivación, que escribiremos [$D$]. Se puede realizar la exponencial de la derivación.
[$$e^D = \sum_{k=0}^\infty \frac{D^k}{k!} $$]
Para ver mejor sus efectos, aplicaremos el resultado de [$\alpha$] veces esta exponencial sobre [$x^n$].
[$$e^{\alpha D} x^n = \sum_{k=0}^\infty \frac{\alpha^k D^k}{k!} x^n $$]
Podemos derivar hasta [$n$] veces [$x^n$]
[$$\sum_{k=0}^n \frac{n!  \alpha^k x^{n-k} }{k! (n-k)!}$$]
Es interesantísimo ver que lo obtenido es justamente el binomio de Newton.
[$$ \sum_{k=0}^n \frac{n!  \alpha^k x^{n-k} }{k! (n-k)!} = (x+\alpha)^n $$]
Debido a que estamos trabajando con operadores lineales, podemos volver a usar una serie de potencias para aplicar la exponencial de la derivación sobre una función analítica arbitraria.
[$$ (e^{\alpha D} f)(x) = e^{\alpha D} \sum_{i=0}^\infty {a_i x^i} =   \sum_{i=0}^\infty {a_i   e^{\alpha D} x^i} =  \sum_{i=0}^\infty {a_i  (x+\alpha)^i} = f(x+\alpha) $$]
Así que la exponencial de la derivación no es más que una traslación.
Los físicos me dicen que acabo de descubrir que el operador de momento genera las traslaciones. ¡Vaya! Pues no lo sabía.