これは #NervesJP Advent Calendar 2021 の18日目です。昨日は @torifukukaiou さんの毎日自動更新！　記事の舞台裏 -- Nerves on Raspberry Pi 2大活躍 🚀🚀🚀 でした。

はじめに

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

概要

Bitwise は整数に対して bit 演算をする関数群です。Erlang の関数に対するマクロで記述されていて、ガードで使えるという特徴があります。

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

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

宣言

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

iex(1)> use Bitwise
Bitwise

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

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

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

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 する際に指定します。

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 に対しても使うことができません。

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 から来ているようです。

iex(10)> ~~~0
-1

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

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

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 の返り値、すなわちパイプで受け取った前の関数の返り値そのものです。

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 を使っても同様の結果が返ります。

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の補数表現に対してビット反転をします。

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回適用するともとに戻ります。

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 から来てるものと思います。

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

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

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 として、こういう風にも使えます。

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

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

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

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

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

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

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

bor/2 (|||/2) 関数

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

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 になっています。

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

bxor/2 (^^^/2) 関数

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

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

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

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

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 と思います。

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) は失われます。

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)は捨てられます。

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引数を負にすると左シフトをします。

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 です。

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 の記事は再び @torifukukaiou さんの asdfでよく使うコマンドです。お楽しみに！

参考文献

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

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