brainfuck 閑話：マルチバイト変数 設計編
概要
今回はマルチバイト変数（多バイト長整数）について書いていきます。
簡単に言うと、256 の数値を扱う方法です。
本当はもっと後に書く予定でしたが、知りたいという方がいたので前倒しで書きました。
今は閑話としてカテゴライズして、後でもう一度まとめようと思います。
目次
マルチバイト変数の概要
brainfuck ではマルチバイト変数は自分で作るしかありません。
しかし、これといったセオリーがあるものではなく、
- 命令の実行時間はどうか
- 命令のコード長はどうか
- 自身が扱いやすいかどうか
なとどいった重要要素が多くあるので、これといったセオリーがあるわけではありません。
なので、今回は私が作成したマルチバイト変数を紹介しつつ、設計方法の説明をしていきたいと思います。
もちろん、私が紹介したコードをそのまま使用してもらっても構いませんし、
私のコードを改変して使用してもらっても構いません。
データ格納方法の検討
マルチバイト変数と一括りに行ってしまっても、その設計方法は様々です。設計の上で検討するべき項目を以下に示します。
- 何進数を採用するか
- 固定長か可変長か
1桁に対して何byteを割り当てるか- 各変数の前後に何
byteの余裕を持たせるか - 負数をどうするか
それぞれ詳しい説明をしていきます。
何進数を採用するか
数字がいくつになった場合に桁上がりが発生するか、です。
進数が小さければ小さいほど、使用メモリが多くなり、大きれば大きいほど、様々な演算処理が重くなる印象です。
以下は実装を検討しても良いであろう進数を書きます。
1進数8進数10進数16進数256進数
1 進数は桁上がりなどは簡単ですが、メモリ量が膨大なためおすすめはしません。
256 進数はメモリ的には最良ですが、桁上がりなどがめんどくさそうなのと、計算の実行速度が遅くなりそうです。
8 進数、16 進数は bit 演算と相性が良さそうですが、入出力がめんどくさいという欠点があります。
10 進数は、bit 演算と相性が悪いという欠点がありますが、入出力が簡単です。
以上より、私は 10 進数を採用しています。
余裕がああれば、10進数と、8 または 16 真数の両方作ってもいいかもしれませんね。
固定長か可変長か
固定長は計算が楽になり、可変長はメモリ使用量が少なくなります。
私は、固定長で実装しています。
1 桁に対して何 byte を割り当てるか
1 桁に対して複数 byte を用意するのは不思議かもしれませんが、理由はあります。
まずは、そのメモリが、桁として有効かどうかを示す必要があることです。
具体的には、0 が格納されているメモリが、「変数の末端（変数の領域外）なのか、0 という数値が格納されているのか」
という問題を解決するために、桁に使用されているメモリであることを明示する必要があります。
桁数をハードコーディングしてもいいですが、桁数ごとに加算などの桁数を変更しないといけないという欠点があります。
また各桁に対して空きメモリを用意することで、各桁に対する演算を行うためのワーキングメモリとして役立つことも多いです。
基本的には 3 byte 用意すれば十分なように思います。
ここまでの話を否定するようですが、私は 1 桁 1 byte を採用しています。
上記の問題の具体的な解決方法は後述します。
各変数の前後に何 byte の余裕を持たせるか
変数間の空きは変数の端を検出するだけでなく、二項演算の処理のワーキングメモリにすることもできます。
変数の端を検出するためには、1 桁当たりの byte 数以上の空きを用意する必要があります。
私は、3 byte を採用しています。
負数をどうするか
負数をどうするかもいくつか方法があります。
- 補数表現
- 絶対値表現
- 実装しない
補数表現はそのままで、実質符号なし整数と同じようにアンダーフローを実装して、一定以上なら負数とみなす方法です。
絶対値表現は、符号と絶対値による表現です。
実装しないは、動作未定義もしくは、負数は全て 0 にする方法です。
実際は、未定義にするのが楽ですが、汎用性を考えると実装したいです。
絶対値表現もいいのですが、条件分岐がめんどくさくなるため、
私は補数表現を採用しました。
また、補数表現も、1 の補数と 2 の歩数がありますが、2 の補数を採用しています。
ちなみに、簡単のため、最上位が 0 なら正それ以外なら負として扱っています。
負数の方が数字を多く表現できることになりますが、基本的に数桁余裕を持ってコードを書くため、0 か 9 以外を取らないことになります。
設計方針のまとめ
10進数- 可変長
1桁に対して1 byteを割り当て- 各変数の前後に
3 byteの余裕 - 負数を補数表現で実装
1 桁 1 byte の実現方法
先ほど説明したとおり、「変数の末端（変数の領域外）なのか、0 という数値が格納されているのか」を判別する必要があります。それを 1 byte で表現するために、 各桁の値に 1 足した値を採用しています。
例えば、固定長 6 桁で 129 を表現する場合
{0} {0} {0} {1} {1} {1} {2} {3} {10} {0} {0} {0}
となります。
まぁ、今では 2 byte 用意しても良かったのとは思っています。
実装する演算
マルチバイト変数の設計方針がある程度固まったらあとは様々な演算等を実装していくだけです。
個人的に思う優先度ごとにわけて記述します。
必要演算
ほぼ必須となる演算や処理です。 * 入力 * 出力 * インクリメント * デクリメント
高優先度演算
必須演算で代用することもできますが、計算量の関係で実装しておいたほうがいい演算が主です。
- 加算
- 減算
- 比較
- 非零判定
- 正負判定
あると嬉しい演算
高優先度演算で実装できるが実装しておいたほうが計算量が削減できるものと、時々必要になる演算が主です。
- 比較
- スワップ
- 絶対値
- 符号反転
- シングルバイト変数との積算
- シングルバイト変数での剰余算
無くても良い
必要になる機会はありますが、実装がめんどくさい演算です。
- マルチバイト変数同士の積算
- マルチバイト変数同士の剰余算
次
実際の実装は別記事にまとめようと思います。
brainfuck 記事一覧
brainfuck 入門：リンクまとめ - 三流プログラマの戯言
brainfuck 入門：文字列の受け取り
概要
今回は文字の入力に関して説明します。数値の入力ではないです。ごめんなさい。
目次
文字列読み込み
1 行読み込み
brainfuck では 1 行読み取るという高度なことはできないので、改行文字まで読み取るということをします。ここで改行コードは \n (=10)とします。
,---------- [ ++++++++++ code ,---------- ]
読み取った値から 10 引いて 0 であれば処理を抜けるというコードになります。
3行目で 10 を足していますが、これは元の文字コードに戻す処理なので、文字数を数える場合などでは不必要となります。
また、メモリに展開したい場合は、
,---------- [ ++++++++++ > ,---------- ]
と書くことができます。
スペースまでの読み取り
時々、スペースまでを読み取りたい時があります。そういった場合には、 1 行読み取りの\n の代わりに空白 (=32) で判断することができます。
,>++++[-<-------->] [ ,>++++[-<++++++++>] code ,>++++[-<-------->] ]
インクリメント、デクリメントを 32 回行う代わりに、ループで処理しています。
改行またはスペースまでの読み取り
改行とスペースの両方の区切り文字で読み取りを終了を行いたい場合、一方のみの時と比べてめんどくさいコードになります。
>+ [ -< ,----- ----- [ >++++[-<----->]<-- [ >++++[-<++++++++>]< code [-]>[-]+< ] ]> ]<
読み取りを行うメモリの右側を区切り文字以外が入力されたかどうかをフラグ管理しています。
問題例
- ABC 072 B - OddString
AtCoderでbrainfuckやってる人には有名な問題です。AtCoderでの色々な裁定を知っていれば、9 byteで解くことができます。
しかし、ここまでの知識を駆使すれば裁定を知らなくても解くことができます。
ただし、AtCoderでは10000文字をメモリに展開できないので気を付けてください。
次回
次回こそは、大小比較書きたいですね。
記事一覧
brainfuck 入門：リンクまとめ - 三流プログラマの戯言
brainfuck 入門：if 文と bool 演算
概要
今回は、if 文とそれに伴う bool 演算について解説します。等価、不等価も説明しますが、大小比較に関しては別記事で書こうと思っています。
目次
if 文
if 文
brainfuck は条件により分岐するのはループ文しかありません。そこで、ループ分を利用して if 文を構築します。ただし、 0 を false それ以外を true とします。
[[-] code ]
ループ内でデクリメントを行う代わりに、初期化を行うとで ループ回数を1 回にすることができます。
if-else 文
else 句を付ける場合はフラグを用いる必要があります。
>+<[[-]>-< if ]>[- else ]<
else 句では初期化ではなくデクリメントしてますが、フラグは 0 か 1 しかとらないので、問題ないです。（もちろん初期化をしても問題ないです。）フラグ管理は Not の項目を見てください。
bool 演算
bool 代数として、 0 を false 、それ以外を true とします。
ただし、brainfuck では true,false を使用できるわけではないので、false を 0 、 true を 1 として表現することが多いです。この記事ではそのように表現することとします
bool 化 ((bool)value)
0 を 0 、 それ以外を 1 に変換するコードです。if 文で実現できます。
[[-]>+<]
変換結果は次のメモリに格納されます。
真理値反転 (!value)
Not は if を利用して実装を行います。
具体的には、あらかじめフラグを立てておいて、if 句でフラグを下げることで、そのフラグ値が Not の結果となります。
>+<[[-]>-<]
演算の結果はひとつ右のメモリに格納されます。
不等価演算 (!=)
c++ における != 演算です。 以下の例では、0 番地と 1番地の値を比較しています。
[->-<]>[[-]<+>]<
また別の機会に説明しようと思いますが [->-<]は引き算を行います。
ただし、0 に対するデクリメントが 255 になる環境でのみ使用できます。0 に対するデクリメントが許可されない環境での不等価はまた別の機会に説明したいと思います。
等価演算 (==)
c++ における == 演算です。 以下の例では、0 番地と 1番地の値を比較しています。不等価演算と Not の組み合わせで実現できます。
[->-<]+>[[-]<->]<
不等価演算と同様に 0 に対するデクリメントが 255 となる環境でのみ使用できます。
if 文と bool 演算の組み合わせ
bool 演算の項目で、0,1 に変換する構文を書いてきましたが、実際には 0,1 に変換することなく if 文につなげることも多いです。
例えば不等価の時に処理したいときは、
[->-<]>[[-] code ]<
というように書くことができます。
ただし、等価時に指定のコードを実行したい場合は、
[->-<]+>[[-]<->]<[- code ]
という風に Not をとる必要がどうしても出てきます。
臨機応変に対応しましょう。
固定値との比較
比較対象が固定値であり、ハードコーディングできる場合は、直接数値を引くことができます。
例えば、20 かどうかの判別は
>++++[-<----->]<[[-]>+<]
と書くことができます。（この例では結果は次のメモリに格納されます。）
問題例
- ABC 070 A - Palindromic Number
等価比較を行うことでACすることが可能です。
次回
次回は、大小比較書きたいですね。
記事一覧
brainfuck 入門：リンクまとめ - 三流プログラマの戯言
brainfuck 入門：値の移動とコピーと初期化と準非破壊ループ
概要
brainfuck を書く上で基本となる、値の移動、値のコピー、値の初期化および、準非破壊な繰り返し文の説明をします。
目次
構文解説
値の移動
brainfuck では、どのメモリに値があるかが重要になることが多々あります。そのため、望む位置に値を移動させることが重要となってきます。
値の移動は以下のコードで実現できます。
[->+<]
上記コードは一つ右に移動させます。ただし、移動先の初期値が 0 である必要があります。
また、> と < を適切に変更することで任意の位置に値を移動させることができます。ただし、ループの開始と終了でポインタの位置が変化しないように気を付ける必要があります。
値のコピー
brainfuck では基本的に破壊的命令が多いです。そのため、一つの数値を使いまわすためには値をコピーすることが必要となります。値のコピーは以下のコードで実現できます。
[->+>+<<]
上記コードは値を次とその次のメモリに複製します。値の移動と同様に複製先の初期値が 0 である必要があることに気を付けてください。
また、最初に値があったポインタは 0 になることに気を付けてください。
最初の位置に値を復元したい場合は、値のコピーの後、値の移動を行う必要があります。
[->+>+<<]>>[-<<+>>]<<
これは、次のメモリに値をコピーするコードです。
値の初期化
値の移動やコピーで述べた通り、brainfuck の構文はいくつかのメモリが 0 となっている必要があることがあります。もちろん、メモリは 0 初期化されていますが、いくつかのコードの実行後に 0 であることが保証されないことも少なくありません。そこで、メモリの初期化をする必要が出てきます。以下のコードで実現できます。
[-]
メモリの値が 0 になるまで、デクリメントするだけです。
準非破壊ループ
完全に非破壊なループを組むことはできませんが、あらかじめ値のコピーを行うことでループ回数を保持したままループを行うことができます
[->+>+<<]>>[-<<+>>]<< >[- code]
ただし、値のコピーをループ文を一つにまとめることができます。
[->+ code <]>[-<+>]<
このコードを見てもらうとわかりますが、値の複製も、順非破壊ループを使用しているとも言えます。
問題例
今回の説明は基本的なため、特に問題例はありません。
次回
次回は、bool 演算と if 文を書きたいですね。
記事一覧
brainfuck 入門：ループ文と定数生成と文字出力
今回の主軸
今回は、文字出力の行い方を解説します。 プログラミング的には後でもいいんですけど、AtCoderをやるうえでは、かなり重要となるので、初めに説明しておきます。 また文字出力に必要となるループ文と定数生成の説明をしたいと思います。
目次
ループ (繰り返し)文
いきなりループかと思われるかもしれませんが、brainfuck ではこれが最も基本的な構文となります。
掛け算や割り算、果ては加算減算ですら、ループ文が使用されます。
[- code ]
現在の値の回数だけ code を実行します。- はcode の前でも後でも問題ないです。場合によって使い分けでください。
ただし、終了時に、繰り返し回数を格納していたメモリは 0 となります。
また、 code の開始時と終了時にポインタの位置が同じである必要があります。
定数の生成
brainfuckでは定数の生成を行う場合は、値を定数回インクリメントします。以下は10を生成するコードです
++++++++++
ただし、この方法で100といった大きい数字を生成しようとした場合は多くの+を書かないといけないことになります。
そこでそれを回避するために、ループ文を使用して生成します。
以下は100を生成するコードです。
++++++++++[->++++++++++<]>
ただし、この方法で100といった大きい数字を生成しようとした場合は多くの+を書かないといけないことになります。
そこでそれを回避するために、ループ文を使用して生成します。
以下は100を生成するコードです。
++++++++++[->++++++++++<]>
定数の変更
定数の生成を行うときに、すでにある定数を変更することによって新たな定数とすることができます。以下は、
まず、41を生成して、その後80にして、そのあと57にするというプログラムです。
+++++[->++++++++<]>+ 41を生成 <+++++[->++++++++<]>- 80に変更 (40を足して1を引く) <+++++[->------<]>--- 57に変更 (20を引いて３を引く)
文字出力
一文字の出力
brainfuckでは文字は文字コードを生成して出力を行います。 例えば H という文字を出力しようとした場合、H の文字コードは 72 (=8x9) なので、
++++++++[->+++++++++<]>.
とすることで H を出力することができます。
複数文字の出力
複数の文字を出力する場合は毎回文字コードを生成するのは面倒なので、前回の値に増減させて表示を行うことがあります。
以下は Helloを出力するプログラムです。 Hello文字コードは順に、72,101,108,108, 111です。
++++++++[->+++++++++<]>. <+++++[->++++++<]>-. +++++++.. +++.
ちなみに、言語仕様編 に記載されている Hello World.は少し違った方法で実現しています。
問題例
- いろはちゃんコンテスト Day3 J - Go to Heaven
文字列を出力するだけでACが取れる問題もあります。
次回
次回は今度こそ基本構文の話しようと思います。
記事一覧
brainfuck 入門：リンクまとめ
brainfuck 入門：言語仕様編
今回の主軸
今回は、 brainfuck の言語仕様と環境依存の挙動について解説します。
目次
brainfuck とは
Hello World.
言葉で説明するよりも、コードを見てもらったほうが早いのではないかと思います。
下に示すのはプログラミングでよく最初に書かれる Hello World. と出力するプログラムです。
++++++++++[->++++++++++>+++>++++++++++++>+++++>+++++++<<<<<] >>>>>++.<<<<+.+++++++..+++.>++.>-.<<.+++.------.--------.>>>----.
概要
brainfuck はプログラミング言語の一つで、コンパイラおよびインタプリタのサイズが小さくなるように設計されています。
よく勘違いされますが、人がプログラミングしにくいように作られた言語ではありません。
また、fuck という単語は良くないということで、
brainf*ck や brainfxxk などといった表記がされることがあります。この記事では特別な場合を除き brainfuck で統一しています。
予約語
brainfuck には以下の8個の予約語のみが与えられ、それ以外の文字はすべてコメントとして扱われます。
+-><[],.
また、それぞれの命令の内容は以下の通りとなっています。
| 予約語 | 命令内容 | Cの相当コード |
|---|---|---|
+ |
現在の値をインクリメント | *ptr++; |
- |
現在の値をデクリメント | *ptr--; |
> |
ポインタをインクリメント | ptr++; |
< |
ポインタをインクリメント | ptr--; |
[ |
現在の値が 0 なら対応する ] に移動 |
while(*ptr){ |
] |
現在の値が 1 なら対応する [ に移動 |
} |
, |
入力を1文字受け取り現在の値をその文字コードにする | *ptr = getchar(); |
. |
現在の値を文字コードとする文字を出力する | putchar(*ptr); |
メモリ仕様
brainfuck には変数というものは存在しておらず代わりに最低 30000 byte の 0 で初期化されたのメモリを有しており、
そのメモリの位置を指し示すポインタを移動させることにより任意のメモリにアクセスできるようになっています。
未定義動作
brainfuck には未定義動作がいくつか存在します。そのうち重要なものを紹介します。
- 最大値に対するインクリメント
- 最小値に対するデクリメント
- メモリ領域外アクセス
これらの動作は一般的に動作が実行環境ごとに設定されていることが多いです。
実行環境による裁量
上記の未定義動作以外にも実行環境による裁量で変化しているものもあります。 以下にそのいくつかを紹介します。
- 値の最小値
- 値の最大値
EOF(入力の末端)
今回の記事に用いる実行環境
今回の記事で用いる環境は AtCoder という競技プログラミングを行うサービルで使われいてる実行環境に準拠します。
AtCoder での環境は以下の通りです。
- 値は
byte型 (0 ~ 255) 0に対するインクリメントは255255に対するインクリメントは0EOFは-1(= 255)- 対応する
]のない[はエラー - 対応する
[のない]はジャンプ時に先頭に戻る メモリは9999 byte( ※言語仕様を満たしません )- メモリの領域外アクセスはエラー
※メモリの byte 数は言語アップデートにより 30000 以上になりました。実際のサイズは確認していませんが、メモリオーバーすることはないと思って問題だけの数があります。
この記事で登場するコード例では、
[ と ] との対応はすべて取っており、メモリも仕様も 9999 を超えることがないように作成されています。
実行環境例
brainfuck のコードは実際に動かしてみるとわかりやすいです。こちらのサイトで簡単に実行できるので気になるコードは実際に動かして試してみてもいいかもしれません。
オンラインBrainf*ckデバッガ
問題例
いろはちゃんコンテスト Day1 A - 一問目
言わずと知れたbrainfuck向けの問題です。ABC 085 A - Already 2018
BACの中で最もbrainfuck向けの問題です。
次回
次回は基本構文の話しようと思います。
文字出力の話しました。
brainfuck 入門：ループ文と定数生成と文字出力 - 三流プログラマの戯言
