比較的高度なビット演算

# はじめに
有名な ビット演算のハックをまとめたページがある。

- [Bit Twiddling Hacks By Sean Eron Anderson](https://graphics.stanford.edu/~seander/bithacks.html)
    - 可搬性についてしっかり検討されている
    - ユースケースで引ける（逆引き）なので便利
- [awesome-bits By Keon Kim](https://github.com/keon/awesome-bits)
    - 説明がない分簡潔
    - github のマークダウンのレンダリングは読みやすい
- [Hacker's Delight Second Edition](http://www.hackersdelight.org/)
    - この業界のバイブル
    - 第2章が無料公開されていてそこだけでもすごい情報量

使えるケースが多いけど、ぱっと見理解ができない ハック を理解した際のメモ。ポータビリティは一旦脇に置き、**符号あり/なし32ビット**で考える。対話的にやりたいので 検証の多くは JavaScript上で行った（Cとの大きな違いは、unsigned な場合 右シフトには `>>>` が必要ということ）。

# コレじゃない方
`n` が `a` か `b` かのどちらかであることがわかっている。その他方を知りたい時の操作は `n ^ a ^ b`となる。XOR は2回実施すると 0 になるので `a^a^b`は`0^b`つまり`b`になる。`b^a^b`も交換可能なので `a^b^b`つまり`a^0`つまり`a`になる。 もう少し詳しい説明は[Wikipedia](https://en.wikipedia.org/wiki/XOR_swap_algorithm#Proof_of_correctness) .

```js
const theOther = (n, a, b) => n ^ a ^ b;

theOther(32, 32, 100) // 100
theOther(100, 32, 100) // 32
```

# ビットのスワップ
`i` 番目と `j`番目のビットを交換する操作。1 ビットだけ交換してもよいのだが、より一般に `i`から左に続く長さ`L`の列と `j`から左に続く長さ`L`の列を交換するとしても計算量はそれほど変わらない。以下がその実装と、実行例:

```js
const bitsSwap = (n, i, j, L = 1) => {
  const x = ((n >>> i) ^ (n >>> j)) & ((1 << L) - 1);
  return n ^ ((x << i) | (x << j));
};

bitsSwap(0b11110000, 1, 5);    // 11010010
bitsSwap(0b11110000, 1, 5, 2); // 10010110
bitsSwap(0b00101111, 1, 5, 3); // 11100011
```

簡単のため `L=1` で考察(簡単に一般化できる）。`x` は i番目のビット値 `I` と j番目のビット値 `J` を XOR で混ぜ込んだ `I ^ J` となる。これに `I` を XOR してあげると `J` になるし、逆に `J` を XOR してあげると `I` になる（一つ上の**コレじゃない方**を参照）。 したがって マスク`(x << i) | (x << j)` を作って XOR すれば、狙った結果になる。列同士がオーバーラップしてはいけないので注意。

# べき判定
べき判定は `n && !(n & (n - 1))` となる。前半部は非ゼロを主張しているだけなので、以降 n は非ゼロの場合のみ考える。ポイントは `n & (n - 1)`という操作。**[n が負の場合]**: `n-1`をしても 負であるので MSBはセットされたまま。よって AND すると少なくともMSBはセットされるので非ゼロ。**[正でべきの場合]**、以下のように 唯一の1でボローが発生して 結果 1 だらけになる。ANDすると 0 になる。

```
1<<5      00000000000000000000000000100000
(1<<5)-1  00000000000000000000000000011111
```

**[正でべきでない場合]**、`n-1`においてボローが起きるとしても、それが一番左の1以外である。よって `n-1` でも 一番左の1はセットされたまま。よってANDすると非ゼロになる。以上すべての場合で意図通りの動作をする。

```js
const isPowered = n => n && !(n & (n - 1));

[1, 2, 4, 8, 16].every(isPowered); // true
[-4, -3, 0, 3, 9].every(x => !isPowered(x)); // true 
```


# 符号のテスト
2の補数表現では 最上位ビットのみで符号が判定可能。つまり `n >> 31` の値が 「-1 なら負で 0 なら非負」とわかる。`1 | (n >> 31)` にすると「負なら -1 で非負なら 1」になるので使いやすくなる。` (n > 0) - (n < 0)` は「負なら -1, ゼロなら 0, 正なら 1」となる。

```sign.js
// equivalents to : n => (n > 0) ? 1 : (n === 0) ? 0 : -1 
const sign = n => (n > 0) - (n < 0);

sign(4) // 1
sign(0) // 0
sign(-4) // -1
```

応用として**絶対値/abs**。 `M = n >> 31` として `(n + M) ^ M` 及び `(n ^ M) - M`が絶対値を返す。非負の場合は `M=0` なのでどちらも`n`に評価されるし、負の場合は`M=-1`なので`(n-1)^(-1)`,`n^(-1)+1`となるが、-1 との XOR が NOT であることを考慮すると、これは共に NEG であるとわかる。

```abs.js
// equivalent to Math.abs
const abs = n => (n + (n >> 31)) ^ (n >> 31);
const abs2 = n => (n ^ (n >> 31)) - (n >> 31);

abs(4) === 4 && abs2(4) === 4 // true
abs(-4) === 4 && abs2(-4) === 4 // true
abs(0) === 0 && abs2(0) === 0 // true
```

# フラグセット/クリアのどちらか実施 
フラグ `f` が false の場合にはマスク`M`でセットして、そうでない場合はマスクでクリアするという操作は `n ^ ((-f ^ n) & M)`とかける。`f`の真偽で場合分けして考察:**[f が false すなわちクリアしたい時]**: `-f^n`は `n` になるので `(-f^n)&M`は、「今セットされているが、クリアすべきビット一覧」を表す。よって これを n に XOR すると、該当箇所がクリアされる。これは意図どおり。**[f が true すなわちセットしたい時]**: `-f^n` は `-1^n` すなわち `~n` になる。よって`(-f^n)&M`は、「今クリアだが、セットすべきビット一覧」を表す。よってこれを n に XOR すると該当する箇所がセットされる。これは意図どおり。

```conditionalFlagManupulation.js
const cMaskOp = (n, M, f) => n ^ ((-f ^ n) & M);

cMaskOp(0b1100, 0b0110, true) // 0b1110
cMaskOp(0b1100, 0b0110, false) // 0b1000
```


# 条件付きNEG
フラグ `f` がtrueのときのみ NEG するには `(n ^ -f) + f`。f がfalseの時は `n` になるのは すぐわかる。 f が true の時は NOTして 1 を足す操作になるがこれは NEG そのものであるので意図どおり。

```conditionalNegation.js
const cNEG = (n, f = true) => (n ^ -f) + f;

cNEG(3, true) // -3
cNEG(3, false) // 3
cNEG(-1, true) // 1
cNEG(-1, false) // -1
```

# 重要用語（おまけ）

**[MSB/LSB](https://ja.wikipedia.org/wiki/%E6%9C%80%E4%B8%8A%E4%BD%8D%E3%83%93%E3%83%83%E3%83%88)**: 一番左がMSBで一番右がLSB。負数のMSBは必ずセットされる(2の補数の場合)
**[FFS/CTZ](https://en.wikipedia.org/wiki/Find_first_set)**: LSBから見て最初にセットされたビット位置を知りたいときの操作。
**CLZ**: MSBから見て最初にセットされたビット位置を知りたい時の操作。
**isolation**: 特定の(セットされた)ビットのみを抽出する操作。
**[popcount](https://en.wikipedia.org/wiki/Hamming_weight)**: セットされたフラグの個数を知りたい時の操作。