# Brainfuck algorithms

This article presents a number of algorithms for use with the Brainfuck language.

In the interest of generality, the algorithms will use variable names in place of the < and > instructions. Temporary cells are denoted "temp". When using an algorithm in a program, replace the variable names with the correct number of < or > instructions to position the pointer at the desired memory cell.

Example:

If "a" is designated to be cell 1, "b" is cell 4, and the pointer is currently at cell 0, then:

a[b+a-]

becomes:

>[>>>+<<<-]

If a particular algorithm requires cell value wrapping, this will be noted, along with a non-wrapping version, if known. Certain assumptions, such as that a temporary memory cell is already zero, or that a variable used for computation can be left zeroed, are not made. Some optimizations can therefore be performed when exact conditions are known.

## Contents

- 1 Header comment
- 2 EsoAPI 1.0 installation check
- 3 Read all characters into memory
- 4 x = 0
- 5 x = y
- 6 x = x + y
- 7 x = x - y
- 8 x = x * y
- 9 x = x * x
- 10 x = x / y
- 11 x = x ^ y
- 12 swap x, y
- 13 x = -x
- 14 x = not x (bitwise)
- 15 Find a zeroed cell
- 16 x(y) = z (1-d array) (2 cells/array element)
- 17 x = y(z) (1-d array) (2 cells/array element)
- 18 x(y) = z (1-d array) (1 cell/array element)
- 19 x = y(z) (1-d array) (1 cell/array element)
- 20 x = x == y
- 21 x = x != y
- 22 x = x <= y
- 23 x = x < y
- 24 z = x > y
- 25 z = sign(x-y)
- 26 x = not x (boolean, logical)
- 27 x = x and y (boolean, logical)
- 28 x = x or y (boolean, logical)
- 29 if (x) { code }
- 30 if (x == 0) { code }
- 31 if (x) { code1 } else { code2 }
- 32 x = pseudo-random number
- 33 Divmod algorithm
- 34 Modulus algorithm
- 35 Print value of cell x as number (8-bit)
- 36 Print value of cell x as number for ANY sized cell (ie 8bit, 16bit, etc)
- 37 String to byte
- 38 Input a decimal number
- 39 See also

## Header comment[edit]

The usefulness of this type of comment is that instructions commonly used for punctuation (such as "," and ".") may be used freely. The use of "[" and "]" inside a comment should be avoided, unless they are matched. This commenting style does not work well for internal code comments, unless strategically placed where the cell value is known to be zero (or can be modified to be zero and restored):

[]comment

To make no assumption about the initial cell value, use:

[-][]comment

Since loops only terminate when / if the current cell is zeroed, comments can safely be placed directly behind any other loop.

,[.,][]comment

## EsoAPI 1.0 installation check[edit]

Attribution: Jeffry Johnston

+>.++++++++.[++++++[>++>+++++>++++++++>+++++++>+<<<<<-]>>-.>+++.----.< ----.+++++++++++++++.-------.<++++.>>+++.>+++.<-.++++.>++++.<---.>---- .-.>-.---.>>]<[-]EsoAPI compatible program

## Read all characters into memory[edit]

,[>,]

## x = 0[edit]

### Wrapping[edit]

x[-]

### Non-wrapping[edit]

Attribution: User:quintopia

This will clear a cell no matter its sign in an unbounded signed implementation. Also clobbers the cell to the left of x and the cell to the right of temp.

temp[-]† >[-]† x<[-]>[† temp>-[x+temp+>+] x[temp>] <[+[x-temp>-<-]x<] > ] temp[-] >[+]

_{† Each of these lines should have their polarities reversed if temp, the cell to the right of temp, and the cell to the left of x, respectively, contain a negative value.}

Note that rather than just clearing the two cells at temp, one could condition upon the sign that x had.

## x = y[edit]

temp0[-] x[-] y[x+temp0+y-] temp0[y+temp0-]

## x = x + y[edit]

### Wrapping[edit]

temp0[-] y[x+temp0+y-] temp0[y+temp0-]

## x = x - y[edit]

### Wrapping[edit]

temp0[-] y[x-temp0+y-] temp0[y+temp0-]

## x = x * y[edit]

temp0[-] temp1[-] x[temp1+x-] temp1[ y[x+temp0+y-]temp0[y+temp0-] temp1-]

## x = x * x[edit]

Same as above, but copies x to temp2. (Might be improvable)

temp0[-] temp1[-] temp2[-] x[temp2+temp1+x-] temp1[ temp2[x+temp0+temp2-] temp0[temp2+temp0-] temp1- ]

## x = x / y[edit]

Attribution: Jeffry Johnston

temp0[-] temp1[-] temp2[-] temp3[-] x[temp0+x-] temp0[ y[temp1+temp2+y-] temp2[y+temp2-] temp1[ temp2+ temp0-[temp2[-]temp3+temp0-] temp3[temp0+temp3-] temp2[ temp1- [x-temp1[-]]+ temp2-] temp1-] x+ temp0]

## x = x ^ y[edit]

Attribution: chad3814

temp0[-] x[temp0+x-] x+ y[ temp1[-] temp2[-] x[temp2+x-] temp2[ temp0[x+temp1+temp0-] temp1[temp0+temp1-] temp2-] y-]

## swap x, y[edit]

temp0[-] x[temp0+x-] y[x+y-] temp0[y+temp0-]

## x = -x[edit]

### Wrapping[edit]

temp0[-] x[temp0-x-] temp0[x-temp0+]

### Non-Wrapping[edit]

Requires another variable signx, where 0 = positive, 1 = negative.

temp0[-]+ signx[temp0-signx-] temp0[signx+temp0-]

## x = not x (bitwise)[edit]

### Wrapping[edit]

temp0[-] x- [temp0-x-] temp0[x+temp0-]

### Non-Wrapping[edit]

Produces an answer for 8-bit cells. For other sized cells, set temp1 to 2^(bits)-1.

temp0[-] temp1[-]+++++++++++++++[temp0+++++++++++++++++temp1-] x[temp0-x-] temp0[x+temp0-]

## Find a zeroed cell[edit]

### To the right[edit]

[>]

### To the left[edit]

[<]

## x(y) = z (1-d array) (2 cells/array element)[edit]

Attribution: Jeffry Johnston

The cells representing x, temp0, and temp1 must be contiguous, with x being the leftmost cell and temp1 the rightmost, followed by adequate memory for the array. Each array element requires 2 memory cells. The pointer ends at x.

temp0[-] temp1[-] temp2[-] y[temp1+temp2+y-]temp2[y+temp2-] z[temp0+temp2+z-]temp2[z+temp2-] x>>[[>>]+[<<]>>-]+ [>>]<[-]<[<<] >[>[>>]<+<[<<]>-] >[>>]<<[-<<]

The code up through "-]+" creates a trail of 1's that the later loops will use to find the destination cell. The cells are grouped as "data cell, 1-cell". The destination cell is "data cell, 0-cell", so that the "[>>]" stops in a useful place. The x cell is always 0, and serves as the left-side stop for the "[<<]" statements (notice that t1 is cleared by the first loop, but the loop's trailing "+" converts it to the first 1-cell in the trail). Next, the trail is followed and "[-]" clears the destination cell. The array is now prepared, so an add-to loop of the form "temp0[dest+temp0-]" moves the value in temp0 to the destination cell. Finally, with ">[>>]" the trail of 1's is followed one last time forward, and cleared on the way back, ending at the left stop, x. Contiguous memory required for the array is 3 + 2 * number of array elements.

## x = y(z) (1-d array) (2 cells/array element)[edit]

Attribution: Jeffry Johnston

The cells representing y, temp0, and temp1 must be contiguous, with x being the leftmost cell and temp1 the rightmost, followed by adequate memory for the array. Each array element requires 2 memory cells. The pointer ends at y.

x[-] temp0[-] temp1[-] z[temp1+temp0+z-]temp0[z+temp0-] y>>[[>>]+[<<]>>-]+[>>]<[<[<<]>+< (pointer is at y) x+ y>>[>>]<-]<[<<]>[>[>>]<+<[<<]>-]>[>>]<<[-<<]

## x(y) = z (1-d array) (1 cell/array element)[edit]

Attribution: Konstantinos Asimakis

The cells representing space, index1, index2 and Data must be contiguous and initially empty (zeroed), with space being the leftmost cell and Data the rightmost, followed by adequate memory for the array. Each array element requires 1 memory cell. The pointer ends at space. index1, index2 and Data are zeroed at the end.

z[-space+data+z]space[-z+space] y[-space+index1+y]space[-y+space] y[-space+index2+y]space[-y+space] >[>>>[-<<<<+>>>>]<[->+<]<[->+<]<[->+<]>-] >>>[-]<[->+<]< [[-<+>]<<<[->>>>+<<<<]>>-]<<

For an explanation on how this algorithm works read this article.

## x = y(z) (1-d array) (1 cell/array element)[edit]

Attribution: Konstantinos Asimakis

The cells representing space, index1, index2 and Data must be contiguous and initially empty (zeroed), with space being the leftmost cell and Data the rightmost, followed by adequate memory for the array. Each array element requires 1 memory cell. The pointer ends at data. index1, index2 and Data are zeroed at the end.

z[-space+index1+z]space[-z+space] z[-space+index2+z]space[-z+space] >[>>>[-<<<<+>>>>]<<[->+<]<[->+<]>-] >>>[-<+<<+>>>]<<<[->>>+<<<]> [[-<+>]>[-<+>]<<<<[->>>>+<<<<]>>-]<< x[-] data[-x+data]

## x = x == y[edit]

### Wrapping[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true) and preserves y.

temp0[-] temp1[-] x[temp1+x-]+ y[temp1-temp0+y-] temp0[y+temp0-] temp1[x-temp1[-]]

And if you don't need to preserve x or y, the following does the task without requiring any temporary blocks. Returns 0 (false) or 1 (true).

x[-y-x]+y[x-y[-]]

## x = x != y[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true).

temp0[-] temp1[-] x[temp1+x-] y[temp1-temp0+y-] temp0[y+temp0-] temp1[x+temp1[-]]

## x = x <= y[edit]

Attribution: Ian Kelly

x and y are unsigned. temp1 is the first of three consecutive temporary cells. The algorithm returns either 0 (false) or 1 (true).

temp0[-] temp1[-] >[-]+ >[-] << y[temp0+ temp1+ y-] temp0[y+ temp0-] x[temp0+ x-]+ temp1[>-]> [< x- temp0[-] temp1>->]<+< temp0[temp1- [>-]> [< x- temp0[-]+ temp1>->]<+< temp0-]

## x = x < y[edit]

Attribution: Ian Kelly

x and y are unsigned. temp1 is the first of three consecutive temporary cells. The algorithm returns either 0 (false) or 1 (true).

temp0[-] temp1[-] >[-]+ >[-] << y[temp0+ temp1+ y-] temp1[y+ temp1-] x[temp1+ x-] temp1[>-]> [< x+ temp0[-] temp1>->]<+< temp0[temp1- [>-]> [< x+ temp0[-]+ temp1>->]<+< temp0-]

## z = x > y[edit]

Attribution: User:ais523

This uses balanced loops only, and requires a wrapping implementation (and will be very slow with large numbers of bits, although the number of bits otherwise doesn't matter.) The temporaries and x are left at 0; y is set to y-x. (You could make a temporary copy of x via using another temporary that's incremented during the loop.)

temp0[-]temp1[-]z[-] x[ temp0+ y[- temp0[-] temp1+ y] temp0[- z+ temp0] temp1[- y+ temp1] y- x- ]

## z = sign(x-y)[edit]

Attribution: User:quintopia

This is a comparison of two numbers for non-wrapping implementations. The signs of the two numbers must be known. Part of it can also be used to find the sign of an unknown number if both it and its opposite are available. z and the four cells to its right must be free and clear (and will be again when the algorithm terminates), an assumption that must be made in a non-wrapping implementation, as the direction to clear these cells could not be known to this algorithm. The code blocks indicated by parenthetical comments could contain code which depends on the result of the comparison; there is no particular reason in practice to wait for the value of z to be set to one of {-1,0,1}.

x[z>>+>-x-]† y[z>>->+y-]† z+>> [->-[>]<<] <[ (y>=x) - >>[ (y>x) <<+>>[+] ]< ] >>[ (x>y) [+] ] <<< (put an {if 0, then do} algorithm here to run code conditional on y=x)

†The polarity of these lines should be reversed if x and y are negative.

## x = not x (boolean, logical)[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true).

temp0[-] x[temp0+x[-]]+ temp0[x-temp0-]

## x = x and y (boolean, logical)[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true).

temp0[-] temp1[-] x[temp1+x-] temp1[ temp1[-] y[temp1+temp0+y-] temp0[y+temp0-] temp1[x+temp1[-]] ]

## x = x or y (boolean, logical)[edit]

### Wrapping[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 255 (true).

temp0[-] temp1[-] x[temp1+x-] temp1[x-temp1[-]] y[temp1+temp0+y-]temp0[y+temp0-] temp1[x[-]-temp1[-]]

## if (x) { code }[edit]

temp0[-] temp1[-] x[temp0+temp1+x-]temp0[x+temp0-] temp1[temp1[-]]code

or alternatively:

temp0[-] x[temp0 ]xcode

## if (x == 0) { code }[edit]

The code examples in the following section work for this: if (x) { code1 } else { code2 }. Just have "code1" be empty.

## if (x) { code1 } else { code2 }[edit]

Attribution: Jeffry Johnston (39 OPs)

temp0[-] temp1[-] x[temp0+temp1+x-]temp0[x+temp0-]+ temp1[temp0- temp1[-]] temp0[code1temp0-]code2

Attribution: Daniel Marschall (33 OPs)

temp0[-]+ temp1[-] x[temp0- x[temp1+x-] ] temp1[x+temp1-] temp0[code1temp0-]code2

This is an alternate approach. It's more efficient since it doesn't require copying x, but it does require that temp0 and temp1 follow x consecutively in memory.

Attribution: Ben-Arba (25 OPs)

temp0[-]+ temp1[-] x[x>-]> [<code1x>->]<<code2

## x = pseudo-random number[edit]

Attribution: Jeffry Johnston

This algorithm employs a linear congruential generator of the form:

V = (A * V + B) % M

Where:

A = 31821, B = 13849, M = period = 65536, V = initial seed

A and B values were obtained from the book:

Texas Instruments TMS320 DSP DESIGNER'S NOTEBOOK Number 43 Random Number Generation on a TMS320C5x, by Eric Wilbur

Assumes 8-bit cells. After the code is executed, the variable "x" holds a pseudo-random number from 0 to 255 (the high byte of V, above). The variable cells "randomh" and "randoml" are the internal random number seed and should not be altered while random numbers are being generated.

temp0[-] temp1[-] temp2[-] temp3[-] temp4[-] temp5[-] randomh[temp0+randomh-] randoml[temp1+randoml-] temp3+++++++[temp2+++++++++++@temp3-] temp2[ temp0[randomh+temp3+temp0-] temp3[temp0+temp3-] temp1[randomh+temp3+temp4+temp1-] temp4[temp1+temp4-] temp3[ randoml+[temp4+temp5+randoml-] temp5[randoml+temp5-]+ temp4[temp5-temp4[-]] temp5[randomh+temp5-] temp3-] temp2-] ++++++[temp3++++++++temp2-] temp3-[ temp1[randomh+temp2+temp1-] temp2[temp1+temp2-] temp3-] temp0[-]temp1[-]+++++[temp0+++++temp1-] temp0[ randoml+[temp1+temp2+randoml-] temp2[randoml+temp2-]+ temp1[temp2-temp1[-]] temp2[randomh+temp2-] temp0-] ++++++[randomh+++++++++temp0-] randomh[x+temp0+randomh-] temp0[randomh+temp0-]

## Divmod algorithm[edit]

A clever algorithm to compute div and mod at the same time:

# >n 0 d [->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<] # >0 n d-n%d n%d n/d

If one does not need to preserve n, use this variant:

# >n d [->-[>+>>]>[+[-<+>]>+>>]<<<<<] # >0 d-n%d n%d n/d

This algorithm doesn't work when the divisor is 0 or 1.

## Modulus algorithm[edit]

If we do not need to compute the quotient as well, the following approach is shorter than the divmod algorithm.

# 0 >n 0 d 0 0 0 [>+>->+<[>]>[<+>-]<<[<]>-] # 0 >0 n d-n%d n%d 0 0

As an additional advantage, this algorithm works even if the divisor is 1.

If n doesn't have to be preserved, the following variant can be used instead.

# 0 >n d 0 0 0 [>->+<[>]>[<+>-]<<[<]>-] # 0 >0 d-n%d n%d 0 0

## Print value of cell x as number (8-bit)[edit]

x >>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[- <+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++ <]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<

Solution from Stack Overflow.

## Print value of cell x as number for ANY sized cell (ie 8bit, 16bit, etc)[edit]

x [>>+>+<<<-]>>>[<<<+>>>-]<<+>[<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-] ++++++++[<++++++>-]>[<<+>>-]>[<<+>>-]<<]>]<[->>++++++++[<++++++>-]]<[.[-]<]<

Algorithm explanation

;copy cell to workspace and back [>>+>+<<<-]>>> [<<<+>>>-]<<+> [<->[ ;while value exists >++++++++++< ;make a 10 [->-[>+>>]>[+[-<+>]>+>>]<<<<<] ;divide value by 10 >[-] ;dont need this cell ++++++++[<++++++>-] ;add 48 to remainder >[<<+>>-] ;store the remainder >[<<+>>-] ;get next value << ]>] <[- ;else need to make a zero >>++++++++[<++++++>-] ] ;print and clear each stored remainder in reverse <[.[-]<]<

Alternative:

>> x >+ [[-]< [->+< [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+< [->[-]>>+>+<<<] ]]]]]]]]< ]>>[>]++++++[-<++++++++>]>> ]<<<[.[-]<<<]

## String to byte[edit]

By: Jonne 'YoYoYonnY' Ransijn

Convert a string to a byte. The string is a list of characters in the following format:

0 0 49 48 48 0 R ^ R = Pointer at the end of the algoritm (Result) ^ = Pointer at the start of the algorithm

This algorithm will not check if the string is a number. It supports up to 3 digits, but is modulair, allowing the programmer to easily support more digits. Result will be placed one cell before the string.

>------------------------------------------------[<<+>>-]> [ <<< [<+>-]< [>++++++++++<-]> >>> ------------------------------------------------ [<<<+>>>-]> [ <<<< [<+>-]< [>++++++++++<-]> >>>> ------------------------------------------------ [<<<<+>>>>-] ] < ] <<<

## Input a decimal number[edit]

by Urban Müller (1993)

Value is input into the current cell, uses three more cells to the right. End of the number is a newline, or eof. All other character are treated the same as digits. Works correctly with bignum cells.

[-]>[-]+ // Clear sum [[-] // Begin loop on first temp >[-], // Clear the inp buffer to detect leave on eof and input [ +[ // Check for minus one on eof -----------[ // Check for newline >[-]++++++[<------>-] // Subtract 38 to get the char in zero to nine <--<<[->>++++++++++<<] // Multiply the existing value by ten >>[-<<+>>] // and add in the new char <+>] ] ] <] < // Current cell is the number input

## See also[edit]

- Brainfuck
- Brainfuck constants
- Brainfuck bitwidth conversions
- BrainClub (contains algorithms usable for stack-based programming, you might understand them if you understand Forth)