Archive for 9th 6月 2009

シフト演算の右オペランドの制限

2009 年 6 月 9 日, 12:05 PM

シフト演算の右側の値には、int型であれが32ビット以上の値、
long型であれば64ビット以上の値は指定しても無駄になる。
符号ビットを考えれば、int型で表せるのは31ビットまでで、
long型なら63ビットまでである。

当たり前だが、int型で以下のようにシフトしたら0になる。

System.out.println(
	Integer.toBinaryString(2147483647) + "(2147483647) >> 31"
	+ " = "  + Integer.toBinaryString(2147483647 >> 31)
	+ "(" + (2147483647 >> 31) + ")"
);
//結果
1111111111111111111111111111111(2147483647) >> 31 = 0(0)

左シフトした場合は符号を残して左シフトしているが、算術シフトの場合は符号を引き継ぐのではなかったか？

System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) << 31"
		+ " = "  + Integer.toBinaryString(2147483647 << 31)
		+ "(" + (2147483647 << 31) + ")"
);
//結果
1111111111111111111111111111111(2147483647) << 31
          = 10000000000000000000000000000000(-2147483648)

NOTと同じ結果だなぁ。なぜ？

さらにマイナス値を右オペランドに指定した場合だが、まずJava言語規定
のシフト演算子の項によると、

左辺オぺランドの昇格した型が int ならば，右辺オぺランドの下位5ビットだけをシフト幅として使用する。それは，右辺オペランドが，マスク値 0×1f を用いたビット単位のAND演算子 & (15.21.1) に従うかのようとする。したがって実際に使用するシフト幅は， 0 から 31 までの範囲とする。

左辺オぺランドを昇格した型が long ならば，右辺オぺランドの下位6ビットだけをシフト幅として使用する。それは，右辺オペランドが，マスク値 0×3fを用いたビット単位のAND演算子 & (15.21.1) に従うかのようとする。したがって実際に使用するシフト幅は， 0 から 63 までの範囲とする。

と記載がある。intなら2進数で11111(31)、longなら2進数で111111(63)でマスクされる。つまりANDということは
比較元と比較先がどちらも1じゃないと真とならないため、それ以内で1の桁、またそれ以上の値は無効になります。
シフト幅10ビットの場合（9ビット以上は省略）
00001010 ←10進数で10
00011111 ←マスク値(31)
———
00001010 ←10

シフト幅42ビットの場合
00101010 ←10進数で42
00011111 ←マスク値(31)
———
00001010 ←10

マイナス値の場合にも法則はあるようで、
例えば
シフト幅-1ビットの場合は2進数だと32桁全て1なので、下位五桁は31になります。
11111111 11111111 11111111 11111111←10進数で-1
00000000 00000000 00000000 00011111←マスク値(31)
—————————————
00000000 00000000 00000000 00011111←結果(31)
-5の場合
11111111 11111111 11111111 11111011←-5
00000000 00000000 00000000 00011111←マスク値(31)
—————————————
00000000 00000000 00000000 00011011←結果(27)
-10の場合
11111111 11111111 11111111 11110110←-10
00000000 00000000 00000000 00011111←マスク値(31)
—————————————
00000000 00000000 00000000 00010110←結果(22)
-30の場合
11111111 11111111 11111111 11100010←-30
00000000 00000000 00000000 00011111←マスク値(31)
—————————————
00000000 00000000 00000000 00000010←結果(2)
-32の場合
11111111 11111111 11111111 11100000←-32
00000000 00000000 00000000 00011111←マスク値(31)
—————————————
00000000 00000000 00000000 00000000←結果(0)
-35の場合
11111111 11111111 11111111 11011101←35
00000000 00000000 00000000 00011111←マスク値(31)
—————————————
00000000 00000000 00000000 00011101←結果(29)

実際にシフト演算してみると

//左シフト
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) << -1"
		+ " = "  + Integer.toBinaryString(2147483647 << -1)
		+ "(" + (2147483647 << -1) + ")"
);
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) << -5"
		+ " = "  + Integer.toBinaryString(2147483647 << -5)
		+ "(" + (2147483647 << -5) + ")"
);
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) << -10"
		+ " = "  + Integer.toBinaryString(2147483647 << -10)
		+ "(" + (2147483647 << -10) + ")"
);
//右算術シフト
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) >> -1"
		+ " = "  + Integer.toBinaryString(2147483647 >> -1)
		+ "(" + (2147483647 >> -1) + ")"
);
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) >> -5"
		+ " = "  + Integer.toBinaryString(2147483647 >> -5)
		+ "(" + (2147483647 >> -5) + ")"
);
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) >> -10"
		+ " = "  + Integer.toBinaryString(2147483647 >> -10)
		+ "(" + (2147483647 >> -10) + ")"
);
//右論理シフト
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) >>> -1"
		+ " = "  + Integer.toBinaryString(2147483647 >>> -1)
		+ "(" + (2147483647 >>> -1) + ")"
);
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) >>> -5"
		+ " = "  + Integer.toBinaryString(2147483647 >> -5)
		+ "(" + (2147483647 >>> -5) + ")"
);
System.out.println(
		Integer.toBinaryString(2147483647) + "(2147483647) >>> -10"
		+ " = "  + Integer.toBinaryString(2147483647 >>> -10)
		+ "(" + (2147483647 >>> -10) + ")"
);
//結果
1111111111111111111111111111111(2147483647) << -1
       = 10000000000000000000000000000000(-2147483648)
1111111111111111111111111111111(2147483647) << -5
       = 11111000000000000000000000000000(-134217728)
1111111111111111111111111111111(2147483647) <> -1 = 0(0)
1111111111111111111111111111111(2147483647) >> -5 = 1111(15)
1111111111111111111111111111111(2147483647) >> -10 = 111111111(511)
1111111111111111111111111111111(2147483647) >>> -1 = 0(0)
1111111111111111111111111111111(2147483647) >>> -5 = 1111(15)
1111111111111111111111111111111(2147483647) >>> -10 = 111111111(511)

右オペランドがマイナス値の場合にも法則性がありそうだけど正直使わなさそうなのでここまで。


タグ: ,
カテゴリー: 開発  |  コメント