lunes, 5 de julio de 2010

Chuchería binaria

Me he encontrado con el problema de, dado un número entero, calcular la siguiente potencia de dos. Por ejemplo, del número cinco obtendría ocho. Este problema es muy usual. La restricción de ser potencia de dos aparece en muchos algoritmos. Por ejemplo, en el cálculo de FFT.

Hay un algoritmo bastante curioso para resolver este cálculo. Es el que sigue:

n = n - 1;
n = n | (n >> 1);
n = n | (n >> 2);
n = n | (n >> 4);
n = n | (n >> 8);
n = n | (n >> 16);
...
n = n | (n >> (bitspace / 2));
n = n + 1;

Depende del tamaño de palabra que usemos para almacenar los enteros y no funciona en valores menores o iguales que cero. De todas las maneras, hace lo que tiene que hacer de forma maravillosa.

0 comentarios:

Publicar un comentario en la entrada