# One Bit at a Time

*Task 2 of 6 · [Radix Sort](https://gpu.rocks/learn/radix-sort-fd3ff796.md) · GPU.js Learn*

Take the narrowest radix there is: **2**. One bit per pass, two
buckets, and the whole bucket table collapses to a single number — how many zeros there
are. Zeros go to the front in the order they appeared; ones go behind them, also in
order. So element `i`'s destination is either *how many zeros are before
me*, or *every zero, plus how many ones are before me*.

That count of preceding flags is a running total over a 0/1 array — the same shape
stream compaction uses to close its gaps, except here neither half gets thrown away.
The zero total is 32 numbers coming back to JavaScript, which is cheap to finish there.

Moving the data is one line of ordinary JavaScript: `out[dest[i]] = keys[i]`.
Enjoy it while it lasts. That line is a **scatter**, and it is the one thing
a kernel cannot do — task 4 is about turning it inside out.

## Goal

**Goal:** split `keys` by their low bit — even keys first,
odd keys behind them, each half keeping its original order — and log the result.

## Requirements

- `lowBit` returns `keys[this.thread.x] % 2` — a 0/1 flag per key
- Count the zeros in plain JavaScript and pass the total into the second kernel
- A zero's destination is how many zeros came before it; a one's is `zeros` plus how many ones came before it
- `console.log` the reordered array (the starter's last line already does)

## Hint 1 — count your own kind

Both halves need the same thing: how many *earlier* elements share your
flag. One loop does it for either flag —

```js
if (bits[j] === mine && j < this.thread.x) before++;
```

— and then only the starting point differs.

## Hint 2 — the two starting points

The zero bucket starts at slot 0. The one bucket starts right after every
zero, at slot `zeros`:

```js
if (mine === 0) return before;
return zeros + before;
```

## Same idea elsewhere

The one-bit split is where GPU radix sorting started — Satish, Harris and
Garland's manycore sorting paper builds an entire sort from it, one bit at a time, with a
prefix sum over the flag array supplying every destination. Modern hardware does the
counting in a single instruction: CUDA's `__ballot_sync` + `__popc`
and WGSL's `subgroupBallot` give a warp its flag ranks for free.

## Starter code

```js
// Radix 2: two buckets, and the whole bucket table is one number.
const gpu = new GPU({ mode });

const lowBit = gpu.createKernel(function (keys) {
  // TODO: return this key's low bit — 0 for even, 1 for odd
  return 0;
}, { output: [32] });

const destination = gpu.createKernel(function (bits, zeros) {
  const mine = bits[this.thread.x];
  let before = 0;
  for (let j = 0; j < this.constants.n; j++) {
    // TODO: count the EARLIER elements carrying the same flag
    before += 0;
  }
  // TODO: zeros start at slot 0; ones start after every zero
  return before;
}, {
  output: [32],
  constants: { n: 32 },
});

const bits = await lowBit(keys);

let zeros = 0;
for (let i = 0; i < bits.length; i++) {
  if (bits[i] === 0) zeros++;
}
console.log('zeros:', zeros);

const dest = await destination(bits, zeros);

// A scatter — fine in JavaScript, impossible inside a kernel. Task 4 fixes it.
const out = new Array(32);
for (let i = 0; i < 32; i++) out[dest[i]] = keys[i];
console.log('after the pass:', out.join(' '));
```

---

Interactive version: https://gpu.rocks/learn/radix-sort-fd3ff796/2

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