一からコンピュータを作る ~ブール算術~

2章の目標は、ALUを理解し、実装することです。
頑張っていきましょう！！

参考にした記事
[CPUの演算処理を司るALUの仕組み - Qiita](https://qiita.com/satodayo/items/755672aa44acdec1e66e#comments)
実装を助けてくれるリポジトリ
[GitHub - y-meguro/nand2tetris: 「コンピュータシステムの理論と実装」の演習用](https://github.com/y-meguro/nand2tetris)
[GitHub - ikenox/nand2tetris: 『コンピュータシステムの理論と実装』演習問題の回答・メモ](https://github.com/ikenox/nand2tetris)
[GitHub - youkidearitai/nand2tetris: nand2tetris.org / コンピュータシステムの理論と実装の解答](https://github.com/youkidearitai/nand2tetris)


## PCで使用される計算
**PCで使用される計算 = 論理演算 + 算術演算**
[コンピュータシステムの理論と実装2](https://www.slideshare.net/HiroyukiTamaki1/computer2-165793939/1)

## 加算器
- 半加算器  
2つのビットの和を求める
- 全加算器  
3つのビットの和を求める
- 加算器  
2つのnビットの和を求める
- インクリメンタ  
与えられた数値に1を加算するように設計される

この4つを組み合わせて、ALUをどう設計していくかを考えるのが2章の醍醐味になってきます。
[加算器 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8)


### 半加算器
`Xor` と `And` で構成されます。
`sum` は、 `Xor` を指し、`carry` は `And` を指します。

```
CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b 
        carry;  // Left bit of a + b

    PARTS:
        Xor(a=a, b=b, out=sum);
        And(a=a, b=b, out=carry);
}
```


### 全加算器
**上記の半加算器と全加算器の違いは、繰り上がりを処理するかどうかになります。**
[論理回路の半加算器と全加算器の違いは何ですかすみませんが教え... - Yahoo!知恵袋](https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1210726462)

>加算器には、下の桁からの桁上がりを考慮した全加算器と、考慮しない半加算器がある
[CPUの中枢「ALU」を作ってみよう](https://ednjapan.com/edn/articles/1308/09/news002_2.html)

```
CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    PARTS:
        HalfAdder(a=a, b=b, sum=s1, carry=cr1);
        HalfAdder(a=s1, b=c, sum=sum, carry=cr2);
        Or(a=cr1, b=cr2, out=carry);
}
```

### 加算器(多ビット加算器)
`Add16.hdl`ファイルの実装をどのようにしていくのか
加算器を実装することになります。
下記全体図はがわかりやすいです。

>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148392/add7e373-f33c-88fa-4565-97e7c7b5329c.png)
[組合せ回路の例（加算回路）](http://kccn.konan-u.ac.jp/information/cs/cyber08/cy8_cmex.htm) より引用

`a[16]`の16は、16ビットを指します。


### インクリメンタ
どのようにしてビット演算で **1を足すことを実現するのか**を考えていくことになります。
このときのポイントは反転させることにあります。
ビット演算は反転させるだけで、1を足したことになる

[Indoor Space Cowboy: コンピュータシステムの理論と実装 第２章 ブール算術 回答例](https://is-cowboy.blogspot.com/2015/04/blog-post_6.html)
[2の補数表現における演算](http://www.cc.kyoto-su.ac.jp/~kbys/kiso/number/int-op.html)
[O'REILLY コンピューターシステムの理論と実装【第2章①】 - sota0113](https://sota0113.hatenablog.com/entry/2019/01/18/183729)


## ALU
算術論理演算器と呼ばれています。
第二章は、ALUの実装を目指します。
最初は難しいですが、 単なる組み合わせ回路と思えば少し気が楽になります。

考え方とかは下記の記事とかが非常にわかりやすいです。
[加算器の実装など (nand to tetris(6))](https://weblog.metacircular-evaluator.org/blog/2015/04/05/nand2tetris6/)

### 考えるべきこと
#### if文がかなり出てくるので、Muxが便利になる
`// if (zx == 1) set x = 0`のような条件式の場合は、 `Mux`が便利です。
`Mux16 (a=x, b=false, sel=zx, out=w1);`のようにselを起点に実装することができます。

#### `set x = !x`をどう実現するか
これは単純に `Not` で実装することができます。
`Not16(in=x, out=notx);`


#### f の条件分岐をどう実現するか
`// if (f == 1)  set out = x + y` と `// if (f == 0)  set out = x & y` には、 `Add` と `And` を実装することで解決することができます。

#### Or8way
[１章　ブール理論（番外編）｜tango｜note](https://note.com/tango9512357/n/n326875c4c353?magazine_key=m96f5f4049665#AReq3)

### 最上位、最下位ビット
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148392/2bbb5abf-d1cd-b031-75ed-c0a1e4c10ee1.png)
[最上位ビット - Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%80%E4%B8%8A%E4%BD%8D%E3%83%93%E3%83%83%E3%83%88) より引用

>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148392/54b7c29c-b335-c8d6-cc99-35fafa8ccef8.png)
[最下位ビット - Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%80%E4%B8%8B%E4%BD%8D%E3%83%93%E3%83%83%E3%83%88) より引用


### 足し算
>XOR演算は「繰り上がりが無ければ、足し算と同じ結果」
AND演算は「繰り上がるかどうかが分かる(結果が1なら繰り上がる)」
[ビット演算(AND,XOR,左シフト)だけで、足し算を行う。単純なようでいて、結構難しい…。 \| メサイア・ワークス](https://www.messiahworks.com/archives/19836) より引用


### その他
[ひとりNand2Tetris(2) - ALUまで: Architect Note](http://blog.tojiru.net/article/426464326.html)