ビットボードの任意のラインを8ビットに変換・逆変換

# 1. はじめに
本記事では、下記の2つの変換を取り扱う。
- 符号なし64ビット変数である8x8のビットボードの任意のライン ⇒ 8ビット変数
- ビットボードの任意のラインを変換した8ビット変数 ⇒ ビットボード

変換したいビットボードの任意のラインの指定方法は「ライン上に含まれる特定のビット＆ラインの方向」という組み合わせで指定することにする。
例えば、ビットボードのD列を8ビット変数に変換したい場合は「D列に含まれるいずれかのビット＆垂直方向」という組み合わせとなる。

# 2. 本記事で用いるビットボード
符号なし64ビット整数を8×8の行列だと捉えたものを用いる。
オセロの駒の位置とビット位置は下記の画像のように対応する。
例えば、位置A1の駒の状態は63ビット目で管理する。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/41fdbd07-61fa-d7bb-d183-5ffd91afe926.png)
また、ビットボードの行番号・列番号を下記とする。
![2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/4df16f7c-f084-edab-17cd-7f67afc0f642.png)
よって、本記事では下記の2つの関数を使用する。
```
// あるビットの行番号を取得する
int getRow(int bit) {
    return bit / 8;
}

// あるビットの列番号を取得する
int getColumn(int bit) {
    return bit % 8;
}
```

# 3. ビットボードの任意のライン ⇒ 8ビットへの変換
ビットボードの任意のラインの選び方は、下記の4つが存在する。
- 水平方向のライン
- 垂直方向のライン
- 斜め上方向のライン
- 斜め下方向のライン

各ラインを8ビットに変換する方法を下記で解説する。

## 3-1. 水平方向のライン ⇒ 8ビットへの変換
あるビットの水平方向のラインの8ビットへの変換は
ビットの水平方向のラインをマスクし、ビットの行番号の8倍だけ右シフトすることで実現できる。
```
using u64 = unsigned long long;
using u8  = unsigned char;

// あるビットの水平方向のライン ⇒ 8ビット
u8 convertHorizontalTo8(u64 x, int bit) {
	int shift = getRow(bit) * 8;
	u64 mask = 0x00000000000000FF << shift;
	return (x & mask) >> shift;
}
```

## 3-2. 垂直方向のライン ⇒ 8ビットへの変換
下記の手順で実現できる。

①  あるビットの垂直方向のラインを列数だけ右シフトして、右端に集める。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/4c3e1330-1b0a-83fc-b2fa-9a849e12fee0.png)
②  0x0102040810204080を掛け、上位8ビットに垂直方向のラインを集める。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/f4825b96-dd7c-c828-44b3-d5a8099dede5.png)
③  56ビットだけ右シフトする。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/49cf5a82-c927-612e-8783-f40ee559d549.png)
```
// あるビットの垂直方向のライン ⇒ 8ビット
u8 convertVerticalTo8(u64 x, int bit) {
	int clmn = getColumn(bit);
	u64 mask = 0x0101010101010101 << clmn;
	return (((x & mask) >> clmn) * 0x0102040810204080) >> 56;
}
```

## 3-3. 斜め上方向のライン ⇒ 8ビットへの変換
下記の手順で実現できる。2つの例を用いて解説する。

- あるビットの斜め上方向のラインが下記のとき
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/bf3d5900-83b6-2274-8657-e57bcc23d981.png)
①  0x0101010101010101を掛け、上位8ビットに斜め上方向のラインを集める。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/7495d3c3-2a0e-5d12-ba87-ed5a60f88eb0.png)
①  56ビットだけ右シフトする
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/49cf5a82-c927-612e-8783-f40ee559d549.png)

- あるビットの斜め上方向のラインが以下のとき
 ![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/f69fa621-4411-7a64-61be-275b4e635088.png)
①  0x0101010101010101を掛け、上位8ビットに斜め上方向のラインを集める。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/6d753c92-6fd3-22d2-c899-3f01a127230b.png)
①  56ビットだけ右シフトする。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/ce7d3a6f-b2c4-cf36-5168-47357f5ac67f.png)

```
// 斜め上方向のマスク
u64 dia_a8h1_mask[] = {
	0x0000000000000001, 0x0000000000000102, 0x0000000000010204,
	0x0000000001020408, 0x0000000102040810, 0x0000010204081020,
	0x0001020408102040, 0x0102040810204080, 0x0204081020408000,
	0x0408102040800000, 0x0810204080000000, 0x1020408000000000,
	0x2040800000000000, 0x4080000000000000, 0x8000000000000000
};

// ビットの行番号・列番号から斜め上方向のマスクを求める
u64 getDiagonalA8H1Mask(int bit) {
	return dia_a8h1_mask[getRow(bit) + getColumn(bit)];
}

// あるビットの斜め上方向のライン ⇒ 8ビット
u8 convertDiagonalA8H1To8(u64 x, int bit) {
	u64 mask = getDiagonalA8H1Mask(bit);
	return ((x & mask) * 0x0101010101010101) >> 56;
}
```

## 3-4. 斜め下方向のライン ⇒ 8ビットへの変換
下記の手順で実現できる。2つの例を用いて解説する。

- あるビットの斜め下方向のラインが下記のとき
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/3ad79384-157f-2e78-49b2-729b8418f27c.png)
①  0x0101010101010101を掛け、上位8ビットに斜め下方向のラインを集める。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/bb24865b-f701-487a-56ff-de7d3c80bde8.png)
②  56ビットだけ右シフトする。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/49cf5a82-c927-612e-8783-f40ee559d549.png)

- あるビットの斜め下方向のラインが下記のとき
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/5ddae968-9ae2-bfc8-e39b-01e57e3446a7.png)
①  0x0101010101010101を掛け、上位8ビットに斜め下方向のラインを集める。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/800542c9-ce99-3a08-d0a5-d5c85613c995.png)
②  56ビットだけ右シフトする。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/5e0824b3-98ab-d296-7feb-12953e65afae.png)

```
// 斜め下方向のマスク
u64 dia_a1h8_mask[] = {
	0x0000000000000080, 0x0000000000008040, 0x0000000000804020,
	0x0000000080402010, 0x0000008040201008, 0x0000804020100804,
	0x0080402010080402, 0x8040201008040201, 0x4020100804020100,
	0x2010080402010000, 0x1008040201000000, 0x0804020100000000,
	0x0402010000000000, 0x0201000000000000, 0x0100000000000000
};

// ビットの行番号・列番号から斜め下方向のマスクを求める
u64 getDiagonalA1H8Mask(int bit) {
	return dia_a1h8_mask[(getRow(bit) - getColumn(bit)) + 7];
}

// あるビットの斜め下方向のライン ⇒ 8ビット
u8 convertDiagonalA1H8To8(u64 x, int bit) {
	u64 mask = getDiagonalA1H8Mask(bit);
	return ((x & mask) * 0x0101010101010101) >> 56;
}
```

# 4. 任意のラインを変換した8ビット ⇒ ビットボードへの変換
## 4-1. 水平方向のラインを変換した8ビット ⇒ ビットボードへの変換
変換した8ビットを、あるビットの行数の8倍だけ左シフトすることで実現できる。
```
// 水平方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToHorizontal64(u8 x, int bit) {
	return (u64)x << (getRow(bit) * 8);
}
```

## 4-2. 垂直方向のラインを変換した8ビット ⇒ ビットボードへの変換
下記の手順で実現できる。

①  垂直方向のラインの8ビット
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/409f94fd-c84c-a659-710f-bd8b50279052.png)
②  0x0101010101010101を掛ける。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/eed87e7f-2af2-838c-e06d-051f5c058cca.png)
③  A1からH8の対角線のマスクを取る。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/07e394e3-4f0c-d246-bc80-b8180591532f.png)
④  0x00000000000000FFを掛け、左端に垂直方向のラインを集める。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/c0d248a2-abf6-822f-d429-f9027363119c.png)
⑤  左端のマスクを取る。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/5d5a7bb1-cc23-025b-59e7-1d488afa72fa.png)
⑥  (7 - あるビットの列数)だけ右シフトする。
```
// 垂直方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToVertical64(u8 x, int bit) {
	return (((((u64)x
			   * 0x0101010101010101) & 0x8040201008040201)
		       * 0x00000000000000FF) & 0x8080808080808080)
			   >> (7 - getColumn(bit));
}
```

## 4-3. 斜め上方向のラインを変換した8ビット ⇒ ビットボードへの変換
下記の手順で実現できる。

①  斜め上方向のラインの8ビット
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/a4848d63-3536-dfd9-7431-db81e1281dfb.png)
②  0x0101010101010101を掛ける。
![無題.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2367021/63900d7e-37a5-c707-33ec-f450ed64a9ce.png)
③  あるビットの斜め上方向のマスクを取る。
```
// 斜め上方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToDiagonalA8H1(u8 x, int bit) {
    u64 mask = getDiagonalA8H1Mask(bit);
	return ((u64)x * 0x0101010101010101) & mask;
}
```

## 4-4. 斜め下方向のラインを変換した8ビット ⇒ ビットボードへの変換
先程の斜め上方向と同様に、斜め下方向のラインを変換した8ビットに0x0101010101010101を掛け、あるビットの斜め下方向のマスクを取ることで実現できる。

```
// 斜め下方向のラインを変換した8ビット ⇒ ビットボードへの変換
u64 convert8ToDiagonalA1H8(u8 x, int bit) {
    u64 mask = getDiagonalA1H8Mask(bit);
	return ((u64)x * 0x0101010101010101) & mask;
}
```