1406. Fast Fourier Transform Butterfly — Bit Reversal

The first step of an iterative Fast Fourier Transform reorders the input by bit reversal: for an array of length 2^k, the element at index i moves to the index obtained by reversing the k-bit binary representation of i. Given an array whose length is a power of two, return the array after applying this bit-reversal permutation, where result[i] equals the input element at the bit-reversed index of i.

Input: A JSON object {"arr": [<values>]} whose length is a power of two.

Output: Return the bit-reversal-permuted array.

Examples

Input: {"arr":[0,1,2,3,4,5,6,7]}
Output: [0,4,2,6,1,5,3,7]
Explanation: The bit-reversal permutation gives [0,4,2,6,1,5,3,7].

Input: {"arr":[10,20,30,40]}
Output: [10,30,20,40]
Explanation: Indices 1 and 2 swap -> [10,30,20,40].

Constraints

• 1 <= len(arr) <= 2^16
• len(arr) is a power of two

Asked by