# Who Is My Partner?

*Task 2 of 5 · [Bitonic Sort](https://gpu.rocks/learn/bitonic-sort-84e0728e.md) · GPU.js Learn*

Adjacent pairs are only the first pass. The network also compares at distance 2,
4, 8, 16 — always a power of two, always the same pattern regardless of what the values
are. The classic way to write it is one character long:

```js
partner = i ^ stride;
```

XOR with a power of two flips exactly one bit of the index — bit
`log₂(stride)`. If your bit is 0 you move forward across the gap; if it is 1 you
move back. Do it twice and you are home, which is why the pairing is always mutual: no
thread is anybody's partner twice, and nobody is left over.

`^` does work in gpu.js — but it is worth knowing what you are buying. Both
WebGL backends compile it to a helper function that walks up to 32 bits of both operands in
a loop; the native GLSL integer operator is never emitted. One character of JavaScript, a
32-iteration loop in the shader. On CUDA or WebGPU, XOR is a single instruction. Here it is
not, so this module spells the flip out in arithmetic instead — two operations, and it
hands you something XOR hides: the *value* of the bit you are flipping.

```js
const bit = Math.floor(i / stride) % 2;   // 0 or 1 — my bit at log2(stride)
partner = bit === 0 ? i + stride : i - stride;
```

Hold on to that `bit`. The next task needs it, and needs a second one just
like it.

## Goal

**Goal:** return the *partner index* for each of 16 threads at a
given power-of-two `stride` — no data involved, pure index arithmetic.

## Requirements

- The kernel takes `stride` as an argument and returns an index, not a value
- Work for *any* power-of-two stride — 1, 2, 4 and 8 all have to come out right
- Pairing must be mutual: the partner of your partner is you

## Hint 1 — which bit?

At `stride = 4` the indices 0…7 split into 0–3 (bit clear, step
forward) and 4–7 (bit set, step back). `Math.floor(i / 4) % 2` is exactly
that split: 0, 0, 0, 0, 1, 1, 1, 1.

## Hint 2 — the whole kernel

```js
const i = this.thread.x;
const bit = Math.floor(i / stride) % 2;
if (bit === 0) return i + stride;
return i - stride;
```

`return i ^ stride;` gives the same answers, at the cost of that
32-iteration loop — and it will not help you with the next task.

## Same idea elsewhere

The XOR partner is the canonical spelling of a sorting network everywhere:
CUDA's `__shfl_xor_sync(mask, value, laneMask)` takes the lane XOR mask
directly, and WGSL's `subgroupShuffleXor` is named after it. Both are one
instruction on the hardware — worth remembering that the arithmetic form you write here is
a gpu.js accommodation, not a universal truth.

## Starter code

```js
// Pure index arithmetic: no data, no comparison. Just "who do I pair with?"
const gpu = new GPU({ mode });

const partner = gpu.createKernel(function (stride) {
  const i = this.thread.x;

  // TODO: flip the bit that `stride` names.
  // Which bit is it? Math.floor(i / stride) % 2 tells you its value —
  // 0 means step forward by stride, 1 means step back.
  return i;
}, { output: [16] });

console.log('stride 1:', await partner(1));
console.log('stride 4:', await partner(4));
```

---

Interactive version: https://gpu.rocks/learn/bitonic-sort-84e0728e/2

[Previous task](https://gpu.rocks/learn/bitonic-sort-84e0728e/1.md) · [Next task](https://gpu.rocks/learn/bitonic-sort-84e0728e/3.md)