---------------------- <表1> ビット演算の真理値表とJavaの演算子 Javaの演算子 x1 x2|0 ~(x1|x2) - ~x1 - ~x2 x1^x2 ~(x1&x2) x1&x2 ~(x1^x2) x2 - x1 - x1|x2 ~0 0 0 |0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 |0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 |0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 |0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Javaの演算子が - の列は、x1とx2の演算結果として得ることができない値。 # 表への注文: x1とx2が入力相当で、右側が出力相当なので、縦線で区切ってください。 ---------------------- ---------------------- <リスト1> 素直なアラインメント処理 // コード1; n以上で、Nの倍数の最小値を求めるコード int mod = n % N; if (mod == 0) { return n; } else { return n + N - mod; } // コード2; nより大きい、Nの倍数の最小値を求めるコード return n + N - (n % N); ---------------------- ---------------------- <リスト2> ビット演算を使ったアラインメント処理 // n以上で、Nの倍数の最小値を求めるコード(Nは2の倍数) (n + (N - 1)) & ~(N - 1) // nより大きい、Nの倍数の最小値を求めるコード(Nは2の倍数) n + N - (n & (N - 1)) ---------------------- ---------------------- <リスト3> ビット演算を使うコードの速度比較 final int N = 8; final int LOOP_NUM = 1024 * 1024 * 32; int sum = 0; // to avoid that the compiler optimization would reduce the code long start_tm = System.currentTimeMillis(); for (int i = 0; i < LOOP_NUM; i++) { sum += (i + N - (i % N)); } System.out.println((System.currentTimeMillis() - start_tm) + " " + sum); sum = 0; start_tm = System.currentTimeMillis(); for (int i = 0; i < LOOP_NUM; i++) { sum += (i + N - (i & (N - 1))); } System.out.println((System.currentTimeMillis() - start_tm) + " " + sum); ---------------------- ---------------------- # [Q] これは常識すぎて不要? <表2> 4bitの対応表 2進数 8進数 10進数 16進数 0000 ... 1111 ---------------------- ---------------------- <図1> perlで数値の基数の変換 $ perl -e 'printf("%x",10)' # 10進数から16進数 $ perl -e 'printf("%d",0xa)' # 16進数から10進数 $ perl -e 'printf("%d",012)' # 8進数から10進数 $ perl -e 'printf("%o",10)' # 10進数から8進数 $ perl -e 'printf("%d",0b1010)' # 2進数から10進数 $ perl -e 'printf("%b",10)' # 10進数から2進数 ---------------------- ---------------------- <図2> シェルで数値の基数の変換 function 2to8 () { dc -e "8o 2i $1 p"; } function 2to10 () { dc -e "2i $1 p"; } function 2to16 () { dc -e "16o 2i $1 p"; } function 8to2 () { dc -e "2o 8i $1 p"; } function 8to10 () { dc -e "8i $1 p"; } function 8to16 () { dc -e "16o 8i $1 p"; } function 10to2 () { dc -e "2o $1 p"; } function 10to8 () { dc -e "8o $1 p"; } function 10to16 () { dc -e "16o $1 p"; } function 16to2 () { x=`echo $1|tr '[a-z]' '[A-Z]'`; dc -e "2o 16i $x p"; } function 16to8 () { x=`echo $1|tr '[a-z]' '[A-Z]'`; dc -e "8o 16i $x p"; } function 16to10 () { x=`echo $1|tr '[a-z]' '[A-Z]'`; dc -e "16i $x p"; } 使い方 $ 16to10 a # 16進数から10進数 10 ---------------------- ---------------------- <図3> 4ビットの符号無し整数 - 円上に時計周りに 0000,0001,0010,...,1111 を配置 - 対応する数値が、0,1,2,...,7,8,...,15 - 時計まわりに1ずつ増加する旨を併記 ---------------------- ---------------------- <図4> 4ビットの符号付き整数 - 円上に時計周りに 0000,0001,0010,...,1111 を配置 - 対応する数値が、0,1,2,...,7,-8,-7,...,-1 - 時計まわりに1ずつ増加する旨を併記 ---------------------- ---------------------- <図5> 2の補数と1の補数の求め方 2の補数 00100111 => 全ビットを反転 => 11011000 => 1を足す => 11011001 1の補数 00100111 => 全ビットを反転 => 11011000 ---------------------- ---------------------- <リスト4> java.math.BigIntegerからコードを整形して抜粋 /** * This mask is used to obtain the value of an int as if it were unsigned. */ private final static long LONG_MASK = 0xffffffffL; //...[1] private static int[] add(int[] x, int[] y) { int xIndex = x.length; int yIndex = y.length; int result[] = new int[xIndex]; long sum = 0; // Add common parts of both numbers while(yIndex > 0) { sum = (x[--xIndex] & LONG_MASK) + //...[2] (y[--yIndex] & LONG_MASK) + //...[3] (sum >>> 32); //...[4] result[xIndex] = (int)sum; //...[5] } boolean carry = (sum >>> 32 != 0); // Grow result if necessary if (carry) { int newLen = result.length + 1; int temp[] = new int[newLen]; for (int i = 1; i 大きな数の加算の例 - 32bitずつの加算はCPU命令で行う - 桁あがり(キャリー)も含めて、32bitの単位で順々に加算をするループ処理をソフトウェアで行う様子 +-------+ +-------+ +-------+ x | 32bit | | 32bit | | 32bit | +-------+ +-------+ +-------+ [3] [2] [1] +-------+ +-------+ +-------+ y | 32bit | | 32bit | | 32bit | +-------+ +-------+ +-------+ / ^ / ^ / \-+ \-carry-+ \-carry-+ 1. [1]の加算(CPU命令) 2. 繰り上がりがあれば、[2]の計算結果に加算 3. 繰り上がりがあれば、[3]の計算結果に加算 4. [3]の繰り上がりがあれば、結果を1バイト伸ばす ---------------------- ---------------------- <図7> 浮動小数点の基本(10進数) 1024 => 1.024 * 10^3 1.024: 仮数 10 : 基数 3 : 指数 0.1024 => 1.024 * 10^(-1) 1.024: 仮数 10 : 基数 -1 : 指数 ---------------------- ---------------------- <図8> 浮動小数点の基本(2進数) 1.024 10進数では (1 x 1) + (0 x 1/10) + (2 x 1/100) + (4 x 1/1000) n x 1/(10^m) の積和。nの値の範囲は0から9 2進数では (b x 1) + (b x 1/2) + (b x 1/4) + (b x 1/8) + (b x 1/16) + ... bの値の範囲は 0 もしくは 1 1.024の2進表現を計算してみると、 1. (b x 1)のbは1 => 残りは 0.024 2. (b x 1/2)のbは0 => 残りは 0.024 3. ...しばらくbは0 4. (b x 1/64)のbは1 => 残りは 0.008375 (= 0.024 - (1/64)) 5. (b x 1/128)のbは1 => 残りは 0.0005625 (= 0.008375 - (1/128)) 6. ...しばらくbは0 7. (b x 1/2048)のbは1 => 残りは 0.00007421875 (= 0.0005625 - (1/2048)) ... ---------------------- ---------------------- <図9> IEEE754 http://www.ibm.com/developerworks/jp/java/library/j-jtp0114/ の図 符号: 1bit (0:正、1:負) 指数: 8bit (指数部に127を足した値) 仮数: 23bit (正規化した先頭の1は省略) ---------------------- ---------------------- <リスト5> floatの内部表現の確認 System.out.println(Integer.toBinaryString(Float.floatToRawIntBits(0.5f))); 出力をIEEE754の形式に分割すると 0 01111101 00000000000000000000000 動作解説 2進表現 2^0 x 0 + 2^-1 x 1 => 0.1 x 2^0 正規化(仮数の1桁目を1以上2未満) => 1.0 x 2^-1 仮数の1桁目はコード化しない(ムダなので) => 0 指数は127足す => -1 + 127 => 126 => 01111101(2進数) System.out.println(Integer.toBinaryString(Float.floatToRawIntBits(0.25f))); 出力をIEEE754の形式に分割すると 0 01111110 00000000000000000000000 動作解説 2進表現 2^0 x 0 + 2^-1 x 0 + 2^-2 x 1 => 0.01 x 2^0 正規化 => 1.0 x 2^-2 仮数の1桁目はコード化しない => 0 指数は127足す => -2 + 127 => 125 => 01111110 System.out.println(Integer.toBinaryString(Float.floatToRawIntBits(16f))); 出力をIEEE754の形式に分割すると 0 10000011 00000000000000000000000 動作解説 2進表現 2^4 x 1 + 2^3 x 0 + 2^2 x 0 + 2^1 x 0 + 2^0 x 0 => 10000 x 2^0 正規化(仮数の1桁目を1以上2未満) => 1.0000 x 2^4 仮数の1桁目はコード化しない => 0 指数は127足す => 4 + 127 => 131 => 10000011 System.out.println(Integer.toBinaryString(Float.floatToRawIntBits(1.024f))); 出力をIEEE754の形式に分割すると 0 01111111 00000110001001001101111 仮数部が、図の (b x 1/2)以降の b と対応していることを確認してください。 ---------------------- ---------------------- <図10> BigDecimalの内部表現 new BigDecimal("1.024"); => 1024のint 小数点以下3桁 new BigDecimal("10.24"); => 1024のint 小数点以下2桁 new BigDecimal("102.4"); => 1024のint 小数点以下1桁 new BigDecimal("102.40"); => 10240のint 小数点以下2桁 注意: intのサイズを越える場合、内部ではBigIntegerを使います ---------------------- ---------------------- <リスト6> BigDecimalの使用例 BigDecimal bd = new BigDecimal("1.024"); BigDecimal bd2 = new BigDecimal("10.24"); BigDecimal result = bd.add(bd2); System.out.println(result); // BigDecimalにはtoString()が実装されています ---------------------- ---------------------- <リスト7> BigDecimalの除算 new BigDecimal("1").divide(new BigDecimal("3"), BigDecimal.ROUND_HALF_UP); => 0 new BigDecimal("1.000").divide(new BigDecimal("3"), BigDecimal.ROUND_HALF_UP); => 0.333 ----------------------