# 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 Read all characters into memory
- 3 x = 0
- 4 x = y
- 5 x = x + y
- 6 x = x - y
- 7 x = x * y
- 8 x = x * x
- 9 x = x / y
- 10 x = x ^ y
- 11 swap x, y
- 12 x = -x
- 13 x = not x (bitwise)
- 14 Find a zeroed cell
- 15 x(y) = z (1-d array) (2 cells/array element)
- 16 x = y(z) (1-d array) (2 cells/array element)
- 17 x(y) = z (1-d array) (1 cell/array element)
- 18 x = y(z) (1-d array) (1 cell/array element)
- 19 x = x == y
- 20 x = x != y
- 21 x = x <= y
- 22 x = x < y
- 23 z = x > y
- 24 z = sign(x-y)
- 25 x = not x (boolean, logical)
- 26 x = x and y (boolean, logical)
- 27 x = x or y (boolean, logical)
- 28 while (x) { code }
- 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

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

## Read all characters into memory

,[>,]

## x = 0

### Wrapping

x[-]

### Non-wrapping

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.

Attribution: JungHwan Min

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

Uses x and two cells to the right of it.

Originally posted at Code Golf Stack Exchange.

## x = y

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

## x = x + y

### Wrapping

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

## x = x - y

### Wrapping

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

## x = x * y

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

## x = x * x

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

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

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

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

## x = -x

### Wrapping

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

### Non-Wrapping

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

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

## x = not x (bitwise)

### Wrapping

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

### Non-Wrapping

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

### To the right

[>]

### To the left

[<]

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

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)

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)

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)

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

### Wrapping

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

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

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

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

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)

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)

Attribution: Jeffry Johnston

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

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

Attribution: Sunjay Varma

Another version for when you can consume x (mutate its value). Also assumes that x is either 0 or 1. If you do not want to consume x, you can still use this algorithm. Just copy x to another cell, then apply the operation. The algorithm returns either 0 (false) or 1 (true).

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

## x = x and y (boolean, logical)

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[-]] ]

### z = x and y (boolean, logical)

Attribution: Sunjay Varma

Consumes x and y (leaves them as zero at the end of the algorithm) and stores the result in z. For short-circuit evaluation, don't evaluate x or y until just before they are used.

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

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

INPUT | OUTPUT | ||||
---|---|---|---|---|---|

x | y | x | y | z | |

0 | 0 | 0 | 0 | 0 | |

0 | 1 | 0 | 0 | 0 | |

1 | 0 | 0 | 0 | 0 | |

1 | 1 | 0 | 0 | 1 |

## x = x or y (boolean, logical)

### Wrapping

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[-]]

### z = x or y (boolean, logical)

Attribution: Sunjay Varma

Consumes x and y (leaves them as zero at the end of the algorithm) and stores the result in z. For short-circuit evaluation, don't evaluate x or y until just before they are used.

If you don't care about short-circuit evaluation, temp0 can be removed completely. If temp0 is removed and both x and y are 1, z will be 2, not 1. This is usually not a problem since it is still non-zero, but you should keep that in mind.

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

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

INPUT | OUTPUT | |||||
---|---|---|---|---|---|---|

x | y | x | y | z | temp0 | |

0 | 0 | 0 | 0 | 0 | 0 | |

0 | 1 | 0 | 0 | 1 | 0 | |

1 | 0 | 0 | 0 | 1 | 0 | |

1 | 1 | 0 | 0 | 1 | 0 |

## while (x) { code }

Attribution: Sunjay Varma

To implement a while loop, you need to evaluate the condition x both before the loop and at the end of the loop body.

x[evaluate xcodex ]evaluate x again

### break and continue

Attribution: Sunjay Varma

To implement break and continue statements in loops, consider that the following two pieces of pseudocode are functionally equivalent:

while (foo) { if (bar == foo) { if (x > 2) { break; } else { // do stuff } // do stuff } // update foo for the next iteration } // Equivalent without break statement: while (foo) { shouldBreak = false if (bar == foo) { if (x > 2) { shouldBreak = true } else { // do stuff } // don't evaluate any more code in the loop after breaking if (!shouldBreak) { // do stuff } } if (shouldBreak) { // so that the loop stops foo = 0 } else { // update foo for the next iteration } }

Notice that we need to guard **all** code *after* the break statement in the loop to prevent it from running. We don't need to guard in the else statement immediately after the break statement because that will never run after the break statement has run.

This approach allows us to implement break and continue statements in brainfuck despite the lack of sophisticated jump instructions. All we're doing is combining the concept of an if statement (defined below) with the while loop we just defined and applying it here.

Implementing a continue statement is the same thing except you never guard the loop updating code:

while (foo) { if (bar == foo) { if (x > 2) { continue; } else { // do stuff } // do stuff } // update foo for the next iteration } // Equivalent without continue statement: while (foo) { shouldContinue = false if (bar == foo) { if (x > 2) { shouldContinue = true } else { // do stuff } // don't evaluate any more code in the loop after continuing if (!shouldContinue) { // do stuff } } // This code stays the same after a continue because we still want to move on to the next iteration of the loop // update foo for the next iteration }

To implement both break and continue, you can compose the concepts here and make any combination you want. You can consider break and continue statements to be "sugar" that needs to be "desugared" in your brainfuck code.

## if (x) { code }

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

or alternatively:

temp0[-] x[temp0 ]xcode

or alternatively if you don't need x anymore:

x[x[-] ]code

## if (x == 0) { code }

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 }

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

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

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

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)

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

Solution from Stack Overflow.

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

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

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

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

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