Visualization of Bit Reversal Ring05 Mar 2016
Bit reversal ring of size z could be defined as the reverse of the binary representation of each number x in the sequence 0 to z - 1.
When the size of the ring is 2n, the reversal just rearranges the numbers in the sequence. It doesn’t remove or introduce any new number to the list.
In the first two visualizations, line represents a interchange and the color of the line represents distance between the two numbers.
Two list of numbers a and b can be said as order equivalent if and only if a[i] < a[j] = b[i] < b[j] for every i and j.
An example would be [1, 5, 3] and [2, 6, 4]. The bit reversal operation preserves some of the order equivalence of sub groups within the ring. Each arch represents a group of numbers after bit reversal operation. Groups with same order share same color. The size of the group increases as you go from top to bottom. The size of the ring (4, 8, 16) increases as you go from left to right.
For example, the ring in the column 2 and row 3 represents the groups (0,4,2), (4,2,6), (2,6,1), (6,1,5), (1,5,3), (5,3,7), (3,7,0), (7,0,4).