Java
ビット演算

BigIntegerでバイナリ値のビット演算を行う

ブログからの転載記事です。

Javaにはバイナリ値を扱う便利な機能があまり用意されていないないため、バイナリ値が格納されたbyte配列に対してビット演算を行うには、自力でビット(配列)間の値引き渡し処理を実装する必要があります。

よく使われる方法には、byte配列をint型やlong型などの整数型に一度格納してからビット演算を行い、再度byte配列に戻すというものがありますが、この方法では最大でlong型の8byteまでしか扱えません。

BigIntegerクラスを使うことで任意のサイズのbyte配列を扱えますが、データ変換に少し工夫が必要となりますので、ポイントをまとめてみました。

BigIntegerでbyte配列のビット演算を行う方法

BigIntegerを使ったbyte配列のビット演算は以下の手順でできる。

  1. byte配列を正数としてBigIntegerに読み込む。
    • BigInteger(byte[] val)コンストラクタで読み込んだ後に、符号ビットをマスク処理で0に変える。
  2. BigIntegerインスタンスのメソッドを使って各種演算を行う。
    • インクリメント・ディクリメント:addメソッド、subtractメソッド
    • 論理演算:andメソッド、orメソッドなど
    • シフト演算:shiftRightメソッド、shiftLeftメソッド ※ これらは算術シフトであるが、論理シフトと同じ結果になる。(ポイント1参照)
    • 各演算の後には毎回マスク処理を行い、BigIntegerの値の正数化と不要な上位バイトの各ビットの0への変換を行う。
  3. BigIntegerをbyte配列に再び変換する。
    • toByteArrayメソッドでbyte配列に変換し、バイト数が不足する場合は補完処理、バイト数が多い場合は削減処理を行う。

実装例

ポイント1:BigIntegerを常に正数の状態に保つ

BigIntegerの値が負になると、上手くいかないケースがある。

論理シフトの算術シフトでの代用

BigIntegerには算術シフトしか実装されていない。(そもそもBigIntegerはバイト列を意識することなく数値を扱うためのクラスなので、論理シフトが意味を持たないため。)このため、算術シフトを論理シフトで代用する必要があるが、負数に対する右シフトは算術シフトと論理シフトで結果が異なる。

1010 1010 -- 1bit論理右シフト --> 0101 0101
1010 1010 -- 1bit算術右シフト --> 1101 0101 # 論理シフトと結果が異なる。

そこで、BigIntegerの値が常に正数となるように変換する必要がある。この変換処理は最初のbyte配列読み込みと各演算の後に毎回行う必要がある。

1010 1010
  -- 正数としてBigIntegerに変換 --> 0000 1010 1010
  -- 1bit算術右シフト --> 0000 0101 0101 # 論理シフトと同じ結果になる。

BigIntegerを正数にする方法には、符号ビットを指定してbyte配列を読み込む方法と、マスク処理で符号ビットを1に変更する2通りあるが、後述のポイント2の目的でも利用できるマスク処理をする方法が簡単である。

// 入力バイト配列: c0 00
byte[] input = new Bytes(new byte[] {(byte) 0xc0, (byte) 0x00}).toByteArray();

// 正数(符号ビットを0)として読み込む方法
// 00 c0 00
new BigInteger(1, input).toByteArray();

// 符号ビットをマスク処理で0に変える方法
// ff c0 00 (入力) AND 00 ff ff (マスク) => 00 c0 00
// ※ バイト配列にしたときにサイズの異なるBigIntegerのAND演算では、
//    サイズの小さい方がサイズの大きい方に合うように拡張される。
BigInteger mask = new BigInteger(1, new Bytes(new byte[] {(byte) 0xff, (byte) 0xff}).toByteArray());
new BigInteger(input).and(mask).toByteArray();

ポイント2:余分な上位バイトの各ビットを0に保つ

BigIntegerインスタンスに対してインクリメント・ディクリメントをしたときに元のバイト数で表現できる範囲を超えてしまった場合や、左シフト演算を行った場合に、本来のバイト数よりも上位のバイトにデータが残ってしまうことがある。

この余分な上位バイトのデータは以降の処理でシフト演算をするときに影響を与えてしまうので、各演算の後に各ビットを0にクリアする必要がある。これは、ポイント1で述べたマスク処理で同時に行える。

// 入力バイト配列: c0 00
byte[] input = new Bytes(new byte[] {(byte) 0xc0, (byte) 0x00}).toByteArray();
BigInteger mask = new BigInteger(1, new Bytes(new byte[] {(byte) 0xff, (byte) 0xff}).toByteArray());
// 1bit左シフト、1bit右シフトの順でシフト演算する。
// 本来は最上位1bitが捨てられて 80 00 となるが、元の c0 00 に戻ってしまう。
new BigInteger(input).and(mask).shiftLeft(1).shiftRight(1);

ポイント3:BigIntegerをbyte配列に戻すときにバイト数を調整する

toByteArrayメソッドはBigIntegerに格納されている数字の表現に必要な最小の要素数のbyte配列を返却するため、元のbyte配列よりもサイズの小さなbyte配列となることがある。

// 入力バイト配列: 00 7f
byte[] input = new Bytes(new byte[] {(byte) 0x00, (byte) 0x7f}).toByteArray();
// 出力バイト配列: 7f
// BigIntegerに変換すると1バイトになる。(数字としては127で1バイトで表現できるため。)
byte[] output = new BigInteger(input).toByteArray();

また、各演算により元のbyte配列よりもサイズの大きなbyte配列になることもある。

// 入力バイト配列: 40 00
byte[] input = new Bytes(new byte[] {(byte) 0x40, (byte) 0x00}).toByteArray();
// 1bit左算術シフト後の出力バイト配列: 00 80 00
byte[] output = new BigInteger(input).shiftLeft(2).toByteArray();

このため、byte配列に戻すときには元のバイト数と一致するように調整する必要がある。

// 変換対象のBigIntegerインスタンス
BigInteger bi;
// 変換するバイト配列のサイズ
int byteSize;

byte[] ba = bi.toByteArray();
ByteBuffer bb = ByteBuffer.allocate(byteSize);
// 余分な上位バイトを取り除く。
if (ba.length >= byteSize) {
  bb.put(ba, ba.length-byteSize, byteSize);
// 不足するbyte数分ByteBufferを先頭から埋める。
} else {
  int byteSizeToFill = byteSize - ba.length;
  for(int i=0; i<byteSizeToFill; i++) {
    bb.put((byte) 0);
  }
  bb.put(ba);
}

// 変換後のバイト配列
byte[] output = bb.array();

厳密にはBigIntegerが負数の場合は、不足バイトを0ではなく1で埋める必要があるが、ポイント1の対応でBigIntegerの値は常に正数になるように調整しているため、負数の場合を考慮する必要はない。

// 入力バイト配列: ff ff
byte[] input = new Bytes(new byte[] {(byte) 0xff, (byte) 0xff}).toByteArray();
// 出力バイト配列: ff
// 負数の場合には不足する上位ビットを1で埋める必要がある。
byte[] output = new BigInteger(input).toByteArray();