FLYING

/* TODO: 気の利いた説明を書く */

brainfuckで四則演算

brainfuck

brainfuckでの四則演算の実装方法を分かりやすく解説したリソースが見当たらなかったので公開。唐突にbrainfuckでfizzbuzzを書きたくなった時などにご利用ください。あえて冗長なコードで書いているので，実際に利用（？）する際には不要なポインタ移動を削除するなどして最適化したほうがいいかもしれません。

足し算

##################################################
### input
##################################################

+>++<

##################################################
### algorithm
##################################################

# {0} add !{1}
>[-<+>]<
入力完了後のメモリ
[1][2][0]...
実行完了後のメモリ
[3][0]...

引き算

足し算とほとんど同じ方法で実装できるので省略

掛け算

##################################################
### input
##################################################

++++>++<

##################################################
### algorithm
##################################################

# {2} add !{0}
[->>+<<]
# while {1} do
#   decr {1}
>[-<
#   {3:4} add !{2}
#   {2}   add !{4}
>>[->+>+<<]<<
>>>>[-<<+>>]<<<<
#   {0}   add !{3}
>>>[-<<<+>>>]<<<
# end
>]<
C言語風

上のコードでやっていることはこういうことです。

a = 4;
b = 2;
tmp = a;
a = 0;
while (b) {
  b--;
  a += tmp;
}
tmp = 0;
入力完了後のメモリ
[4][2][0]...
実行完了後のメモリ
[8][0]...

割り算と剰余

条件分岐が異様に辛い。

##################################################
### input
##################################################

+++++++>+++<

##################################################
### algorithm
##################################################

# incr {3}
>>>+<<<

# while {3} do
>>>[<<<

#   {4:5} add !{0}
#   {0}   add !{5}
[->>>>+>+<<<<<]
>>>>>[-<<<<<+>>>>>]<<<<<
#   {5:6} add !{1}
#   {1}   add !{6}
>[->>>>+>+<<<<<]<
>>>>>>[-<<<<<+>>>>>]<<<<<<

#   while {4} do
>>>>[<<<<
#     {6:7} add !{5}
#     {5}   add !{7}
>>>>>[->+>+<<]<<<<<
>>>>>>>[-<<+>>]<<<<<<<
#     if !{6} then
#       decr {5}
#     end
>>>>>>[[-]<->]<<<<<<
#     decr {4}
>>>>-<<<<
#   end
>>>>]<<<<

#   incr {4}
>>>>+<<<<
#   {6:7} add !{5}
#   {5}   add !{7}
>>>>>[->+>+<<]<<<<<
>>>>>>>[-<<+>>]<<<<<<<
#   if !{6} then
#     decr {4}
#   end
>>>>>>[[-]<<->>]<<<<<<

#   if !{5} then
#     decr {3}
#   end
>>>>>[[-]<<->>]<<<<<
#   if !{4} then
>>>>[[-]<<<<
#     incr {2}
>>+<<
#     {6:7} add !{1}
#     {1}   add !{7}
>[->>>>>+>+<<<<<<]<
>>>>>>>[-<<<<<<+>>>>>>]<<<<<<<
#     {0}   sub !{6}
>>>>>>[-<<<<<<->>>>>>]<<<<<<
#   end
>>>>]<<<<

# end
>>>]<<<

# !{1}
>[-]<
# {1} add !{0}
# {0} add !{2}
[->+<]
>>[-<<+>>]<<
C言語風

上のコードでやっていることはこういうことです。

a = 7;
b = 3;
count = 0;
flag = 1;

while (flag) {
  tmp_a = a;
  tmp_b = b;
  
  //tmp_a <  tmp_b ならば tmp_b != 0
  //tmp_a >= tmp_b ならば tmp_b == 0 となってほしい
  while (tmp_a) {
    if (tmp_b) {
      tmp_b--;
    }
    tmp_a--;
  }
  
  //tmp_a == !tmp_b となってほしい
  tmp_a = 1;
  if (tmp_b) {
    tmp_a--;
  }
  
  if (tmp_b) {
    flag = 0;
  }
  if (tmp_a) {
    count++;
    a -= b;
  }
}

b = a;
a = count;

より高級に書くと次のようになります。

a = 7;
b = 3;
count = 0;
while (1) {
  if (a < b) {
    break;
  } else {
    count++;
    a -= b;
  }
}
b = a;
a = count;
入力完了後のメモリ
[7][3][0]...
実行完了後のメモリ
[2][1][0]... （2あまり1）

コメントの読み方

!{n}
n番地の値を0にする
incr {n}
n番地の値をインクリメント
decr {n}
n番地の値をデクリメント
{m} add !{n}
m番地にn番地の値を足す。ただしn番地は実行後クリアされる
{m} sub !{n}
m番地からn番地の値を引く。ただしn番地は実行後クリアされる
{a:b} add !{n}
a番地とb番地にn番地の値を足す。ただしn番地は実行後クリアされる
{a:b} sub !{n}
a番地とb番地からn番地の値を引く。ただしn番地は実行後クリアされる
while {n} do ... end
n番地の値が0でない間コードブロックを繰り返し実行
if !{n} then ... end
n番地の値が0でなければコードブロックを実行。ただしn番地は実行後クリアされる

参考

Javascript Brainfuck Interpreter / Debugger
Brainf*ck