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

※ 当ページには【広告/PR】を含む場合があります。

2021/10/25

2022/01/21

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

『ビット演算』

。

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

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

そんなときこそ

「Bash」

を使いましょう。

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

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

【効果的学習法レポート】シェルスクリプトをこれから学びたい人のためのオススメ書籍＆教材特集

基礎編

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

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

【効果的学習法レポート】シェルスクリプトをこれから学びたい人のためのオススメ書籍＆教材特集

ビット演算(レベル１)

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

４つの基礎論理演算子

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

開く/閉じる

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

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

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

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

AND演算子

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

まずは例として

0110

と

1011

の論理積を

&

演算子で求めましょう。

開く/閉じる

            
            $ echo 'obase=2;' $((2#0110 & 2#1011)) | bc | xargs printf "%04d\n"
0010

と論理積の答えは

0010

と出てきました。

これは

開く/閉じる

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

OR演算

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

|

演算子に置き換えて、

開く/閉じる

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

となります。

開く/閉じる

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

XOR演算

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

^

演算子に置き換えて、

開く/閉じる

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

となります。

開く/閉じる

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

NOT演算子

演算子

~

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

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

開く/閉じる

            
            $ echo 'obase=2;' $((~2#0110)) | bc
-111

結果は

0110

のビット反転が

-111

として出力されています。

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

開く/閉じる

のようになることだったのですが、結果には何やら

−(マイナス)

が付いております。

このマイナスは負というより、

2進数での補数

を表していることに注意が必要です。

ビット演算では、２進数の頭に

−

記号が付いている場合、補数として捉えます。

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

実際、

0110

をビット反転させた

1001

に

0111

を足し算すると、

開く/閉じる

となります。

この理屈から無理やり５ビット目(

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乗倍することと等価

開く/閉じる

            
            #👇１ビット左シフト
$ echo 'obase=2;' $((2#0110 << 1)) | bc | xargs printf "%04d\n"
1100

#👇１ビット右シフト
$ 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

などとすると良いでしょう。

【効果的学習法レポート】シェルスクリプトをこれから学びたい人のためのオススメ書籍＆教材特集

ビット演算(レベル２)

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

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

Nビット目の取得

パターン:

(２進数 >> 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

各ビットが個別に抽出されていることが分かります。

また、別のパターン:

２進数 & (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、１なら非ゼロ、という判定で使います。

Nビット目に書き込みをする

先程の読み出しと同じような考え方で、書き込みのパターン:

２進法 | (1 << N)

とすると、(N+1)ビット目を1に変えることができます。

開く/閉じる

            
            $ echo 'obase=2;' $(( 2#1011 | (1 << 2) )) | bc
1111

対して(N+1)ビット目を0にしたい場合の書き込みパターン:

２進法 &~ (1 << N)

とします。

開く/閉じる

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

Nビット目を反転

(N+1)ビット目を反転させたいときに使うパターン:

２進法 ^ (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言語等でビット演算が活躍します。

例えば

x

という変数をビット演算した結果を再度変数

x

に拘束したい場合以下のよう書けます。

開く/閉じる

            
            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^Nの剰余を取得

2^N

ビット区切りで商余り(余剰)を求めるパターン:

二進法 & (1 << N) - 1

で循環整数を表現することができます。これはさほど難しい操作では有りません。

例えば４ビットの数として、

1101

を考えてみます。1101は10進法で13です。

３ビット(

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言語で

2^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

で

0 \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)

と書き表すことができます。

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

偶奇性

値が偶数か奇数であることを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言語と同じようなビット演算を再現することが可能になっていることが、この記事を呼んでいただけると分かると思います。

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

記事を書いた人

記事の担当:taconocat

ナンデモ系エンジニア

主にAngularでフロントエンド開発することが多いです。開発環境はLinuxメインで進めているので、シェルコマンドも多用しております。コツコツとプログラミングするのが好きな人間です。

【効果的学習法レポート】シェルスクリプトをこれから学びたい人のためのオススメ書籍＆教材特集