Code patternsControlFind a zero cell or a marker
Find a zero cell or a marker
Moves the pointer to the nearest cell with a given value, however far away it is.
Watch it run
The form “The first zero to the right” works on 6 cells, named “cell 0”, “cell 1”, “cell 2”, “cell 3”, “cell 4” and “zero”. Press Play, drag the step slider forwards and back, or edit cells:
The figure needs JavaScript. The program below is the result for the example values.
[>] is a loop whose whole body is one step to the right. It asks "is this cell zero?" and, if not, moves on. It stops on the first zero cell.
To stop on another value, change the question: take the value off, ask, and put it back before moving on.
A scan is the one loop here that does not come back to where it started. The program no longer knows the number of the cell it stands on, only what kind of cell it is. That is how brainfuck does without addresses.
The code
This is the program the figure ran. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
[>]
What it needs
- There must be a cell to stop on, or the pointer runs off the tape.
- The marker forms need wrapping cells (0 − 1 has to be a number).
- The scan for a non-zero cell needs one spare zero cell to the left of where it starts.
Common mistakes
- Data that may contain a zero inside a
[>]scan: the scan stops there. - Starting the non-zero scan on the first cell of the tape. As usually given, it says only "the start cell must be zero"; it also touches the cell to the left of it.
What it costs
A plain step is one command. An optimised step is one step of an interpreter that folds runs of the same command and flat loops. Choose the values and watch the two bars; What costs what explains how cost is counted:
The figure needs JavaScript. The table below has the measured steps.
Cost as a formula, and measured
| Form | Plain steps | Optimised steps |
|---|---|---|
| The first zero to the right | 1 + 2 per cell passed | 1 + 1 per cell passed |
| The first zero to the left | 1 + 2 per cell passed | 1 + 1 per cell passed |
| The first cell that holds 1 | 3 + 4 per cell passed | 3 + 3 per cell passed |
| The first cell that is not zero | about 11 per cell passed | about 4 per cell passed |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| The first zero to the right | cells = none | 8 | 3 | 1 | 1 |
| The first zero to the right | cells = 3, 1, 4, 1, 5 | 8 | 3 | 11 | 6 |
| The first zero to the left | cells = 3, 1, 4 | 8 | 3 | 7 | 4 |
| The first cell that holds 1 | m = 4 | 8 | 7 | 19 | 15 |
| The first cell that is not zero | m = 3 | 8 | 17 | 45 | 17 |
Other forms
The first zero to the left
The pointer starts on the last cell.
[<]
Run this form step by step
The form “The first zero to the left” works on 4 cells, named “zero”, “cell 1”, “cell 2” and “cell 3”. Press Play, drag the step slider forwards and back, or edit cells:
The figure needs JavaScript. The program below is the result for the example values.
The first cell that holds 1
Takes 1 off, asks, puts it back. The other cells may hold anything, zero too.
-[+>-]+
Run this form step by step
The form “The first cell that holds 1” works on 5 cells; the named ones are “marker”. Press Play, drag the step slider forwards and back, or change where the 1 is with the slider:
The figure needs JavaScript. The program below is the result for the example values.
The first cell that is not zero
Carries a 1 along over the empty cells. Starts on cell 1, because it uses the cell to its left.
+[>[<-]<[->+<]>]>
Run this form step by step
The form “The first cell that is not zero” works on 6 cells; the named ones are “spare”, “start” and “target”. Press Play, drag the step slider forwards and back, or change empty cells in between with the slider:
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Every walk over data ends in a scan: a row of records (walk an array of records), a string (read a line into memory).
- Pick the largest by a race uses a scan as its "did anyone reach zero?" test.
- Build toward a chatbot, lesson 7, "No addresses", is about working without addresses.
Sources
- Source: Esolang wiki: Brainfuck algorithms: sections "Find a zeroed cell" and "Find a non-zeroed cell" (Epsilon).
Every program on this page was run on many inputs, in plain and in optimised mode, and compared with JavaScript. The explanations are written for this page.