# Put the Input in the Right Order

*Task 3 of 6 · [The FFT Butterfly](https://gpu.rocks/learn/fft-butterfly-d4375da7.md) · GPU.js Learn*

One thing about the last task was quietly wrong. The first pass paired
*adjacent* elements — but the split that started all this was by parity, so the first
pass should be combining `x[0]` with `x[4]`, `x[1]` with
`x[5]`… at n = 8, and with strides that change every pass. Writing a kernel whose
pair distance depends on the stage in a different way each time is possible and horrible.

The trick every iterative FFT uses instead: **permute the input once**, so
that the pairs are adjacent at every stage afterwards. The permutation turns out to be
beautifully simple — send element `i` to the position whose index is `i`
with its **bits reversed**. At n = 8, sample 1 (binary 001) goes to position 4
(binary 100); sample 3 (011) goes to position 6 (110).

gpu.js will happily give you `>>`, `&` and
`|`, and they produce correct answers — but each one compiles to a helper that
loops over up to 32 bits in the shader, so the one-line spelling costs around eight hundred
loop iterations per index. So do it in arithmetic instead, which is nine operations and, more
to the point, says out loud what a bit reversal *is*: peel the low digit off one
number and push it onto the front of another.

```js
let v = this.thread.x;
let reversed = 0;
for (let b = 0; b < this.constants.bits; b++) {
  // push v's lowest bit onto the front of reversed
  reversed = reversed * 2 + (v % 2);
  // and drop it from v
  v = Math.floor(v / 2);
}
```

One happy accident is worth naming: reversing an index twice gives it back, so this
permutation is its own inverse. It is the one rearrangement in the whole course where
"push my value there" and "pull the value that belongs here" land on the same answer. Write
it as the gather anyway — that habit is what makes the other ninety-nine cases work.

## Figures

- **the permutation is just the index, spelled backwards**

## Goal

**Goal:** write the kernel that reads the 16 real samples of
`signal` into bit-reversed order and presents them as a complex spectrum — real
part permuted, imaginary part zero.

## Requirements

- Compute the reversal arithmetically, over `this.constants.bits` = 4 bits
- It is a *gather*: cell `i` returns `x[reversed]`
- Plane 1 (imaginary) is all zeros — the input signal is real

## Hint 1 — one digit at a time

`v % 2` is the lowest bit of `v`;
`Math.floor(v / 2)` throws that bit away. Multiplying
`reversed` by 2 before adding shifts everything already collected one place
up, so the first bit taken ends up highest.

## Hint 2 — how many bits?

Exactly `log₂(n)` — 4 for 16 elements. Fewer and the top bits never
move; more and every index lands outside the array. It is already in
`this.constants.bits`.

## Hint 3 — the whole thing

Check yourself against the first three: 0 → 0, 1 → 8, 2 → 4. Then:

```js
if (this.thread.y === 0) return x[reversed];
return 0;
```

## Same idea elsewhere

The bit-reversal permutation is a named, tuned primitive everywhere: cuFFT and
rocFFT fold it into the first pass's addressing so the array is never physically permuted,
FFTW spends real effort on cache-friendly reversal orders, and hardware FFT blocks in DSPs
ship a bit-reversed addressing mode in the address generator itself. It is also why so many
library APIs offer a "bit-reversed output" variant — if you are about to multiply two
spectra together and transform back, neither of them ever needs to be in order.

## Starter code

```js
// Reverse the bits of your own index, then go and fetch that element.
const gpu = new GPU({ mode });

const scramble = gpu.createKernel(function (x) {
  let v = this.thread.x;
  let reversed = 0;
  for (let b = 0; b < this.constants.bits; b++) {
    // TODO: push v's low bit onto the front of `reversed` before dropping it.
    v = Math.floor(v / 2);
  }

  if (this.thread.y === 0) return x[reversed];
  return 0;
}, { output: [16, 2], constants: { bits: 4 } });

const ordered = scramble(signal);
console.log('original: ', signal);
console.log('scrambled:', ordered[0]);
console.log('imaginary:', ordered[1]);
```

---

Interactive version: https://gpu.rocks/learn/fft-butterfly-d4375da7/3

[Previous task](https://gpu.rocks/learn/fft-butterfly-d4375da7/2.md) · [Next task](https://gpu.rocks/learn/fft-butterfly-d4375da7/4.md)