Ordenação bit-reversa

Em matemática aplicada, uma ordenação bit-reversa ou uma permutação bit-reversa é uma permutação de uma seqüência de n itens, onde n = 2^k é uma potência de dois. Ele é definido pela indexação de elementos da sequência, os números de 0 a n − 1 e, em seguida, invertendo as representações binárias de cada um desses números (acolchoado para que cada um destes números binários tenha comprimento de exatamente k). Cada item é mapeado para a nova posição dada por este valor invertido. O bit de reversão de permutação é uma involução, então repetindo a mesma permutação duas vezes retorna-se para a ordenação original sobre os itens.

Generalizações

A generalização para n = b^m para um número inteiro arbitrário b > 1 é uma permutação base-b dígito-reversa, na qual os dígitos de base-b de cada elemento são revertidos para obter a troca do índice. Uma outra generalização arbitrária composto dimensões é uma base mista dígito-reversa (em que os elementos da sequência são indexados por um número expresso em uma base mista, cujos dígitos são revertidos por permutações).

Permutações que generalizem a permutação bit-reversa invertendo blocos contíguos de bits dentro de representações binárias dos seus índices podem ser usadas para intercalar duas sequências de comprimento igual de dados no local.^[1]

Há duas extensões da permutação bit-reversa para sequências de tamanho arbitrário. Estas extensões coincidem com a bit-reversa para sequências cujo tamanho é uma potência de 2, e sua finalidade é separar itens adjacentes em uma seqüência para o funcionamento eficiente do algoritmo de Kaczmarz. A primeira destas extensões, chamada Ordenação Eficiente,^[2] opera em números compostos, e é baseada na decomposição do número em componentes primos.

A segunda extensão, chamada EBR (Extended Bit-Reversal em inglês),^[3] é semelhante em espírito a bit-reversa. Dada um vetor de tamanho n, EBR preenche o array com uma permutação dos números no intervalo $0,...,n-1$ em tempo linear. Sucessivos números são separados na permutação por pelo menos $\lfloor n/4\rfloor$ posições.

Referências

↑ Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013). «In-place permuting and perfect shuffling using involutions». Information Processing Letters. 113 (10-11): 386–391. doi:10.1016/j.ipl.2013.02.017 .
↑ Herman, Gabor T. (2009). Fundamentals of Computerized Tomography 2nd ed. London: Springer. p. 209. ISBN 978-1-85233-617-2
↑ Gordon, Dan (2017). «A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates». Numerical Algorithms. doi:10.1007/s11075-017-0356-3

Este artigo sobre computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.

[1] Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013). «In-place permuting and perfect shuffling using involutions». Information Processing Letters. 113 (10-11): 386–391. doi:10.1016/j.ipl.2013.02.017 .

[2] Herman, Gabor T. (2009). Fundamentals of Computerized Tomography 2nd ed. London: Springer. p. 209. ISBN 978-1-85233-617-2

[3] Gordon, Dan (2017). «A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates». Numerical Algorithms. doi:10.1007/s11075-017-0356-3

[1]

[2]

[3]