ビット演算の高速化（ビットマップのループ・ビットカウント・ビットリバース）

# はじめに
元ネタは[ハッカーのたのしみ](https://www.amazon.co.jp/dp/443420159X)（原題：Hacker's Delight）です。

# ビットマップのループ

```
01011000
↓
f(00001000)
f(00010000)
f(01000000)
```
右から走査して1のときだけ処理を行いたいとき、
ビットの長さ分ループしなくても1の数のループで済ませられる。

```java
for (int x = 0b01011000; x > 0; x &= x - 1) {
  f(x & -x);
}
```
このように`x & -x`と`x &= x - 1`を繰り返せば、1の部分だけ渡り歩くことができる。

## x & -x

`01011000` = x
`10100111` = not(x)
`10101000` = not(x)+1 = -x
つまり
`00001000` = x & -x
となって、**右端の1だけが残る。**

## x & x-1

`01011000` = x
`01010111` = x-1
つまり
`01010000` = x & x-1
となって、**右端の1が消える。**

# ビットカウント

```
00101110 10100000 11100101 11001011
↓
16
```
1の数を数えたいとき、
ビットの数だけループしなくてもlog（ビット数）回のビット演算で求められる。

```java
x = 0b00101110101000001110010111001011;
x = (x & 0x55555555) + ((x >>>  1) & 0x55555555)
x = (x & 0x33333333) + ((x >>>  2) & 0x33333333)
x = (x & 0x0F0F0F0F) + ((x >>>  4) & 0x0F0F0F0F)
x = (x & 0x00FF00FF) + ((x >>>  8) & 0x00FF00FF)
x = (x & 0x0000FFFF) + ((x >>> 16) & 0x0000FFFF)
```
やっていることは、部分和をx自身に書き込んでいく分割統治。

## 手順

### 代入1回目
データを2ビットずつに区切り、2ビットごとの1の数を求めてxを上書きする。
`00 10 11 10 10 10 00 00 11 10 01 01 11 00 10 11` = x
↓
`_0 _1 _2 _1 _1 _1 _0 _0 _2 _1 _1 _1 _2 _0 _1 _2`（10進表現）
↓
`00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10` = 新しいx

---

`00 10 11 10 10 10 00 00 11 10 01 01 11 00 10 11` = x
`_0 _0 _1 _0 _0 _0 _0 _0 _1 _0 _1 _1 _1 _0 _0 _1` = x & 0x55555555
`_0 _1 _1 _1 _1 _1 _0 _0 _1 _1 _0 _0 _1 _0 _1 _1` = ((x >>> 1) & 0x55555555)
２ビットで分けたときの上の桁、下の桁を同時に足し合わせる
`00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10` = (x & 0x55555555) + ((x >>> 1) & 0x55555555)
やっていることは、2ビットのベクトル演算。

### 代入2回目

データを4ビットずつに区切り、4ビットごとの1の数を求めてxを上書きする。
`0001 1001 0101 0000 1001 0101 1000 0110` = x
↓
`_0_1 _2_1 _1_1 _0_0 _2_1 _1_1 _2_0 _1_2`（10進表現）
↓
`___1 ___3 ___2 ___0 ___3 ___2 ___2 ___3`（10進表現）
↓
`0001 0011 0010 0000 0011 0010 0010 0011` = 新しいx

---

`0001 1001 0101 0000 1001 0101 1000 0110` = x
`__01 __01 __01 __00 __01 __01 __00 __10` = x & 0x33333333
`__00 __10 __01 __00 __10 __01 __10 __01` = (x >>> 1) & 0x33333333
4ビットで分けたときの上の2ビット、下の２ビットを同時に足し合わせる
`0001 0011 0010 0000 0011 0010 0010 0011` = (x & 0x33333333) + ((x >>> 2) & 0x33333333)
やっていることは、4ビットのベクトル演算。

### 代入3回目

データを8ビットずつに区切り、8ビットごとの1の数を求めてxを上書きする。
`00010011 00100000 00110010 00100011` = x
↓
`___1___3 ___2___0 ___3___2 ___2___3`（10進表現）
↓
`_______4 _______2 _______5 _______5`（10進表現）
↓
`00000100 00000010 00000101 00000101` = 新しいx

### 代入4回目

データを16ビットずつに区切り、16ビットごとの1の数を求めてxを上書きする。
`0000010000000010 0000010100000101` = x
↓
`_______4_______2 _______5_______5`（10進表現）
↓
`_______________6 ______________10`（10進表現）
↓
`0000000000000110 0000000000001010` = 新しいx

### 代入5回目

データ全体の1の数を求めて、xに上書きする。
`0000000000000110 0000000000001010` = 新しいx
↓
`_______________6 ______________10`（10進表現）
↓
`_______________________________16`（10進表現）
↓
`0000000000000000 0000000000010000` = 新しいx
↓
16

## ちなみに

標準ライブラリで実装されていたりします。JavaとGoの例しか知りませんが、
Java : Integer.bitCount()、Long.bitCount()
Go : bitsパッケージのOnesCountXX()
（上記のコードよりも最適化されている）。

さらに言うと、10年前ぐらいからCPUの拡張命令（IntelであればSSE4.2のPOPCNT）としても実装されているので、
そもそも本気で高速化するなら直接POPCNTを呼べる言語を利用すべきです。

Javaに関してはJITがbitCount()をPOPCNTに置き換えてくれるらしいですが、
Goはどうなんでしょうか？

## 参考
wikipedia : SSE4、ハミング重み
https://en.wikipedia.org/wiki/SSE4
https://en.wikipedia.org/wiki/Hamming_weight

openjdk8のLongクラス（ソースコード）
https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/lang/Long.java

Goのbitsパッケージ（ソースコード）
https://golang.org/src/math/bits/bits.go?s=3946:3972#L103

# ビットリバース

```
00101110 10100000 11100101 11001011
↓
11010011 10100111 00000101 01110100
```
ビットを逆順にしたいときも分割統治が使える。

```java
x = 0b00101110101000001110010111001011;
x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >>> 16;
x = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>> 8;
x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>> 4;
x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>> 2;
x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>> 1;
```

## 手順

###  代入1回目
データを16ビットずつに区切り、入れ替える。
`0010111010100000 1110010111001011` = x
↓
`1110010111001011 0010111010100000` = 新しいx

---

`0010111010100000 1110010111001011` = x
`1110010111001011 ________________` = (x & 0x0000FFFF) << 16
`________________ 0010111010100000` = (x & 0xFFFF0000) >>> 16
`1110010111001011 0010111010100000` = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >>> 16

###  代入2回目
データを8ビットずつに区切り、隣り合う同士で入れ替える。
`11100101 11001011 00101110 10100000` = x
↓
`11001011 11100101 10100000 00101110` = 新しいx

---

`11100101 11001011 00101110 10100000` = x
`11001011 ________ 10100000 ________` = (x & 0x00FF00FF) <<  8 
`________ 11100101 ________ 00101110` = (x & 0xFF00FF00) >>> 8
`11001011 11100101 10100000 00101110` = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>> 8


###  代入3回目
データを4ビットずつに区切り、隣り合う同士で入れ替える。
`1100 1011 1110 0101 1010 0000 0010 1110` = x
↓
`1011 1100 0101 1110 0000 1010 1110 0010` = 新しいx

###  代入4回目
データを2ビットずつに区切り、隣り合う同士で入れ替える。
`10 11 11 00 01 01 11 10 00 00 10 10 11 10 00 10` = x
↓
`11 10 00 11 01 01 10 11 00 00 10 10 10 11 10 00` = 新しいx

###  代入5回目
データを1ビットずつに区切り、隣り合う同士で入れ替える。
`1 1 1 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0` = x
↓
`1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0` = 新しいx


`11010011101001110000010101110100` = もとのx
`00101110101000001110010111001011` = 新しいx
となって、正しく逆順になっている。

## ちなみに

こちらも標準ライブラリで実装されていることがあります。
Java -> Integer.reverseBytes()、Long.reverseBytes()
Go -> bitsパッケージのReverseXX()