Task 2 of 5

Who Is My Partner?

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:

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.

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: 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

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.

All tasks in Bitonic Sort

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.