シェルコマンドを使って学ぶビット演算(&、|、^、~等)の総復習


2021/10/25
2022/01/21
蛸壺の技術ブログ|シェルコマンドを使って学ぶビット演算(&、|、^、~等)総復習

組込開発者には避けて通れない独特な実装をする
ビット演算

たまにビット演算を使うプログラミングに鉢合わせる際には、意外と「あー...この記号ってどういう風に計算するんだっけ?」、という方も結構いると思われます。

ビット演算を手軽に復習したり、計算を試せるツールを欲しい時にサッと出せるように手元に置いておきたいという方も多いでしょう。

そんなときこそ
Bashを使いましょう。

Bashならほとんどの端末にインストールされている(またはインストールできる)のですぐに使うことができます。

後は今回の記事で紹介するテクニックさえ覚えておけば、Bashの使えるターミナルを立ち上げるだけで、ビット演算のお勉強をすることができるようになります。


基礎編

まずはここでビット演算をする上で欠かすことのできない、Bashで2進法を扱うためのコマンド操作をしっかりと理解しておきましょう。

2進法を10進法に表示する

通常Bashで扱う整数は全て10進法の扱いですが、数の頭にN#のように入れるとその基数Nに従う数として柔軟にN進法表記の数として扱うことができます。

この記事では2進法(
2#)しか使いませんが、このNは2~64までの整数が指定できます。

            
            #👇2進法のつもり(10進法では86)
$ A=01010110

#👇これは当然Aの中身は文字として扱われる
$ echo $A
01010110

#👇2進法と明示して、10進法表示にする
$ echo $((2#${A}))
86
        
bashでは簡単な計算ならば$((演算式))で行えるので、これを利用しています。

なおデフォルトで
$((演算式))の結果は10進法になることに留意してください。

いちいち変数を置くのも面倒ですので、上のスクリプトをワンライナーで使うと、

            
            $ echo $((2#01010110))
86
        
というように使います。

10進法を2進法に表示する

シェルコマンドで少し問題になるのは、10進法表記の数を2進法にしたいときです。

これには万能の計算ツール・
bcコマンドにお力添えを頂くことになります。

            
            $ echo 'obase=2;ibase=10;86' | bc
1010110

#👇入力が10進法の場合、ibaseは省略可
$ echo 'obase=2;86' | bc
1010110

#👇文字列を分離したほうが見栄えが良い(かも)
$ echo 'obase=2;' 86 | bc
1010110

#👇echoを使いたくない場合、ヒアストリング(<<<)を使う
$ bc <<< 'obase=2;'86
1010110
        
なお8ビットなど固定ビットで表示させたい場合、printfコマンドで最後にフォーマットしてから表示させると良いでしょう。

            
            #👇8ビット表示
$ echo 'obase=2;' 86 | bc | xargs printf "%08d\n"
01010110

#ヒアストリング版
$ bc <<< 'obase=2;'86 | xargs printf "%08d\n"
01010110
        

ビット演算(レベル1)

ここからBashでのビット演算の話に移ります。

4つの基礎論理演算子

まずは教科書レベルの内容を思い出して頂きながら、以下4つ理論演算子の働きをまとめます。

            
            記号 & ... AND演算子:
    論理積。
    両方1ならば1、それ以外は0を返す

記号 | ... OR演算子:
    論理和。
    どちらか一方が1ならば1、それ以外は0を返す

記号 ^ ... XOR演算子:
    排他的論理和。
    どちらか一方が1ならば1、それ以外は0を返す

記号 ~ ... NOT演算子:
    1ならば0、0ならば1を返す。
    補数表現での、~N = -(N+1)と等価
        

AND演算子

この記事では簡単のため、4ビットの2進数で話を進めていきます。

まずは例として
01101011の論理積を&演算子で求めましょう。

            
            $ echo 'obase=2;' $((2#0110 & 2#1011)) | bc | xargs printf "%04d\n"
0010
        
と論理積の答えは0010と出てきました。

これは

            
            0 1 1 0
1 0 1 1
- - - -
0 0 1 0
        
ですので、正しくAND演算が行われていることが確認できます。

OR演算

先程の例を論理和にしたものでも試してみます。

|演算子に置き換えて、

            
            $ echo 'obase=2;' $((2#0110 | 2#1011)) | bc | xargs printf "%04d\n"
1111
        
となります。

            
            0 1 1 0
1 0 1 1
- - - -
1 1 1 1
        
ですので、正しくOR演算が行われてることが分かります。

XOR演算

次に排他的論理和の例です。

^演算子に置き換えて、

            
            $ echo 'obase=2;' $((2#0110 ^ 2#1011)) | bc | xargs printf "%04d\n"
1101
        
となります。

            
            0 1 1 0
1 0 1 1
- - - -
1 1 0 1
        
ですので、正しくXOR演算が行われていそうです。

NOT演算子

演算子~はビット否定(ビット反転)を行う操作です。

とりあえず使ってみると分かりますが、理解するには少しだけ頭を使います。

            
            $ echo 'obase=2;' $((~2#0110)) | bc
-111
        
結果は0110のビット反転が-111として出力されています。

ビットの反転ですので、期待していたものは

            
            0 1 1 0
= = = =
1 0 0 1
        
のようになることだったのですが、結果には何やら−(マイナス)が付いております。

このマイナスは負というより、
2進数での補数を表していることに注意が必要です。

ビット演算では、2進数の頭に
記号が付いている場合、補数として捉えます。

復習になりますが、補数は元の数を足したときに桁上がりする最小の数のことです。

実際、
0110をビット反転させた10010111を足し算すると、

            
            0 1 0 0 1
0 0 1 1 1
- - - - -
1 0 0 0 0
        
となります。

この理屈から無理やり5ビット目(
10000)を登場させて、0110を反転させた数を表示させようとすると、

            
            $ echo 'obase=2;' $((2#10000 - 2#0111)) | bc
1001

$ echo 'obase=2;' $((2#10000 + ~2#0110)) | bc
1001
        
といった具合でしょうか。

NOT演算子でビット反転させた数と補数表現は、以下の関係式で定義させるように表裏一体です。

            
            関係式: ~N = -(N+1)
例:
    ~0110 = -0111
        
いきなりマイナスが付いて戸惑いますが、ビット演算を使う以上は、「ビット反転は補数なんだな」と見方に慣れる必要が有ります。

なお、このようにBashで補数表記からのビット反転をやらせると、少し頭をひねったことをやっていますが、c言語等では以下のようなもっと素直な方法で、補数表記(
-)の符号を反転してビット反転を実行することができます。

            
            i = ~i + 1;
//もしくは
i = (i ^ -1) + 1;
        

寄り道①〜オタマジャクシ演算子

たまに補数とNOT演算を組み合わせたオタマジャクシ演算子も折角なので触れておきましょう。

算術的な引き算を表すマイナス
-とは違い、補数を論理記号としての-は実際かなり紛らわしいので、式の文脈的に読み替えする必要があります。

ビット演算で単独で
-~~-などの演算子が出現する場合、オタマジャクシ演算子として利用されていることがあります。

補数を表す演算子と見れば、先程の関係式から少し変形して

            
            関係式: -M = ~(M-1)
        
とも書けるので、

これらの関係式を繰り返し、まず演算子
~-は、

            
            関係式: ~-R = ~~(R-1) = R-1
※ ~~ は反転の反転で元に戻す操作
        
となります。

もう一つの
-~も同様に

            
            関係式: -~S = --(S+1) = S+1
※ -- で補数の補数は元に戻す操作
        
となります。

なんと、オタマジャクシ演算子では、1ビットを足したり引いたりするのと同じことができるのです!

            
            $ echo 'obase=2;' $((~-2#0110)) | bc | xargs printf "%04d\n"
0101

$ echo 'obase=2;' $((-~2#0110)) | bc | xargs printf "%04d\n"
0111
        
他の言語などでforループ構文に使うi++などのインクリメント演算子の代わりにこのオタマジャクシ演算子が使えます。

寄り道②〜Javascriptでは小数点以下切り落としに使う

Javascriptでも基本的にビット演算を使うことができます。

ただしJavascriptは型付けのない言語ですので、数値の型にはintやfloatなどの区別はありません(厳密にはプリミティブ型のNumber)。

それでこのJavascriptの数値に
~~演算子を作用させると、面白いことが起こります。

            
            console.log(~~0.7);
console.log(~~3.54);
console.log(~~6317.4906);
console.log(~~-12.76);
console.log(~~-1532.076);
//👇実行結果
0
3
6317
-12
-1532
        
というように、小数点以下切り捨て、で符号は維持されるようになります。

これはJavascript(ECMAScript)の仕様で、数値をビット演算する場合には最初に32ビット整数(Int32)で扱われるために、恒等操作
~~を作用させると小数点以下が切り落とされて元に戻るという話のようです。

通常、符号付きの数値の小数切り捨てを実装したいときに、Math.floor(正符号で小数点以下切り捨て)とMath.ceil(負符号で小数点以下切り捨て)を条件分けしないといけません。

このテクニックを知っておくと、たったの2文字で符号無視の小数点以下切り捨てができるので、ユースケースがはまると、とても便利に使えます。

ビットシフト

シフト演算で各ビットの位置を左右に移動することができます。

            
            記号 << N ... 左シフト演算子:
    各ビットをN桁左にシフトさせる。
    算術的にはNビットのシフトで2のN乗倍することと等価

記号 >> N ... 右シフト演算子:
    各ビットをN桁右にシフトさせる。
    算術的にはNビットのシフトで1/2のN乗倍することと等価
        
            
            #👇1ビット左シフト
$ echo 'obase=2;' $((2#0110 << 1)) | bc | xargs printf "%04d\n"
1100

#👇1ビット右シフト
$ echo 'obase=2;' $((2#0110 >> 1)) | bc | xargs printf "%04d\n"
0011
        
見ての通りで、シフトする度に桁数が空くビットには0が補われます。

なおBashの左シフトは制限がなく延々とビットの桁も左シフトするので、便宜上sedコマンドなどを使って、

            
            #👇sedで下位4ビットだけ取り出し
$ echo 'obase=2;' $((2#1111 << 3)) | bc | sed -r 's/.*(.{4})$/\1/'
1000

#👇(別解)revで下位4ビットを後ろ読みして戻す
$ echo 'obase=2;' $((2#1111 << 2)) | bc | rev | cut -c 1-4 | rev
1100
        
などとすると良いでしょう。


ビット演算(レベル2)

先程の節では、基本となるビット演算子の使い方をメインで解説してみました。

この節ではc言語等で組込の実装で良く目にするいくつかの実用テクニックに焦点を当てます。

Nビット目の取得

パターン: (2進数 >> N) & 1で特定の(N+1)ビット目が0か1かを読み出しするときに使います。

            
            $ echo 'obase=2;' $(( (2#1011 >> 0) & 1 )) | bc
#もしくは echo 'obase=2;' $(( 2#1011 & 1 )) | bc
1
$ echo 'obase=2;' $(( (2#1011 >> 1) & 1 )) | bc
1
$ echo 'obase=2;' $(( (2#1011 >> 2) & 1 )) | bc
0
$ echo 'obase=2;' $(( (2#1011 >> 3) & 1 )) | bc
1
        
各ビットが個別に抽出されていることが分かります。

また、別のパターン:
2進数 & (1 << N)が利用されることもあります。

            
            $ echo 'obase=2;' $(( 2#1011 & (1 << 0) )) | bc
1
$ echo 'obase=2;' $(( 2#1011 & (1 << 1) )) | bc
10
$ echo 'obase=2;' $(( 2#1011 & (1 << 2) )) | bc
0
$ echo 'obase=2;' $(( 2#1011 & (1 << 3) )) | bc
1000
        
こちらのパターンでは、(N+1)ビット目がゼロなら0、1なら非ゼロ、という判定で使います。

Nビット目に書き込むする

先程の読み出しと同じような考え方で、書き込みのパターン: 2進法 | (1 << N)とすると、(N+1)ビット目を1に変えることができます。

            
            $ echo 'obase=2;' $(( 2#1011 | (1 << 2) )) | bc
1111
        
対して(N+1)ビット目を0にしたい場合の書き込みパターン: 2進法 &~ (1 << N)とします。

            
            $ echo 'obase=2;' $(( 2#1011 &~ (1 << 1) )) | bc
1001
        

Nビット目を反転

(N+1)ビット目を反転させたいときに使うパターン: 2進法 ^ (1 << N)もあります。

            
            $ echo 'obase=2;' $(( 2#1011 ^ (1 << 0) )) | bc
1010
        
これで狙ったビットの桁の数だけひっくり返すことができます。

全ビットの反転

ビットを一つ一つ反転するのではなく、一気に全部のビットを反転させたいときがあります。

            
            $ echo 'obase=2;' $(( ~2#1011 )) | bc
$ echo 'obase=2;' $(( 2#1011 ^~ 0 )) | bc
-1100
        
これは上記で説明した通りビット反転後(ここでは0100)の補数表記ですので不安になることは有りません。

補数表記が嫌で、どうしてもシェルコマンドで反転後の形を得たいなら、

            
            $ echo 'obase=2;' $((2#10000 - 2#1100)) | bc | xargs printf "%04d\n"
#👇でも良い
#$ echo 'obase=2;' $(( (1<<4) - 2#1100)) | bc | xargs printf "%04d\n"
0100
        
と確認することができます。

Nビットマスクの作成

特定のビットを抜き出したい時に利用するマスク処理に使うマスクもサクッと作成できます。

1ビット目からNビット目までがすべて1である値を生成します。

Nビットまでのマスク生成パターン:
(1 << N) - 1を使います。

            
            $ echo 'obase=2;' $(( (1<<0) - 1)) | bc | xargs printf "%04d\n"
0000
$ echo 'obase=2;' $(( (1<<1) - 1)) | bc | xargs printf "%04d\n"
0001
$ echo 'obase=2;' $(( (1<<2) - 1)) | bc | xargs printf "%04d\n"
0011
$ echo 'obase=2;' $(( (1<<3) - 1)) | bc | xargs printf "%04d\n"
0111
        

余談〜c言語等で扱う時のオペレーター

組込開発ではc言語等でビット演算が活躍します。

例えば
xxという変数をビット演算した結果を再度変数xxに拘束したい場合以下のよう書けます。

            
            uint8_t x = 0b00001011;
x = x | (1 << 2);
        
ちょっとしたことですが、ビット演算して代入する、という操作は以下のように書き直せます。

            
            x |= (1 << 2);
        
このように書くと、|=もオペレーターっぽく見えてきます。

どちらかいえばオペレーターというよりシンタックスシュガーというべきものですが、Bashではこのような使い方はできません。

略記なし

略記型

a = a | b

a |= b

a = a & b

a &= b

a = a ^ b

a ^= b

a = a << N

a <<= N

a = a >> N

a >>= N

知っているとちょっとだけ楽ができるかも知れません。


ビット演算(レベル2)

頻度は低いけれど、覚えておいたら何かの際に役に立つかも...的なビット演算の応用テクニックも一部取り上げておきます。

2^Nの剰余を取得

2N2^Nビット区切りで商余り(余剰)を求めるパターン: 二進法 & (1 << N) - 1で循環整数を表現することができます。これはさほど難しい操作では有りません。

例えば4ビットの数として、
1101を考えてみます。1101は10進法で13です。

3ビット(
0231(=7)0 \sim 2^3-1(=7) )で余剰を求めてみます。

            
            $ echo 'obase=2;' $((13)) | bc
#👇10進法で13を2進法で
1101

$ echo 'obase=2;' $((13 & (1 << 3))) | bc
#echo 'obase=2;' $((2#1101 & (1 << 3))) | bc でも良い
#👇8(商の部分)
1000

$ echo 'obase=2;' $((13 & (1 << 3) - 1)) | bc
#echo 'obase=2;' $((2#1101 & (1 << 3) - 1)) | bc でも良い
#👇5(余剰部分)
101
        
c言語で2N2^Nビットの循環整数を生成する場合、

            
            count++;
count &= (1<<N) - 1;
        
などとして利用します。

シェルスクリプトで循環整数を実現しようとすると、例えば以下のようなスクリプトを実行することで確認できます。

            
            #!/bin/bash
A=0
for i in `seq 16`; do
echo $(($A & (1 << 3) - 1)) | bc
A=$(echo 'obase=2;' $((-~2#$A)) | bc)
done
        
このスクリプトを走らせると、

            
            $ ./cycle.sh
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
        
02N10 \sim 2^N-1の間で循環整数が生成されています。

等価性

XOR演算子を使うと、2つの値の等価性を簡単に判定できます。

データの中身そのものを比較していますので、アルゴリズム的に高速に動作します。

            
            #👇2値が一致する場合にはゼロを返す
$ echo 'obase=2;' $((2#0110 ^ 2#0110)) | bc
0

#👇2値が一致しない場合には非ゼロを返す
$ echo 'obase=2;' $((2#0101 ^ 2#0110)) | bc
11
        
c言語で用いる際も、

            
            //👇xとyが同じならtrue
(x ^ y) == 0;
//👇もしくは以下でも同じ
!(x ^ y)
        
と書き表すことができます。

ただし、比較する2つの変数は同じデータ型でないと等価性の比較はできません。

偶奇性

値が偶数か奇数であることを1ビット目の数を確認することで判定可能です。

            
            #👇奇数の場合には1を返す
$ echo 'obase=2;' $((2#0101 & 1)) | bc
#echo $((7 & 1)) | bc と同じ
1

#👇偶数の場合には0を返す
$ echo 'obase=2;' $((2#0110 & 1)) | bc
#👇echo $((6 & 1)) | bc と同じ
0
        
c言語などの実装で使うと、

            
            //👇奇数の場合はtrue
(n & 1) == 1;
        
のように使えます。

理屈的にはかなり単純ですが、後方から
& 1を作用させるだけなので、ビット演算を知らない人からすると何が起こっているか分からないと思います。

スワップ

c言語において、2つの変数内の値を交換するショートハンドです。

            
            //👇順に書くと
x ^= y;
y ^= x;
x ^= y;

//👇ワンライナーでスワップ
x^=y^(y=x);
        
スワップもワンライナーで書かれると、知らなければ何かの呪文に見えるかも知れません...。


まとめ

以上、ビット演算のテクニックを学習する目的で、シェルコマンドで組込開発で良く使うテクニックも併せてビット演算の基本から応用的な方法をまとめていきました。

意外に思うかも知れませんが、BashはほぼC言語と同じようなビット演算を再現することが可能になっていることが、この記事を呼んでいただけると分かると思います。

普段は組込開発から離れて久々に趣味でやると、ビット演算の作法がどうしても思い出せないという方には必見です。