ビット単位の演算子 (bitwise operators)とシフト演算子 (shift operators)



主旨

ビット単位の演算子 (bitwise operators)とシフト演算子 (shift operators)を理解する。


対象読者

Java言語を利用している技術者。
C/C++,アセンブラなどメモリ管理等を理解している技術者は対象外です。


経緯

Postgresql7.4.xのJDBCドライバのソースコードを読んでいる時に0xFFを利用した
ビット単位の演算に遭遇した。ビット単位の演算はこれまでJava入門書レベルしか
触れていないので何故にビット単位の演算とシフト演算を行っているかが正直理解できなかった。
最初にした言語がJava言語で、OJT(On the Job Training)として業務プログラムを実装している方は、
「サービス」としての業務アプリケーションを開発しているため今後の開発でも
これから説明する演算は必要ないかもしれません。しかしビット単位の演算とシフト演算は
アルゴリズムと同様に言語依存しないプログラムの根底に当たる部分です。
これを機会に是非自分の技術として取り込んでみてください。


問題

ネットワーク上はbyte単位でデータの扱いをする。
このため、Java言語のint型のデータは、4bytes(32bits)のため
これをbyte型の配列に格納してデータ転送しなければならない。


まずは、基本的な部分としてJava言語のプリミティブ型の値の範囲を確認する。

byte型 (8ビット)  -128〜127
int型  (32ビット)  -2147483648〜2147483647

Javaの実行形式のクラスファイルは、当然ですがJVMで動作します。C/C++やアセンブラと異なり、CPUが
32ビットから64ビットに移り変わってもJVM上は常にint型は32ビットになります。


もう１つ再確認するのは、「Java言語規定・5.6 数値昇格」です。

http://www.y-adagio.com/public/standards/tr_javalang2/conversions.doc.html#170952

この規定の中に、二項数値昇格 (binary numeric promotion) というものがあります。
この二項数値昇格によりJava言語では、byte同士の計算、short同士の計算は存在しません。
この場合、int型に変換されてから計算されます。

byte bValue1 = 50;
byte bValue2 = 100;
bValue1 + bValue2; // int型に変換されてから計算される。

よって、C/C++などのようにbyte同士の演算でのメモリ領域の向上と速度パフォーマンスの向上が
ありません。バイトコード（JVM上のマシン語）にもbyte,shortによる演算は存在しません。


ここから本題です。
ネットワークを流れるデータは基本的に1バイト単位です。そのためJavaのbyte型は
1バイトであるため、そのままデータ転送が可能です。しかしint型の場合はどうでしょう？
例えば、int型の128はそのままの状態ではネットワーク上にデータ転送は不可能です。
int型の数値128はbyte型に変換すると桁あふれが発生します。
なぜなら、byte型は先の説明の通り値をとる範囲は-128〜127までだからです。
では、-128〜127以外のデータはどのように表せばよいのでしょう？
１つの解決方法として、大きなデータをbyte型の配列に変換してデータ転送を行う方法があります。
（どの言語でもこれが一般的でしょう）


int testData = 128;

// int型128をbyte配列で格納する。
byte [] buf = new byte[2];

ここでbyte配列に格納する方法と取得する方法のアルゴリズムをどのように
記述すればよいかが問題である。今回は、シフト演算を利用して格納と取得を
行ってみる。

格納方法

for (int i = 0; i < buf.length; i++) {
    buf[i] = (byte) (testData & 0xff);
    testData >>= 8; // shift 8bit
}

解説

int型の128を2進数であらわすと
0000 0000 0000 0000 0000 0000 1000 0000

int型の0xffを2進数であらわすと
0000 0000 0000 0000 0000 0000 1111 1111

これを演算すると

    0000 0000 0000 0000 0000 0000 1000 0000
  & 0000 0000 0000 0000 0000 0000 1111 1111
-------------------------------------------
    0000 0000 0000 0000 0000 0000 1000 0000

int型の128が現れる

byte型にキャストして格納する。この時byte型として
データをSystem.out.printlnなどで表すと-128に成る。
しかし注意して欲しいのは、この-128はあくまでも
int型データを分割した際の一部であるためbyte型として意味を持たない。


何故0xffで整数ビット単位演算をおこなうか？
上記の2進数で表したとおり0xffはint型で表すと下位8ビットに1が格納される
上位24ビットは、0が格納するため、この演算を行うと必ず
「下位8bitのデータ」のみが演算結果として1を返す場合が出てくるのである。
逆に上位24ビットは0の論理積であるため必ず0を返すのである。

この演算結果をbyte型として格納するという事は下記のint型の32bitから
下位8bitを取り出す事に成る。

int  0000 0000 0000 0000 0000 0000 1000 0000
byte                               1000 0000

次にshift演算を行いデータを移動させる。
0が8ビット分シフトされるので以下のように計算される。
    testData >>= 8; // shift 8bit
前   0000 0000 0000 0000 0000 0000 1000 0000
>>8  0000 0000 0000 0000 0000 0000 0000 0000 1000 0000
後   0000 0000 0000 0000 0000 0000 0000 0000

上記の場合は、8ビット分シフトした事でbyteに格納できるだけのデータが
移動したことになる。今度はこれをもう一度byte配列に格納するように
作業を繰り返す。int型の場合32ビット(4bytes)のため3回のシフトで
int型のデータを取得する事が出来る。


取得方法
今度は、byte型の配列に格納された、int型データをどのように抽出するかである。
結論から言うと以下のようなソースコードになる。

    int result = 0;
    for (int i = 0; i < bArray.length; i++) {
        byte b = bArray[i];
        System.out.println(b);
        int tmp = 0;
        tmp = b & 0xFF; // byte to int
        result = result | (tmp << (8 * i));
        // result |= (tmp << (8 * i));
    }

tmp = b & 0xFF

上記はJava言語規定により演算時にint型として解釈されるため

byte型b                                1000 0000

は、まずint型に変換される。

int型b  0000 0000 0000 0000 0000 0000 1000 0000

このint型bと0xFFを論理積で計算するとint型の128に成る。
int型b  0000 0000 0000 0000 0000 0000 1000 0000
0xFF    0000 0000 0000 0000 0000 0000 111111111 &
-----------------------------------------------
        0000 0000 0000 0000 0000 0000 1000 0000

これをtmp似格納する

tmp = 128

次のビット単位の演算子 (bitwise operators)とシフト演算子 (shift operators)を解析すると

iはfor文内のカウンタなので初期値は0であるので以下の式はint型の0と成る

(8 * i)

次にtmp=128なので(tmp << 0 )を置換すると

(128 << 0)

上記のようになり0ビットのシフト演算をおこなう。（シフト演算を行わないと同意）
最後にresult=0との論理和の演算をおこなうと

result  0000 0000 0000 0000 0000 0000 0000 0000
tmp     0000 0000 0000 0000 0000 0000 1000 0000 |
-----------------------------------------------
result  0000 0000 0000 0000 0000 0000 1000 0000

    result = result | (tmp << (8 * i));

２回目以降はiがカウントされていくためtmpが8ビットごと移動する事になる。つまりバイト単位
移動するので、byte型配列に格納したデータを格納していける。



最後に

今回のソースコード解析により実践的な、ビット単位の演算子 (bitwise operators)とシフト演算子 (shift operators)
が理解できたと思う。より理解を深めるためにサンプルコードをカスタマイズしてみてください。



サンプルソースコード


public class ShiftOperate {
        public static void main(String [] args) {
            ShiftOperate s1 = new ShiftOperate();
            s1.run();
        }
        public void run() {

            // 1         2         3         4
            // 0000 0000 0000 0000 0000 1100 1000 0000
            int testData = 3200;
            System.out.println("testdata:"+ testData);
            byte [] bArray = new byte[4];
            for (int i = 0; i < bArray.length; i++) {
                bArray[i] = (byte) (testData & 0xff);
                testData >>= 8;
            }
            // bArray
            // 4         3         2         1
            // 1000 0000 0000 1100 0000 0000 0000 0000
            int result = 0;
            for (int i = 0; i < bArray.length; i++) {
                byte b = bArray[i];
                System.out.println(b);
                int tmp = 0;
                tmp = b & 0xFF; // byte to int
                result = result | (tmp << (8 * i));
                // result |= (tmp << (8 * i));
            }
            System.out.println(result);
            if (testData == result) {
                System.out.println("cool!!");
            }
        }
}

参考資料


postgresql-7.4.1 JDBCドライバソースコード  org.postgresql.core.PGStream.java
http://www.postgresql.org/

JavaFAQ S007 Q-11
http://www.gimlay.org/~javafaq/S007.html

Java(tm) House Mailing List Homepage 0 〜255 の数値の扱い
http://java-house.jp/ml/archive/j-h-b/026759.html#body

サンプルソースコード