ビット演算のイディオムに関する私的メモ

ビット演算に関するメモです。

>本記事では、汎整数拡張、通常の算術変換、既定の実引数拡張（にともなう符号拡張）の話題はスコープ外としますが、Cでビット演算をする場合はそれらに気を付けてください。[暗黙の型変換にともなう符号拡張](https://qiita.com/yz2cm/items/0e24e1df40ef5cd43249)の影響により、素朴な直観に反する結果となる場合があります。

#「2の補数をとる」ことのビットイメージ

基本情報技術者試験で、`2の補数は「ビット反転+1」`と暗記した思い出がありますが、その効果をビットイメージであらわすと

* 最右のビット`1`より左側にあるビットをすべて反転させる。全ビットが`0`のときは`0`を返す。（例：`1010 1000 -> 0101 1000`）

```:2の補数のビットイメージ
`^^^^`で示すビットのみが反転

    x     ->    -x
---------    ---------
1010 1000 -> 0101 1000
^^^^         ^^^^
1001 0100 -> 0110 1100
^^^^ ^       ^^^^ ^
1111 1111 -> 0000 0001
^^^^ ^^^     ^^^^ ^^^
0000 0000 -> 0000 0000

```

紙とペンを使って、何パターンか`ビット反転+1`をやってみると、この効果が成立するワケが腑に落ちるかと思います。

#x+1のビットイメージ

「`1`の加算」は、手計算しても分かるように「最右のビット`0`から最下位ビットまでをビット反転する」ことに等しいです。

```:最右のビット0から最下位ビットまでをビット反転
    x     ->   x + 1
---------    ---------
1010 1000 -> 1010 1001
        ^            ^
1001 0111 -> 1001 1000
     ^^^^         ^^^^
0000 0000 -> 0000 0001
        ^            ^
1111 1111 -> 0000 0000
^^^^ ^^^^    ^^^^ ^^^^
```

#x-1のビットイメージ

「`1`の減算」は、手計算しても分かるように「最右のビット`1`から最下位ビットまでをビット反転する」ことに等しいです。

```:最右のビット1から最下位ビットまでをビット反転
    x     ->   x - 1
---------    ---------
1010 1000 -> 1010 0111
     ^^^^         ^^^^
1001 0111 -> 1001 0110
        ^            ^
0000 0000 -> 1111 1111
^^^^ ^^^^    ^^^^ ^^^^
1111 1111 -> 1111 1110
        ^            ^
```

#「-~x」が「x+1」、「~-x」が「x-1」に等しい理由

`N`ビットにおける「`x`のビット反転（1の補数）」を数式で表現すると、以下に等しいです。

```math
2^N - 1 - x
```

`N`ビットにおける「`x`の2の補数」を数式で表現すると、以下に等しいです。

```math
2^N - x
```

以上をふまえると`-~x`は

```math
\begin{align}
2^N - (2^N - 1 - x)&= 2^N - 2^N + 1 + x\\ &= x + 1
\end{align}
```

同様に`~-x`は

```math
\begin{align}
2^N - 1 - (2^N - x)&= 2^N - 1 - 2^N + x\\ &= x - 1
\end{align}
```

#ビット演算イディオム集

この性質を利用して、いくつかイディオムを作ってみました（以下表）。

個人的には、`-(-x｜~x)`が「最右のビット1を最下位ビットに移動する」のが、ビットの動きがあって面白いなーと思いました。

```:最右のビット1を最下位ビットに移動
    x     -> -(-x|~x)
---------    ---------
1000 1000 -> 1000 0001
     ^               ^
```

|#|式|説明|例|
|:--:|:--------:|:--|:--:|
|1|`x^x`|定数`0`を返す。|`1010 1011 -> 0000 0000`|
|2|`-~(x^x)`|定数`1`を返す。|`1010 1011 -> 0000 0001`|
|3|`~x｜x`<br>`~(x^x)`<br>`x ^ ~x`|全ビット`1`を返す。|`1010 1011 -> 1111 1111`|
|4|`-~x`|`x + 1`を返す。|`1010 1011 -> 1010 1100`|
|5|`~-x`|`x - 1`を返す。|`1010 1100 -> 1010 1011`|
|6|`-(-x｜~x)`|最右の`1`を、最下位ビットに移動。<br>・`x=0`のとき`1`を返す。|`1010 1000 -> 1010 0001`|
|7|`~(x｜-x)`　　　|末尾の連続する`0`を保存するマスクを作成。<br>・`x=0`のときすべてのビットが`1`となる。<br>・`x`の最下位ビットが`1`のとき`0`を返す。|`1010 1000 -> 0000 0111`|
|8|`x ^ (x & -~x)`|末尾の連続する`1`を保存するマスクを作成。<br>・`x`の最下位ビットが`0`のとき`0`を返す。|`0100 1111 -> 0000 1111`|
|9|`x ^ (~-x)`　　　|最右の`1`と末尾の連続する`0`を保存するマスクを作成。<br>・`x=0`のときすべてのビットが`1`となる。<br>`x`の最下位ビットが`1`のとき`1`を返す。|`1010 1000 -> 0000 1111`|
|10|`x ^ (-~x)`　　　|最右の`0`と末尾の連続する`1`を保存するマスクを作成。<br>・全ビットが`1`のとき`x`を返す。<br>|`0101 0111 -> 0000 1111`|
|11|`-(x&-x)`|最上位ビット～最右の1までを保存するマスクを作成。<br>・`x=0`のとき`0`を返す。|`0110 1000 -> 1111 1000`| 
|12|`x & -x`|最右の`1`をピックアップするマスクを作成。<br>・`x=0`のとき`0`を返す。|`1010 1000 -> 0000 1000`|
|13|`~x & (-~x)`|最右の`0`をピックアップするマスクを作成。<br>・全ビットが`1`のとき`0`を返す。|`0100 1011 -> 0000 0100`|
|14|`x ^ (-~(x｜~-x) & x)`|最右の連続する`1`を保存するマスクを作成。<br>・`x=0`のとき`0`を返す。|`0100 1110 -> 0000 1110`|
|15|`x ^ (~-(x｜-~x)｜x)`|最右の連続する`0`を保存するマスクを作成。<br>・全ビットが`1`のとき`0`を返す。|`0100 0011 -> 0011 1100`|
|16|`~(-x｜~x)`<br>`x & ~-x`|最右の`1`を`0`にする。<br>・`x=0`のとき`0`を返す。|`1010 1000 -> 1010 0000`|
|17|`x ｜ -~x`|最右の`0`を`1`にする。<br>・全ビットが`1`のとき`x`を返す。|`1010 0111 -> 1010 1111`|
|18|`-x & ~x`|「末尾の連続する`0`」以外のビットをすべて反転する。<br>・最下位ビットが1のとき全ビットを反転|`1010 1000 -> 0101 0000`|
|19|`x & -~x`|末尾の連続する`1`を`0`にする。<br>・`x`の最下位ビットが`0`のとき`x`を返す。|`0100 1111 -> 0100 0000`|
|20|`x ｜ ~-x`|末尾の連続する`0`を`1`にする。<br>・最下位ビットが`1`のとき`x`を返す。|`0100 1000 -> 0100 1111`|
|21|`-~(x｜~-x) & x`|最右の連続する`1`を`0`にする。<br>・`x=0`のとき`0`を返す。|`0100 1110 -> 0100 0000`|
|22|`~-(x｜-~x)｜x`|最右の連続する`0`を`1`にする。<br>・全ビットが`1`のとき`x`を返す。|`0101 0011 -> 0101 1111`|

#【参考1】ビットダンプ関数

```c:bit_dump(C99)
#include <stdio.h>
#include <limits.h>

void bit_dump(unsigned char x)
{
    for(size_t pos = sizeof(x) * CHAR_BIT; pos--;)
        printf("%d", !!(x & 1<<pos));
}
```

#【参考2】ビット演算の演算子の優先順位

|優先順位|演算子|結合性|
|:----:|:----|:----:|
|1|単項+、単項-、~、!|右結合|
|2|<<、>>|左結合|
|3|&|左結合|
|4|\^|左結合|
|5|｜|左結合|
|6|&&|左結合|
|7|｜｜|左結合|

#【参考3】参考文献
* 「[ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか](https://www.amazon.co.jp/%E3%83%8F%E3%83%83%E3%82%AB%E3%83%BC%E3%81%AE%E3%81%9F%E3%81%AE%E3%81%97%E3%81%BF%E2%80%95%E6%9C%AC%E7%89%A9%E3%81%AE%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AF%E3%81%84%E3%81%8B%E3%81%AB%E3%81%97%E3%81%A6%E5%95%8F%E9%A1%8C%E3%82%92%E8%A7%A3%E3%81%8F%E3%81%8B-%E3%82%B8%E3%83%A5%E3%83%8B%E3%82%A2-%E3%83%98%E3%83%B3%E3%83%AA%E3%83%BC%E3%83%BBS-%E3%82%A6%E3%82%A9%E3%83%BC%E3%83%AC%E3%83%B3/dp/4434046683/ref=pd_cp_14_1?_encoding=UTF8&psc=1&refRID=RQ2KHJAJN8TS8TD2HVCK)」