En matemáticas aplicadas, una permutación de inversión de bits es una permutación de una secuencia de elementos, donde es una potencia de dos . Se define indexando los elementos de la secuencia por los números de a , representando cada uno de estos números por su representación binaria (rellenada para que tenga una longitud exactamente ) y asignando cada elemento al elemento cuya representación tiene los mismos bits en el orden inverso.
Repetir la misma permutación dos veces vuelve al orden original de los elementos, por lo que la permutación de inversión de bits es una involución .
Esta permutación se puede aplicar a cualquier secuencia en tiempo lineal , realizando únicamente cálculos de índices simples. Tiene aplicaciones en la generación de secuencias de baja discrepancia y en la evaluación de transformadas rápidas de Fourier .
Considere la secuencia de ocho letras abcdefgh . Sus índices son los números binarios 000, 001, 010, 011, 100, 101, 110 y 111, que al invertirse se convierten en 000, 100, 010, 110, 001, 101, 011 y 111. Por lo tanto, la letra a en la posición 000 se asigna a la misma posición (000), la letra b en la posición 001 se asigna a la quinta posición (la numerada 100), etc., dando la nueva secuencia aecgbfdh . Repitiendo la misma permutación en esta nueva secuencia se regresa a la secuencia inicial.
Escribiendo los números de índice en decimal (pero, como arriba, comenzando con la posición 0 en lugar del inicio más convencional de 1 para una permutación), las permutaciones de inversión de bits en los elementos, para , son: [1]
Cada permutación de esta secuencia puede generarse concatenando dos secuencias de números: la permutación anterior, con sus valores duplicados, y la misma secuencia con cada valor aumentado en uno. Así, por ejemplo, al duplicar la permutación de longitud 4 0 2 1 3 se obtiene 0 4 2 6 , al sumar uno se obtiene 1 5 3 7 , y al concatenar estas dos secuencias se obtiene la permutación de longitud 8 0 4 2 6 1 5 3 7 . [2]
La generalización a las representaciones de base , para , y para , es una permutación de inversión de dígitos , en la que los dígitos base del índice de cada elemento se invierten para obtener el índice permutado. La misma idea también se puede generalizar a los sistemas numéricos de base mixta . En tales casos, la permutación de inversión de dígitos debe invertir simultáneamente los dígitos de cada elemento y las bases del sistema numérico, de modo que cada dígito invertido permanezca dentro del rango definido por su base. [3]
Las permutaciones que generalizan la permutación de inversión de bits invirtiendo bloques contiguos de bits dentro de las representaciones binarias de sus índices se pueden utilizar para intercalar dos secuencias de datos de igual longitud en el lugar. [4]
Existen dos extensiones de la permutación de inversión de bits para secuencias de longitud arbitraria. Estas extensiones coinciden con la inversión de bits para secuencias cuya longitud es una potencia de 2, y su propósito es separar elementos adyacentes en una secuencia para el funcionamiento eficiente del algoritmo de Kaczmarz . La primera de estas extensiones, llamada ordenación eficiente , [5] opera sobre números compuestos, y se basa en la descomposición del número en sus componentes primos.
La segunda extensión, llamada EBR (extended bit-reversal), es similar en espíritu a la inversión de bits. Dada una matriz de tamaño , EBR llena la matriz con una permutación de los números en el rango en tiempo lineal. Los números sucesivos están separados en la permutación por al menos posiciones. [6]
La inversión de bits es más importante para los algoritmos de FFT de Cooley-Tukey de base 2 , donde las etapas recursivas del algoritmo, que operan en el lugar , implican una inversión de bits de las entradas o salidas. De manera similar, las inversiones de dígitos de base mixta surgen en las FFT de Cooley-Tukey de base mixta. [7]
La permutación de inversión de bits también se ha utilizado para diseñar límites inferiores en la computación distribuida. [8]
La secuencia de Van der Corput , una secuencia de números de baja discrepancia en el intervalo unitario , se forma reinterpretando los índices de la permutación de inversión de bits como representaciones binarias de punto fijo de números racionales diádicos .
Las permutaciones de inversión de bits se utilizan a menudo para encontrar límites inferiores en estructuras de datos dinámicas . Por ejemplo, sujeto a ciertas suposiciones, el costo de buscar los números enteros entre y , inclusive, en cualquier árbol de búsqueda binario que contenga esos valores, es cuando esos números se consultan en orden de bits invertido. Este límite se aplica incluso a árboles como los árboles splay a los que se les permite reorganizar sus nodos entre accesos. [9]
Debido principalmente a la importancia de los algoritmos de transformada rápida de Fourier , se han ideado numerosos algoritmos eficientes para aplicar una permutación de inversión de bits a una secuencia. [2]
Debido a que la permutación de inversión de bits es una involución, se puede realizar fácilmente en el lugar (sin copiar los datos en otra matriz) intercambiando pares de elementos. En la máquina de acceso aleatorio que se usa comúnmente en el análisis de algoritmos, un algoritmo simple que escanea los índices en el orden de entrada e intercambia cada vez que el escaneo encuentra un índice cuya inversión es un número mayor realizaría un número lineal de movimientos de datos. [10] Sin embargo, calcular la inversión de cada índice puede requerir un número no constante de pasos. Los algoritmos alternativos pueden realizar una permutación de inversión de bits en tiempo lineal mientras usan solo cálculos de índice simples. [11] Debido a que las permutaciones de inversión de bits pueden repetirse varias veces como parte de un cálculo, puede ser útil separar los pasos del algoritmo que calculan los datos de índice utilizados para representar la permutación (por ejemplo, utilizando el método de duplicación y concatenación) de los pasos que utilizan los resultados de este cálculo para permutar los datos (por ejemplo, escaneando los índices de datos en orden y realizando un intercambio siempre que la ubicación intercambiada sea mayor que el índice actual, o utilizando operaciones de dispersión-reunión de vectores más sofisticadas ). [2]
Otra consideración que es aún más importante para el desempeño de estos algoritmos es el efecto de la jerarquía de memoria en el tiempo de ejecución. Debido a este efecto, los algoritmos más sofisticados que consideran la estructura de bloques de la memoria pueden ser más rápidos que este escaneo ingenuo. [2] [10] Una alternativa a estas técnicas es un hardware informático especial que permite acceder a la memoria tanto en orden normal como en orden inverso de bits. [12]
En los campos de la computación de alto rendimiento se ha prestado mucha atención a la mejora del rendimiento de las inversiones de bits tanto en procesadores monoprocesadores como multiprocesadores, ya que el desarrollo de algoritmos que tienen en cuenta la arquitectura puede aprovechar al máximo los recursos de hardware y software del sistema, incluidos los cachés, TLB y núcleos múltiples, acelerando significativamente el cálculo. [13]