Bit-reversal permutation: Difference between revisions

Revision as of 17:13, 16 May 2018

Revision as of 11:35, 28 August 2018

Line 6:

Writing the index numbers in decimal (but, as above, starting with position 0 rather than the more conventional start of 1 for a permutation), the bit-reversal permutations of size 2^''n'', for ''n'' = 0, 1, 2, 3, ... are

* n = 0: 0

* n = 1: 0 1

* n = 2: 0 2 1 3

* n = 3: 0 4 2 6 1 5 3 7

* n = 4: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

{{OEIS|A030109}}<br>

Each permutation in this sequence can be generated by concatenating two sequences of numbers: the previous permutation, doubled, and the same sequence with each value increased by one.