Bit-reversal permutation (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | In applied mathematics, a bit-reversal permutation is a permutation of a sequence of items, where is a power of two. It is defined by indexing the elements of the sequence by the numbers from to , representing each of these numbers by its binary representation (padded to have length exactly ), and mapping each item to the item whose representation has the same bits in the reversed order. Repeating the same permutation twice returns to the original ordering on the items, so the bit reversal permutation is an involution. This permutation can be applied to any sequence in linear time while performing only simple index calculations. It has applications in the generation of low-discrepancy sequences and in the evaluation of fast Fourier transforms. (en) 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. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Hammersley_set_2D.svg?width=300 |
| dbo:wikiPageID | 25692725 (xsd:integer) |
| dbo:wikiPageLength | 11992 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120557118 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_of_two dbr:Binary_search_tree dbr:Permutation dbc:Permutations dbr:Low-discrepancy_sequence dbr:Cooley–Tukey_FFT_algorithm dbr:Linear_time dbr:Lower_bound dbr:Van_der_Corput_sequence dbc:Combinatorial_algorithms dbr:Data_structures dbr:Fast_Fourier_transform dbr:Radix dbr:Involution_(mathematics) dbr:Kaczmarz_method dbc:FFT_algorithms dbr:Mixed_radix dbr:In-place_algorithm dbr:Random-access_machine dbr:Sequence dbr:Memory_hierarchy dbr:Unit_interval dbr:Fixed-point_arithmetic dbr:Vectored_I/O dbr:Dyadic_rational_number dbr:In-place dbr:Binary_representation dbr:Splay_trees dbr:File:Hammersley_set_2D.svg |
| dbp:wikiPageUsesTemplate | dbt:Not_a_typo dbt:Short_description |
| dct:subject | dbc:Permutations dbc:Combinatorial_algorithms dbc:FFT_algorithms |
| gold:hypernym | dbr:Permutation |
| rdf:type | yago:WikicatCombinatorialAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Change107296428 yago:Event100029378 yago:Happening107283608 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Substitution107443761 yago:Variation107337390 yago:WikicatFFTAlgorithms yago:WikicatPermutations |
| rdfs:comment | 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. (pt) In applied mathematics, a bit-reversal permutation is a permutation of a sequence of items, where is a power of two. It is defined by indexing the elements of the sequence by the numbers from to , representing each of these numbers by its binary representation (padded to have length exactly ), and mapping each item to the item whose representation has the same bits in the reversed order. Repeating the same permutation twice returns to the original ordering on the items, so the bit reversal permutation is an involution. (en) |
| rdfs:label | Bit-reversal permutation (en) Ordenação bit-reversa (pt) |
| owl:sameAs | freebase:Bit-reversal permutation yago-res:Bit-reversal permutation wikidata:Bit-reversal permutation dbpedia-fa:Bit-reversal permutation dbpedia-pt:Bit-reversal permutation https://global.dbpedia.org/id/4ZCjB |
| prov:wasDerivedFrom | wikipedia-en:Bit-reversal_permutation?oldid=1120557118&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Hammersley_set_2D.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Bit-reversal_permutation |
| is dbo:wikiPageRedirects of | dbr:Bit-reversal dbr:Bit-reversed_order dbr:Bit_reversal dbr:Digit-reversal_permutation |
| is dbo:wikiPageWikiLink of | dbr:Calkin–Wilf_tree dbr:List_of_numerical_analysis_topics dbr:List_of_permutation_topics dbr:Organizationally_unique_identifier dbr:Cooley–Tukey_FFT_algorithm dbr:Van_der_Corput_sequence dbr:Walsh_matrix dbr:Stern–Brocot_tree dbr:Bit-reversal dbr:Bit-reversed_order dbr:Bit_reversal dbr:Digit-reversal_permutation |
| is foaf:primaryTopic of | wikipedia-en:Bit-reversal_permutation |
