カテゴリー
シェルコマンドを使って学ぶビット演算(&、|、^、~等)の総復習
※ 当ページには【広告/PR】を含む場合があります。
2021/10/25
2022/01/21

組込開発者には避けて通れない独特な実装をする
たまにビット演算を使うプログラミングに鉢合わせる際には、意外と「あー...この記号ってどういう風に計算するんだっけ?」、という方も結構いると思われます。
ビット演算を手軽に復習したり、計算を試せるツールを欲しい時にサッと出せるように手元に置いておきたいという方も多いでしょう。
そんなときこそ
Bashならほとんどの端末にインストールされている(またはインストールできる)のですぐに使うことができます。
後は今回の記事で紹介するテクニックさえ覚えておけば、Bashの使えるターミナルを立ち上げるだけで、ビット演算のお勉強をすることができるようになります。
基礎編
まずはここでビット演算をする上で欠かすことのできない、Bashで2進法を扱うためのコマンド操作をしっかりと理解しておきましょう。
2進法を10進法に表示する
通常Bashで扱う整数は全て10進法の扱いですが、数の頭に
N#
この記事では2進法(
2#
#👇2進法のつもり(10進法では86)
$ A=01010110
#👇これは当然Aの中身は文字として扱われる
$ echo $A
01010110
#👇2進法と明示して、10進法表示にする
$ echo $((2#${A}))
86
bashでは簡単な計算ならば
$((演算式))
なおデフォルトで
$((演算式))
いちいち変数を置くのも面倒ですので、上のスクリプトをワンライナーで使うと、
$ 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、両方1ならば1、両方0は0を返す
記号 ^ ... XOR演算子:
排他的論理和。
どちらか一方が1ならば1、両方1か0ならば0を返す
記号 ~ ... NOT演算子:
1ならば0、0ならば1を返す。
補数表現での、~N = -(N+1)と等価
AND演算子
この記事では簡単のため、4ビットの2進数で話を進めていきます。
まずは例として
0110
1011
&
$ 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
1001
0111
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
$ 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)
$ 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言語等でビット演算が活躍します。
例えば$$x$$という変数をビット演算した結果を再度変数$$x$$に拘束したい場合以下のよう書けます。
uint8_t x = 0b00001011;
x = x | (1 << 2);
ちょっとしたことですが、ビット演算して代入する、という操作は以下のように書き直せます。
x |= (1 << 2);
このように書くと、
|=
どちらかいえばオペレーターというよりシンタックスシュガーというべきものですが、Bashではこのような使い方はできません。
知っているとちょっとだけ楽ができるかも知れません。
ビット演算(レベル3)
頻度は低いけれど、覚えておいたら何かの際に役に立つかも...的なビット演算の応用テクニックも一部取り上げておきます。
2^Nの剰余を取得
$$2^N$$ビット区切りで商余り(余剰)を求めるパターン:
二進法 & (1 << N) - 1
例えば4ビットの数として、
1101
3ビット($$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)
と書き表すことができます。
ただし、比較する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言語と同じようなビット演算を再現することが可能になっていることが、この記事を呼んでいただけると分かると思います。
普段は組込開発から離れて久々に趣味でやると、ビット演算の作法がどうしても思い出せないという方には必見です。
記事を書いた人
ナンデモ系エンジニア
主にAngularでフロントエンド開発することが多いです。 開発環境はLinuxメインで進めているので、シェルコマンドも多用しております。 コツコツとプログラミングするのが好きな人間です。
カテゴリー