Bit-reversal permutation: Difference between revisions

Revision as of 21:50, 7 May 2022

Revision as of 00:10, 12 October 2022

Line 1:

{{Short description|Permutation that reverses binary numbers}}

[[File:Hammersley set 2D.svg|thumb|A [[Hammersley set]] whose coordinates are the integers from 0 to 255 and their bit-reversals]]

In applied mathematics, a '''bit-reversal permutation''' is a [[permutation]] of a [[sequence]] of <math>n</math> items, where <math>n=2^k</math> is a [[power of two]]. It is defined by indexing the elements of the sequence by the numbers from <math>0</math> to <math>n-1</math>, representing each of these numbers by its [[binary representation]] (padded to have length exactly <math>k</math>), and mapping each item to the item whose representation has the same bits in the reversed order.