(x >> k) & 1で x の k ビット目を取り出せる- Bash の整数は符号付き 64 ビットなので,
1 << 63は符号ビットだけが立った int64 の最小値 \(-2^{63}\) として表示される m & (m - 1)は一番下の 1 のビットを消す操作で,結果が 0 なら 1 のビットは 1 個だけ- 2の冪乗判定では,0 と \(-2^{63}\) を除外するために
m > 0が必要 &は==より優先順位が低いので,(m & (m - 1)) == 0のように括弧で囲む- 同じビット列でも,
%dなら符号付き,%uなら符号なしとして表示される
Bash の算術式 $(( )) / (( )) では,C と同じようにシフト演算子 << >> やビット演算子 & | ^ を使えます.本記事では,ビット演算の基本と符号付き整数の落とし穴を整理します.
x=10; k=1
echo $(( (x >> k) & 1 )) # k ビット目を取り出す
echo $(( 1 << 63 ))
# -9223372036854775808
m=16; (( m > 0 && (m & (m - 1)) == 0 )) && echo "2の冪乗" || echo "2の冪乗ではない"
printf '%u\n' $(( 1 << 63 ))
# 9223372036854775808前提として,Bash の整数は符号付き 64 ビット(2の補数)で表されます.
- 表現できる範囲:\(-2^{63}\) 〜 \(2^{63}-1\)
- 最上位ビット(63 ビット目)が符号ビット
- 符号なし整数としての演算は用意されていない
k ビット目を取り出す
x=10; k=1
echo $(( (x >> k) & 1 )) # → 1ビット番号は最下位ビット(LSB)を 0 ビット目として数えます.
| ステップ | 式 | 2進数 | 10進数 |
|---|---|---|---|
| 元の値 | x |
1010 |
10 |
| 右シフト | x >> 1 |
0101 |
5 |
| マスク | & 1 |
0001 |
1 |
x >> kで k ビット目を最下位ビットの位置まで右へ移動する& 1で最下位ビット以外を 0 にする
\(10 = 1010_{(2)}\) の各ビットは下から 0, 1, 0, 1 なので,1 ビット目は 1 です.同様に k=0 なら 0,k=2 なら 0,k=3 なら 1 になります.
x=10; for k in 0 1 2 3; do echo -n "$(( (x >> k) & 1 ))"; done; echo
# 01011 << 63 が負になる理由
echo $(( 1 << 63 ))
# -92233720368547758081 を 63 ビット左へシフトすると,ビット列は次のようになります.
1000 0000 0000 ... 0000 (64ビット,16進で 0x8000000000000000)
立っているのは符号ビットである 63 ビット目だけです.2の補数では,最上位ビットの重みは \(-2^{63}\) なので,このビット列は
\[ -2^{63} = -9223372036854775808 \]
つまり int64 の最小値を表します.
ここで重要なのは,「\(2^{63}\) を計算したらオーバーフローして値が壊れた」のではなく,ビット列そのものは \(2^{63}\) と同じで,Bash がそれを符号付き整数として解釈して表示しているという点です.
2の冪乗かどうかの判定
m=16; (( m > 0 && (m & (m - 1)) == 0 )) && echo "2の冪乗" || echo "2の冪乗ではない"
# 2の冪乗m & (m - 1) の仕組み
ある整数から 1 を引くと,一番下に立っている 1 のビットが 0 になり,それより下のビットはすべて 1 になります.そのため元の値との AND を取ると,「一番下の 1」だけが消えます.
m = 16 = 1 0000
m - 1 = 15 = 0 1111
m & (m - 1) = 0 0000 → 0
2の冪乗は 1 のビットがちょうど 1 個しかないので,それを消すと 0 になります.2の冪乗でない数は 1 のビットが 2 個以上あるので,0 にはなりません.
m = 12 = 1100
m - 1 = 11 = 1011
m & (m - 1) = 1000 → 0 ではない
m > 0 が必要な理由
(m & (m - 1)) == 0 だけでは,次の2つの値を誤って「2の冪乗」と判定してしまいます.
m |
m の2進数 |
m - 1 の2進数 |
m & (m - 1) |
|---|---|---|---|
0 |
000...0 |
111...1(\(-1\)) |
0 |
| \(-2^{63}\) | 100...0 |
011...1(\(2^{63}-1\)) |
0 |
\(-2^{63}\) は前節の 1 << 63 で得た値です.ビット列としては 1 が 1 個しか立っていないため,m & (m - 1) の判定をすり抜けます.
表の m - 1 の列は,どちらも2の補数での減算の結果です.\(0 - 1\) は全ビットが 1 の \(-1\) になります.\(-2^{63} - 1\) は int64 の下限を下回るため,上限の \(2^{63}-1\) に回り込みます(アンダーフロー).2の補数による減算とアンダーフローは コンピューターは数値をどう表現しているのか (2) で詳しく扱っています.
for m in 16 12 0 $(( 1 << 63 )); do
(( (m & (m - 1)) == 0 )) && echo "$m: 2の冪乗" || echo "$m: 2の冪乗ではない"
done
# 16: 2の冪乗
# 12: 2の冪乗ではない
# 0: 2の冪乗
# -9223372036854775808: 2の冪乗m > 0 を先に置くことで,0 と負の数を除外しています.
括弧を省略してはいけない理由
演算子の優先順位は C と同じで,- > == > & の順です.そのため m & m - 1 == 0 と書くと m & ((m - 1) == 0) と解釈され,意図しない結果になります.
m=16
echo $(( m & m - 1 == 0 )) # 16 & (15 == 0) = 16 & 0 → 0
echo $(( (m & (m - 1)) == 0 )) # → 1ビット演算子と比較演算子を組み合わせるときは,(m & (m - 1)) == 0 のように必ず括弧で囲みます.
(( )) && ... || ... の動き
(( 式 ))は式の値が 0 以外なら終了ステータス 0(成功),0 なら終了ステータス 1(失敗)を返すA && B || Cは if-else の簡易表現として使われる
ただし A && B || C は,A が成功しても B が失敗すると C が実行されます.ここでは B が echo なので実質問題ありませんが,B が失敗しうるコマンドの場合は if ...; then ...; else ...; fi を使うのが安全です.
printf '%u' で符号なしとして表示する
printf '%u\n' $(( 1 << 63 ))
# 9223372036854775808$(( 1 << 63 )) の値は前述のとおり 0x8000000000000000 です.printf の %u はこれを符号なし整数として解釈して表示するので,\(2^{63} = 9223372036854775808\) になります.
| 解釈 | 書式 | 表示 |
|---|---|---|
| 符号付き | echo / %d |
-9223372036854775808 |
| 符号なし | %u |
9223372036854775808 |
| 16進 | %x |
8000000000000000 |
printf '%d %u %x\n' $(( 1 << 63 )) $(( 1 << 63 )) $(( 1 << 63 ))
# -9223372036854775808 9223372036854775808 8000000000000000ビット列は同じで,解釈だけが異なります. Bash の算術は符号付きでしか計算しないため,符号なしの値として確認したいときは printf '%u' で表示を切り替えます.