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 = 2k é 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 = bm 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..

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, 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), é 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 em tempo linear. Sucessivos números são separados na permutação por pelo menos posições.

Categoria:Combinatória Categoria:Algoritmos