ビット操作関数 Bitwise を使ってみる

これは [#NervesJP Advent Calendar 2021](https://qiita.com/advent-calendar/2021/nervesjp) の18日目です。昨日は [@torifukukaiou](https://qiita.com/torifukukaiou) さんの [毎日自動更新！　記事の舞台裏 -- Nerves on Raspberry Pi 2大活躍 🚀🚀🚀](https://qiita.com/torifukukaiou/items/a58aa8162422f560ef64) でした。

# はじめに
去年 (2020年) に [組込みに欠かせない Elixir でのビットの扱い方](https://qiita.com/kikuyuta/items/e200a6208013f38333de) と言うアドベントカレンダーの記事を書きました。当然ながら「Bitwiseには触れないの？」というコメントを頂きました。ということで、今年は Bitwise について書きます。

# 概要
[Bitwise](https://hexdocs.pm/elixir/Bitwise.html) は整数に対して bit 演算をする関数群です。Erlang の関数に対するマクロで記述されていて、ガードで使えるという特徴があります。

Bitwise 自体は大変小さく、6種類の関数しかありません。これを2通りの記法で表記してるので、見た目は全部で12通りの関数があります。

残念ながら Bitwise はバイト列である Binary やビット列 Bitstring に対しては使えません。あくまで Elixir の可変長の整数のみが対象です。このため IoT で多用するビット長が固定幅の用途にはそのままでは使えません。

## 宣言
プログラムで使う場合は `use Bitwise` を宣言します。

```exs
iex(1)> use Bitwise
Bitwise
```

同じ関数に対して、演算子（単項演算子ないしは二項演算子）と通常の関数の記法との2種類が用意されています。

```exs
iex(2)> 5 &&& 3
1
iex(3)> band(5, 3)
1
```

もし、演算子のみを使いたくて関数の記法を用いたくない場合は `only_operators: true` オプションを `use` する際に指定します。

```exs
iex(1)> use Bitwise, only_operators: true
Bitwise
iex(2)> 5 &&& 3
1
iex(3)> band(5, 3)
** (CompileError) iex:3: undefined function band/2
```

逆に、通常の関数風の記法のみを使いたくて演算子の記法を用いたくない場合は `skip_operators: true` オプションを `use` する際に指定します。

```exs
iex(1)> use Bitwise, skip_operators: true
Bitwise
iex(2)> 5 &&& 3
** (CompileError) iex:2: undefined function &&&/2

iex(2)> band(5, 3)
1
```

妙な機能ですが、これはおそらく他で使ってる記述とぶつからないようにという配慮なのかと想像してます。

## 扱う型
Bitwise の対象は整数型のみで、その2進数表現に対するビット操作を行います。整数以外に適用すると `ArithmeticError` 例外を起こします。バイト列である `Binary` やビット列である `Bitstring` に対しても使うことができません。

```exs
iex(3)> ~~~0
-1
iex(4)> ~~~0.0
** (ArithmeticError) bad argument in arithmetic expression: Bitwise.bnot(0.0)
    :erlang.bnot(0.0)
```

なお、負数については2の補数表現になってることに注意してください。これは後で触れます。

# 関数
関数は全部で6種類です。その全てに演算子表現と通常の関数型の表現があります。ただし `bxor` に対応する二項演算子は deprecated です。これはマニュアルには記載がなくて、全部で11種類の関数の記述があります。

## bnot/1 (~~~/1) 関数
2進数表現でのビット単位での否定をとる関数です。この関数群では唯一の arity が 1 の関数（単項演算子）です。関数名は Binary NOT から来ているようです。

```exs
iex(10)> ~~~0
-1
```

これ分かりにくいですね。0 の bit 反転がなぜ -1 なのか。
0 が ERTS でどう表現されてるかというと、とある幅のゼロの列 0000...0000 です[^erts-small-integer]。これのビット反転を取ると 1111...1111 になります。これはビット長によらず2の補数表現としては -1 となります。これが `~~~0` の結果が -1 になる理由です。

[^erts-small-integer]: 正確にいうと小さな整数の場合は 28bit か 60bit 幅のどちらかの長さです。どっちの長さになるかはいごかしてる CPU に依存します。これを超えると可変長の整数表現を使うようになります。

よって、正の整数のビット反転をとった場合、もとの数を n とすると `~~~n` は -n-1 の値を返します。

```exs
iex(20)> ~~~1
-2
iex(21)> ~~~2
-3
iex(22)> ~~~3
-4
iex(23)> ~~~255
-256
```

10進数表現だけではなんだかわからないので `IO.inspect` を使って2進数表現を表示してみます。以下で2進数表現が `IO.inspect` の副作用による表示です。そして、10進数表現が `IO.inspect` の返り値、すなわちパイプで受け取った前の関数の返り値そのものです。

```exs
iex(25)> ~~~0 |> IO.inspect(base: :binary)   
-0b1
-1
iex(26)> ~~~1 |> IO.inspect(base: :binary) 
-0b10
-2
iex(27)> ~~~2 |> IO.inspect(base: :binary) 
-0b11
-3
iex(28)> ~~~3 |> IO.inspect(base: :binary) 
-0b100
-4
iex(29)> ~~~255 |> IO.inspect(base: :binary) 
-0b100000000
-256
```

この負の表示ですが、うまいことビット列が分かります。`-0b` の部分を 1 の列 `1111....1111` と思ってみてください。すると上から順番に

- 1111....1111 **1**
- 1111....1111 **10**
- 1111....1111 **11**
- 1111....1111 **100**
- 1111....1111 **10000000**
というビット列になってると分かります。

`~~~` の代わりに `bnot` を使っても同様の結果が返ります。

```exs
iex(38)> bnot(0) |> IO.inspect(base: :binary)   
-0b1
-1
iex(39)> bnot(1) |> IO.inspect(base: :binary) 
-0b10
-2
iex(40)> bnot(2) |> IO.inspect(base: :binary) 
-0b11
-3
iex(41)> bnot(3) |> IO.inspect(base: :binary) 
-0b100
-4
iex(42)> bnot(255) |> IO.inspect(base: :binary) 
-0b100000000
-256
```

負の数に対してやると、当該引数の2の補数表現に対してビット反転をします。

```exs
iex(43)> ~~~ -1 |> IO.inspect(base: :binary)            
0b0
0
iex(44)> ~~~ -2 |> IO.inspect(base: :binary) 
0b1
1
iex(45)> ~~~ -256 |> IO.inspect(base: :binary)  
0b11111111
255
```

ビット反転ですから2回適用するともとに戻ります。

```exs
iex(46)> ~~~ ~~~ 0 |> IO.inspect(base: :binary)
0b0
0
iex(47)> ~~~ ~~~ 1 |> IO.inspect(base: :binary) 
0b1
1
iex(48)> ~~~ ~~~ 2 |> IO.inspect(base: :binary)
0b10
2
iex(49)> ~~~ ~~~ 3 |> IO.inspect(base: :binary)
0b11
3
iex(50)> ~~~ ~~~ -1 |> IO.inspect(base: :binary)
-0b1
-1
iex(51)> ~~~ ~~~ -2 |> IO.inspect(base: :binary)
-0b10
-2
iex(52)> ~~~ ~~~ -255 |> IO.inspect(base: :binary)
-0b11111111
-255
```

単なるビット反転なんですが、iex で見るとなかなかわかりにくいです。

## band/2 (&&&/2) 関数
2進数表現でのビット単位での論理積をとる関数です。関数名は Binary AND から来てるものと思います。

```exs
iex(53)> 0 &&& 1
0
iex(54)> 5 &&& 6
4
```

これも10進数だと分かりにくいので2進数表現にしてみます。

```exs
iex(55)> (0b0 &&& 0b1) |> IO.inspect(base: :binary)
0b0
0
iex(56)> (0b101 &&& 0b110) |> IO.inspect(base: :binary)
0b100
4
```

`&&&` 演算子より `|>` 演算子のほうが結合が強いので `&&&` 演算の方を括弧で括っています。

負の数を使うことはあまりないと思いますが、ビット長が不定の場合で上位に 1 が並んでいるようなビット列を表現する場合は便利です。例えば下2ビットだけ0に落としてそれ以外はそのままにしたいようなときは、第1引数にマスクする bit を `0b11` として、こういう風にも使えます。

```exs
iex(64)> (~~~0b11 &&& 0b10101010) |> IO.inspect(base: :binary)
0b10101000
168
```

これビット長が8bitと分かっているならマスクビットを8bitにしてこういう風に書けます。

```exs
iex(65)> (0b11111100 &&& 0b10101010) |> IO.inspect(base: :binary)
0b10101000
168
```

しかしこれ後ろのビット長が変わると失敗します。以下の例では先頭の2ビットが　`0`　に落とされてしまいます。

```exs
iex(66)> (0b11111100 &&& 0b1010101010) |> IO.inspect(base: :binary)
0b10101000
168
```

なので、こちらの書き方のほうが可変長ビットに対して汎用性があります。

```exs
iex(67)>  (~~~0b11 &&& 0b1010101010) |> IO.inspect(base: :binary)   
0b1010101000
680
```

## bor/2 (|||/2) 関数
2進数表現でのビット単位での論理和をとる関数です。名前は Binary OR から来てるのでしょう。

```exs
iex(68)> (0b0 ||| 0b1) |> IO.inspect(base: :binary)
0b1
1
iex(69)> (0b101 ||| 0b110) |> IO.inspect(base: :binary)
0b111
7
iex(70)> bor(0b0, 0b1) |> IO.inspect(base: :binary)       
0b1
1
iex(71)> bor(0b101,  0b110) |> IO.inspect(base: :binary)        
0b111
7
```

これも `~~~` と組合せて、下位ビットはそのままで上位ビットを 1...1 とするような演算を行えます。以下では下2bitを残して上位ビットを 1 にしています。結果が2の補数表現で分かりにくいですが 111111...1110 になっています。

```exs
iex(72)> (~~~0b11 ||| 0b10101010) |> IO.inspect(base: :binary)  
-0b10
-2
```

## bxor/2 (^^^/2) 関数
2進数表現でのビット単位での排他的論理和をとる関数です。関数名は Binary eXclusive OR からでしょう。

なおこの `bxor` に対応する二項演算子の `^^^` のみ deprecated です。公式マニュアルにはこの演算子については書いておらず、ソースコード見ないと存在すら分かりません。一応使えはしますが depredated である旨の Warning が出ます。なにかの理由があるのでしょう。だれか知ってたら教えて下さい。

```exs
iex(77)> bxor(0b1100, 0b0101) |> IO.inspect(base: :binary) 
0b1001
9
iex(78)> (0b1100 ^^^ 0b0101) |> IO.inspect(base: :binary)
warning: ^^^ is deprecated. It is typically used as xor but it has the wrong precedence, use Bitwise.bxor/2 instead
  iex:78

0b1001
9
```

これも `~~~` と組合せて任意の上位ビットを反転して、下位の固定長のビットは反転しない、という演算にできます。

```exs
iex(79)> bxor(~~~0b11, 0b10101010) |> IO.inspect(base: :binary)
-0b10101010
-170
iex(80)> bxor(~~~0b11, 0b10) |> IO.inspect(base: :binary)
-0b10
-2
```

そしてこれも相変わらず分かりにくいです。最初のは `1111...11101010110` で、次のは `1111...10` になってます。

## bsl/2 (<<</2) 関数
2進数表現でのビット単位での左シフトをする関数です。第1引数をビット列に見立てて第2引数分の左ビットシフトをします。最下位ビット (LSB) には 0 が入ります。関数名は Binari Shift Left と思います。

```exs
iex(88)> 1 <<< 0
1
iex(89)> 1 <<< 1                                              
2
iex(90)> 1 <<< 3
8
iex(91)> (0b11 <<< 0) |> IO.inspect(base: :binary)
0b11
3
iex(92)> (0b11 <<< 1) |> IO.inspect(base: :binary)
0b110
6
iex(93)> (0b11 <<< 2) |> IO.inspect(base: :binary)
0b1100
12
```

第2引数には負の数も入れられます。この場合右シフトをします。最上位ビット(MSB)には元のMSBと同じ値のビットが入ります。右シフトされる最下位ビット (LSB) は失われます。

```exs
iex(95)> (0b1100 <<< -1) |> IO.inspect(base: :binary)
0b110
6
iex(96)> (0b1100 <<< -2) |> IO.inspect(base: :binary)
0b11
3
iex(97)> (0b1100 <<< -3) |> IO.inspect(base: :binary)
0b1
1
iex(98)> (0b1100 <<< -4) |> IO.inspect(base: :binary)
0b0
0
iex(99)> (0b1100 <<< -5) |> IO.inspect(base: :binary)
0b0
0
```

第1引数には負の整数も使えます。これについては後述します。

## bsr (>>>) 関数
2進数表現でのビット単位での右シフトをする関数です。最上位ビット(MSB)には元のMSBと同じ値が入り、最下位ビット(LSB)は捨てられます。

```exs
iex(102)> (0b1100 >>> 0) |> IO.inspect(base: :binary)
0b1100
12
iex(103)> (0b1100 >>> 1) |> IO.inspect(base: :binary)
0b110
6
iex(104)> (0b1100 >>> 2) |> IO.inspect(base: :binary)
0b11
3
iex(105)> (0b1100 >>> 3) |> IO.inspect(base: :binary)
0b1
1
iex(106)> (0b1100 >>> 4) |> IO.inspect(base: :binary)
0b0
0
iex(107)> (0b1100 >>> 5) |> IO.inspect(base: :binary)
0b0
0
```

これは左シフト関数で第2引数を負にした場合と同じ動作です。右シフトで第2引数を負にすると左シフトをします。

```exs
iex(108)> (0b11 >>> -1) |> IO.inspect(base: :binary)
0b110
6
iex(109)> (0b11 >>> -2) |> IO.inspect(base: :binary)
0b1100
12
iex(110)> (0b11 >>> -3) |> IO.inspect(base: :binary)
0b11000
24
```

## シフト演算の詳細
シフトするときはMSBとLSBとに「新たに入ってくるビット」と「捨てられるビット」が出てきます。これ、慣れてないと（特に符号を表す MSB に新しいビットが来る右シフトが）不思議なので詳しく書いておきます。

なお、CPUのアセンブラをご存じの方は「算術シフト」に該当するので親しみやすいと思います。ただ CPU の場合と異なるのは Elixir の整数が不定長なので、左シフトでビット幅がいくらでも（正確にはプロセスのヒープが許す限り）伸びていくことです。

### 負数の左シフト
`<<<` も `>>>` も第1引数に負数をとることができます。以下では -1 を左シフトしてみます。-1 は2の補数表現で `1111....1111` とすべてのビットが 1 になってます。

```
iex(111)> (-1 <<< 0) |> IO.inspect(base: :binary)            
-0b1
-1
iex(112)> (-1 <<< 1) |> IO.inspect(base: :binary) 
-0b10
-2
iex(113)> (-1 <<< 2) |> IO.inspect(base: :binary) 
-0b100
-4
iex(114)> (-1 <<< 3) |> IO.inspect(base: :binary) 
-0b1000
-8
```

これは上から順番に10進数で -1, -2, -4, -8 と、2進数で `1111....1111`, `1111....1110`, `1111....1100`, `1111....1000` となってます。左に1ビットずつシフトして LSB には 0 が入っているというのは正の場合と同様の操作です。

### 負数の右シフト
今度は -10 を右シフトしてみます。-10 は2の補数表現で `1111....10110` です。

```exs
iex(115)> (-10 >>> 0) |> IO.inspect(base: :binary)           
-0b1010
-10
iex(116)> (-10 >>> 1) |> IO.inspect(base: :binary)
-0b101
-5
iex(117)> (-10 >>> 2) |> IO.inspect(base: :binary)
-0b11
-3
iex(118)> (-10 >>> 3) |> IO.inspect(base: :binary)
-0b10
-2
iex(119)> (-10 >>> 4) |> IO.inspect(base: :binary)
-0b1
-1
iex(120)> (-10 >>> 5) |> IO.inspect(base: :binary)
-0b1
-1
```

順に `1111....10110`,  `1111....11011`,  `1111....11101`, `1111....11110`,  `1111....11111`,  `1111....11111` となってます。最上位ビット (MSB) から元の MSB と同じ値の 1 が入ってきて、最下位ビット (LSB) が捨てられているのが分かります。

# まとめ
ビット操作をする上で欠かせない Bitwise を使ってみました。動作自体は簡単です。しかし Elixir の整数を対象としているため、2の補数表現で負数の上位ビットが連続した1になってること、その10進数表示からはビット列のパターンが分かりにくいことが欠点です。なお、`IO.inspect` の `base: :binary` オプションで見た場合に `-0b` 部分を 1 の連続列とみなすとビットパターンがすぐに分かることを見つけました。

さて、明日の [#NervesJP Advent Calendar 2021](https://qiita.com/advent-calendar/2021/nervesjp) の記事は再び [@torifukukaiou](https://qiita.com/torifukukaiou) さんの [asdfでよく使うコマンド](https://qiita.com/torifukukaiou/items/9009191de6873664bb58) です。お楽しみに！


# 参考文献

- [Elixir Bitwise ドキュメント](https://hexdocs.pm/elixir/Bitwise.html)
- [Elixir Bitwise コード](https://github.com/elixir-lang/elixir/blob/main/lib/elixir/lib/bitwise.ex)
- [The Erlang Runtime System 整数の表現](https://blog.stenmans.org/theBeamBook/#_tags_for_immediates)
- [WikiPedia 2の補数](https://ja.wikipedia.org/wiki/2の補数)