読者です 読者をやめる 読者になる 読者になる

倭マン's BLOG

くだらない日々の日記書いてます。 たまにプログラミング関連の記事書いてます。 書いてます。

いまさら!? ビット演算 ~ビットシフト編~

Java

前回に引き続き、今回はビットシフトに関連する演算子を見ていきます。 ビットシフト演算子には、左シフト (<<)、右シフト (>>)、符号なし右シフト (>>>) の3つがあります。 最初は右シフトと符号なし右シフトの違いが分かりにくいかと思いますが、動作に違いが出てくるのは負の値のときだけです。 また、それぞれのビットシフト演算子には対応する代入演算子 <<=, >>=, >>>= もあります。

準備の復習
前回に引き続いて、この記事でもコード中では 0 の代わりにアンダーバー (_) を使います(単なる見易さのため)。 前回定義した b() メソッドと定数 ___, lll を今回も使うので、定義を再掲しておきます。 加えて、ビットシフトを施す int 値 m, n も併せて定義しておきます:

    static int b(String s){
        return Integer.parseUnsignedInt(s.replaceAll("_", "0"), 2);
    }

    static final String ___ = "________"+"________"+"________";  // 24個の0
    static final String lll = ___.replaceAll("_", "1");          // 24個の1

    static final int m = b(___+"___11_1_");  // ==  26
    static final int n = b(lll+"111__11_");  // == -26

m, n の26, -26 という値には特に深い意味はありません。 シフトされるのが分かりやすそうなビット列だというだけです。

左シフト (<<)

まずは簡単な左シフトから。 左シフト演算子は「<<」で*1、この演算子の後に移動数(int 値)を与えます。

正の値
とりあえず正の int 値 m (= 26) に対して移動数 0~3 で試してみましょう:

// 正の int 値 m (== 26) に対して
assert( (m << 0) == b(___+"___11_1_") );  //  26 == m
assert( (m << 1) == b(___+"__11_1__") );  //  52
assert( (m << 2) == b(___+"_11_1___") );  // 104
assert( (m << 3) == b(___+"11_1____") );  // 208

0シフトは m と同じ値を返すので意味はありませんが(むしろ警告が出たりしますが)、元のビットを明示するために書いてます。 シフト数を増やすごとに左にビットが移動していくのが分かりますね。 一番右には常に0が補完されます。

ビットシフトを行うときにあまり気にする必要はないかも知れませんが、左シフトが数値的には何をしているかを見ておきましょう。 10進数で末尾に0を付けて左へ桁をずらすと10倍するのと同じように、数値の2進数表現であるビット列で左に1だけシフトを行うと数値的には2倍していることになります。 というか、ただそれだけ。 上記の例の右に数値をコメントとして入れていますが、順に2倍されていることが分かりますね。 つまり、 { x } { p } だけ左シフトすると値は  { 2^p x } となります。

さて、さらにビットを左へシフトさせていって、ビットの左端まで行くとどうなるかも見ておきましょう:

// さらに正の int 値 m に対して
assert( (m << 26) == b("_11_1___"+ ___) );  //  1744830464
assert( (m << 27) == b("11_1____"+ ___) );  //  -805306368
assert( (m << 28) == b("1_1_____"+ ___) );  // -1610612736
assert( (m << 29) == b("_1______"+ ___) );  //  1073741824

ここでは右側が0ばかりになるので、右側に24個の0である「___」を付けてます。 まぁ、左端に到達するまでそのまま左へシフトしていくだけですね。 左端を超えた場合は単に落とされます。 左端のビットは符号を表すので符号ビットと呼ばれますが、左シフトでは特に関係なくビットを移動さます。 結果として、移動後に符号が変わったりします。 上記の例で「m << 27」は負になっていますね*2。 移動数がある程度以上大きくなると値は0になります。

さて、移動数は int 値なので負でもいいのか試してみましょう:

// 通常、コーディング・エラー
assert( (m << -1) == b("________"+ ___) );  // 0
assert( (m << -2) == b("1_______"+ ___) );
assert( (m << -3) == b("_1______"+ ___) );

例外が投げられたりはしませんが、マイナスの左シフトだからって右に移動してくれるワケではないようですね。 自分の環境では警告が出たし、(仕様書を確認したわけではないけど)普通に JVM 実装に依りそうな気もします。 基本的には使わない方がいいでしょうけど、移動数に変数を指定すると負の数を与えてしまうこともあるかもしれないので、一応結果を載せておきました*3

負の値
次は移動させる int 値が負の n で場合を見ていきましょう。 

// 負の int 値 n (== -26) に対して
assert( (n << 0)  == b(lll+"111__11_") );  //  -26 == n
assert( (n << 1)  == b(lll+"11__11__") );  //  -52
assert( (n << 2)  == b(lll+"1__11___") );  // -104
assert( (n << 3)  == b(lll+"__11____") );  // -208

まぁ、特に問題はないと思います。 負の数に左シフトを施しても、正の数の場合と同じように値を2倍するだけです。 さらに移動数を大きくすると、やはり符号が変わる場合があります:

// さらに負の int 値 n に対して
assert( (n << 26) == b("1__11___"+ ___) );  // -1744830464
assert( (n << 27) == b("__11____"+ ___) );  //   805306368
assert( (n << 28) == b("_11_____"+ ___) );  //  1610612736
assert( (n << 29) == b("11______"+ ___) );  // -1073741824

移動数を負にした場合、元の int 値に関係なく正の場合と同じになるようです(自分の環境では):

// 通常、コーディング・エラー
assert( (n << -1) == b("________"+ ___) );  // 0
assert( (n << -2) == b("1_______"+ ___) );
assert( (n << -3) == b("11______"+ ___) );

右シフト (>>)

次は右シフト。 右シフトの演算子は「>>」です。 使い方は左シフト演算子の場合と同じです。

正の値
まずは正の int 値 m (= 26) に対して使ってみましょう:

// 正の int 値 m (== 26) に対して
assert( (m >> 0) == b(___+"___11_1_") );  // 26 == m
assert( (m >> 1) == b(___+"____11_1") );  // 13
assert( (m >> 2) == b(___+"_____11_") );  //  6
assert( (m >> 3) == b(___+"______11") );  //  3
assert( (m >> 4) == b(___+"_______1") );  //  1
assert( (m >> 5) == b(___+"________") );  //  0
assert( (m >> 6) == b(___+"________") );  //  0

右端を越えたビットは単に落とされます。 また左端には0を補完します。 まぁ特に問題はありませんね。

数値的には、左シフトとは逆に、1だけ右シフトを行うと数値的には 1/2倍しますが、結果が整数値でない場合はそれを超えない最大の整数(ガウス記号や床関数で得られる)となります。 もしくは

  • 元の int 値が
    • 偶数の場合は2で割る
    • 奇数の場合は1を引いて2で割る

とした方が整数の演算だけしか使わないのでいいでしょうか。  { x } { p } だけ右シフトすると、値は  { [2^{-p} x] } { [\,] } はガウス記号)となります。

負の移動数を施すと(自分の環境では)以下のように常に0となりました:

// 通常、コーディング・エラー
assert( (m >> -1) == b(___+"________") );  //  0
assert( (m >> -2) == b(___+"________") );  //  0
assert( (m >> -3) == b(___+"________") );  //  0

今の場合、移動数を変えていっても結果は変わらないようですね。

負の値
次は負の値に対して右シフトを施してみましょう。

// 負の int 値 n (== -26) に対して
assert( (n >> 0) == b(lll+"111__11_") );  // -26 == n
assert( (n >> 1) == b(lll+"1111__11") );  // -13
assert( (n >> 2) == b(lll+"11111__1") );  //  -7
assert( (n >> 3) == b(lll+"111111__") );  //  -4
assert( (n >> 4) == b(lll+"1111111_") );  //  -2
assert( (n >> 5) == b(lll+"11111111") );  //  -1
assert( (n >> 6) == b(lll+"11111111") );  //  -1

基本的にはビットを右にズラしていくだけですが、左端には1を補完していくのが正の場合と異なります。

数値として見るとやはり1ビットをシフトするごとに 1/2 倍されます。 注意が必要なのは、負の場合でも奇数なら1を引いて1/2倍する(これは同じ)ので、絶対値だけを見ると正の数の場合とことなることです。 上の例では「26 >> 2」は6でしたが「-26 >> 2」は-7となります。 また、元の数が負の場合、移動数を大きくするとビットはすべて1となり、値は-1となります。

負の移動数の場合は(自分の環境では)以下のようになりました:

// 通常、コーディング・エラー
assert( (n >> -1) == b(lll+"11111111") );  //  -1
assert( (n >> -2) == b(lll+"11111111") );  //  -1
assert( (n >> -3) == b(lll+"11111111") );  //  -1

符号なし右シフト (>>>)

最後は符号なしの右シフト。 演算子は「>>>」です。 符号なし右シフトでは、左端に補完するビットとして常に0を使います。 通常の右シフトでは、元の int 値が正なら0、負なら1を補完していたのが違いです。

正の値
符号なし右シフトでは左端に0を補完するので、元の int 値が正なら通常の右シフトと違いはありません:

// 正の int 値 m (== 26) に対して
assert( (m >>> 0) == b(___+"___11_1_") );  // 26 == m
assert( (m >>> 1) == b(___+"____11_1") );  // 13
assert( (m >>> 2) == b(___+"_____11_") );  //  6
assert( (m >>> 3) == b(___+"______11") );  //  3
assert( (m >>> 4) == b(___+"_______1") );  //  1
assert( (m >>> 5) == b(___+"________") );  //  0
assert( (m >>> 6) == b(___+"________") );  //  0

元の int 値が偶数ならなら1/2倍、奇数なら1を引いて1/2倍となること、ある程度以上大きな移動数では値が0となることなども同じです。 負の移動数を与えると(自分の環境では)

// 通常、コーディング・エラー
assert( (m >>> -1) == b(___+"________") );  //  0
assert( (m >>> -2) == b(___+"________") );  //  0
assert( (m >>> -3) == b(___+"________") );  //  0

となって、これも通常の右シフトの場合と同じでした。

負の値
符号なし右シフトが通常の右シフトと結果が異なるのは、負の値に対して演算を行うときです。 右シフトの場合と違って左端には0を補完していきます:

// 負の int 値 n (== -26) に対して
assert( (n >>> 0) == b(""+lll+"111__11_") );  //        -26 == n
assert( (n >>> 1) == b("_"+lll+"111__11") );  // 2147483635
assert( (n >>> 2) == b("__"+lll+"111__1") );  // 1073741817
assert( (n >>> 3) == b("___"+lll+"111__") );  //  536870908
assert( (n >>> 4) == b("____"+lll+"111_") );  //  268435454
assert( (n >>> 5) == b("_____"+lll+"111") );  //  134217727
assert( (n >>> 6) == b("______"+lll+"11") );  //   67108863

1以上移動させた場合は、結果は正の値になります。 2以上移動させた場合は1つ少ない移動数の場合の1/2倍(奇数の場合は1を引いて1/2倍)した値になります。 左端に0を補完するので、この右シフトは正の数に右シフト(符号ありでも符号なしでも同じ)を施した結果と同じです。

これが符号なし右シフトと呼ばれるのは、32ビットで0から  { 2^{32}-1 } までの整数値を表す符号なし int (unsigned int) に対しての右シフト演算になっているためです。 実際、通常の int 値での -26 は符号なし int では  { -26 + 2^{32} = 4294967270 } となりますが、「n >>> 1」(= 2147483635) はこれの1/2倍になっています。

ある程度以上大きな移動数では、正の値の場合と同じく値は0となります(これは通常の右シフトの場合の-1とは異なりますね)。

負の移動数の場合は(自分の環境では)以下のようになりました:

// 通常、コーディング・エラー
assert( (n >>> -1) == b(___+"_______1") );  //  1
assert( (n >>> -2) == b(___+"______11") );  //  3
assert( (n >>> -3) == b(___+"_____111") );  //  7

今回はビットシフトがどのような演算を行うかを見てきました。 まぁ昔々に最初見た頃は「なんじゃこれ」と思って気もしますが、2進法を知ってれば別に大した話でもありませんね。 大抵の場合は必要になってからやってもそんなに問題なく使いこなせるかと思います。 ただ、やはり通常の右シフトと符号なしの右シフトの違いが最初はよく分からないかも知れません。 この記事が理解の一助にならんことを。

【追記】

  • 符号なし右シフトが符号なし int に対しての右シフトであることを追記しました。
  • 最初の方に代入演算子の箇所を追記しました。

Javaによる関数型プログラミング ―Java 8ラムダ式とStream

Javaによる関数型プログラミング ―Java 8ラムダ式とStream

  • 作者: Venkat Subramaniam,株式会社プログラミングシステム社
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2014/10/24
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログ (3件) を見る

*1:言う必要はないかと思いますが、左方向への矢印を表しています。

*2:x = m << 26, y = m << 27 とすると、y = x * 2 - 2^32 となって、int 値の範囲の計算では、これも2倍になっています。 ただし m << 28 から m << 29 へのシフトでは落ちているビットがあるので、2倍にはなっていません。

*3:ちなみに、java.math.BigInteger の左シフトは負の数でもきちんと動くようです。