Permutación de inversión de bits

En matemáticas aplicadas, una permutación de inversión de bits es una permutación de una secuencia de${\displaystyle n}$artículos, donde${\displaystyle n=2^{k}}$es una potencia de dos . Se define indexando los elementos de la secuencia por los números desde${\displaystyle 0}$a${\displaystyle n-1}$, representando cada uno de estos números por su representación binaria (rellenada para tener una longitud exactamente${\displaystyle k}$), y asignando cada elemento al elemento cuya representación tiene los mismos bits en orden inverso.

Repetir la misma permutación dos veces devuelve 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 sencillos. Tiene aplicaciones en la generación de secuencias con baja discrepancia y en la evaluación de transformadas rápidas de Fourier .

Consideremos la secuencia de ocho letras abcdefgh . Sus índices son los números binarios 000, 001, 010, 011, 100, 101, 110 y 111, que al invertirlos se convierten en 000, 100, 010, 110, 001, 101, 011 y 111. Así, 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 como 100), etc., dando como resultado la nueva secuencia aecgbfdh . Al repetir la misma permutación en esta nueva secuencia, se regresa a la secuencia inicial.

Escribiendo los números de índice en decimal (pero, como se indicó anteriormente, 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${\displaystyle n=2^{k}}$artículos, para${\displaystyle k=0,1,2,3,\dots }$, son: ^{[ 1 ]}

Cada permutación de esta secuencia se puede generar concatenando dos secuencias de números: la permutación anterior, con sus valores duplicados, y la misma secuencia con cada valor incrementado en uno. Así, por ejemplo, duplicar la permutación de longitud 4 0 2 1 3 da 0 4 2 6 , sumar uno da 1 5 3 7 , y concatenar estas dos secuencias da la permutación de longitud 8 0 4 2 6 1 5 3 7. ^{[ 2 ]}

La generalización a la raíz${\displaystyle b}$representaciones, para${\displaystyle b>2}$y a${\displaystyle n=b^{k}}$, es una permutación de inversión de dígitos , en la que la base-${\displaystyle b}$Los dígitos del índice de cada elemento se invierten para obtener el índice permutado. Esta misma idea puede generalizarse a 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 pueden usarse para intercalar dos secuencias de datos de igual longitud en el mismo 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, denominada 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 (inversión de bits extendida), es similar en espíritu a la inversión de bits. Dado un array de tamaño${\displaystyle n}$, EBR llena la matriz con una permutación de los números en el rango${\displaystyle 0\ldots n-1}$en tiempo lineal. Los números sucesivos están separados en la permutación por al menos${\displaystyle \lfloor n/4\rfloor }$posiciones. ^{[ 6 ]}

La inversión de bits es de suma importancia para los algoritmos FFT de Cooley-Tukey de base 2 , donde las etapas recursivas del algoritmo, que operan in situ , 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 las representaciones binarias de punto fijo de los 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 enteros entre${\displaystyle 0}$y${\displaystyle n-1}$, inclusive, en cualquier árbol de búsqueda binaria que contenga esos valores, es${\displaystyle \Omega (n\log n)}$cuando esos números se consultan en orden de bits invertidos. 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 ]}

Dado que la permutación de inversión de bits es una involución, puede realizarse fácilmente in situ (sin copiar los datos en otro array) intercambiando pares de elementos. En la máquina de acceso aleatorio comúnmente utilizada en el análisis de algoritmos, un algoritmo simple que recorre los índices en el orden de entrada e intercambia cuando encuentra un índice cuya inversión es 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. Existen algoritmos alternativos que pueden realizar una permutación de inversión de bits en tiempo lineal utilizando únicamente cálculos de índices sencillos. ^{[ 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, mediante 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 cuando la ubicación intercambiada es mayor que el índice actual, o mediante operaciones de dispersión-recolección de vectores más sofisticadas ). ^{[ 2 ]}

Otra consideración aún más importante para el rendimiento 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 ]}

Se ha prestado especial atención a la mejora del rendimiento de las operaciones de inversión de bits en el campo de la computación de alto rendimiento. El desarrollo de algoritmos que tengan en cuenta la arquitectura es crucial para permitir un uso óptimo de los recursos de hardware y software del sistema, como las cachés, las TLB y los procesadores multinúcleo. ^{[ 13 ]}