Bitwise operation

.java .groovy

Java と Groovy のビット演算のメモ

基本

assert (3 & 5) ==  1     // AND
assert (3 | 5) ==  7     // OR
assert (3 ^ 5) ==  6     // XOR
assert     ~3  == -4     // NOT
assert (3 << 2) == 12
assert (5 >> 2) == 1      // Arithmetic shift
assert (-4 >>> 28) == 15  // Logical shift
負数でシフト演算

int は 0x1f、long は 0x3f でマスクしてシフトする。*1

// 右 operand をマイナスにすると逆方向にシフトするように見える
assert (1 << -2) == Integer.parseInt("01000000000000000000000000000000",2)
assert (-2 & 0x1F) == 30
assert (1 << -2) == (1 << 30)
 
// 逆方向にシフトしてから反転したように見える
assert (-1 >>> -2) == Integer.parseInt("00000000000000000000000000000011",2)
assert (-1 >>> -2) == (-1 >>> 30)

ビット演算を使う

foozea 氏の 8-Queens Problem を Groovy に翻訳して勉強する。
Bitboard と De Bruijn sequence が使われているらしい。

De Bruijn sequence

以前、話題になって勉強した記憶がある。

assert 6 == Integer.parseInt("110",2)
assert (6 & -7) == 0  // x & NOT x == 0
assert (6 & -6) == 2  // x & -x == most right bit
assert Integer.numberOfTrailingZeros(6) == 1

De Bruijn sequence とは 1 ビットずつシフトさせていくとすべてのビットパターンが存在するマジックナンバーのこと?
ビットパターンとの対応表を使って numberOfTrailingZeros を求めるらしい。
Java は Wrapper クラスに同じ処理をするメソッドがあるが違う実装で 『Hacker's Delight』を参考にしたとコメントに書いてあった*2。

Bitboard を実装する

foozea 氏の実装では attack_table は別途計算されているがクラス内で計算した。

// http://foozea.org/2010/05/20/8-queens/ の board.hs を Groovy に翻訳
class Bitboard {
  // De Bruijn sequence
  static final long magic = 0x022FDD63CC95386D

  // 列フィルタ
  static final long[] file_mask = [
    0x0101010101010101,
    0x0202020202020202,
    0x0404040404040404,
    0x0808080808080808,
    0x1010101010101010,
    0x2020202020202020,
    0x4040404040404040,
    0x8080808080808080,  // BigInteger
  ]

  // Caught: java.lang.ClassFormatError: Illegal class name "Bitboard$[JHolder_attack_table"
  static final long[] attack_table

  // 0 〜 63 に変換する
  static int hash(long bits) {
    (bits * magic) >>> 58
  }

  static String toString(long bb) {
    def lines = []
    for (i in 0..<8) {
      lines << Long.toBinaryString(bb >>> i*8 & 0xff).padLeft(8, '0').reverse()
    }
    lines.join('\n')
  }

  static long MASK_UPPER = 0x00FFFFFFFFFFFFFF
  static long MASK_LOWER = 0xFFFFFFFFFFFFFF00
  static long MASK_LEFT  = 0x7F7F7F7F7F7F7F7F
  static long MASK_RIGHT = 0xFEFEFEFEFEFEFEFE

  static enum Operator {
    UPPER(-8, Bitboard.MASK_UPPER),
    LOWER( 8, Bitboard.MASK_LOWER),
    LEFT (-1, Bitboard.MASK_LEFT),
    RIGHT( 1, Bitboard.MASK_RIGHT),
    UPPER_LEFT (-9, Bitboard.MASK_UPPER & Bitboard.MASK_LEFT),
    UPPER_RIGHT(-7, Bitboard.MASK_UPPER & Bitboard.MASK_RIGHT),
    LOWER_LEFT ( 7, Bitboard.MASK_LOWER & Bitboard.MASK_LEFT),
    LOWER_RIGHT( 9, Bitboard.MASK_LOWER & Bitboard.MASK_RIGHT);

    int  distance
    long mask

    private Operator(int distance, long mask) {
      this.distance = distance
      this.mask = mask
    }

    long shift(long bb) {
      Long.rotateLeft(bb, distance) & mask
    }
  }

  static {
    long[] table = new long[64]
    for (i in 0..63) {
      long bb = 1L << i
      long attack = 0L
      for (op in Operator.values()) {
        long mask = op.shift(bb)
        while (mask != 0) {
          attack |= mask
          mask = op.shift(mask)
        }
      }
      table[hash(bb)] = attack
    }
    attack_table = table
  }
}

Groovy で実装したが実際に使用する際は Java で実装した方が速い。
def と int は最適化されなくても 1.5 〜 2 倍ぐらい違ったが long はどうだろう。
long で定義したのは速度よりも def より安心してビット演算できるから。
attack_table を @Lazy long[] にしたら型名がクラス名として使われるらしくエラーになるので初期化は static イニシャライザにした。
Operator は昔のソースから参照したが書いたとき何を参考にしたのか思い出せない。

Groovy の 16進数リテラル
// assert 0xFFFFFFFFFFFFFFFFL == -1L  compile error BUG!
assert 0x7FFFFFFFFFFFFFFFL == Long.MAX_VALUE
assert 0x8FFFFFFFFFFFFFFF in BigInteger
assert 0xFFFFFFFFFFFFFFFF as long == -1L

// 負数はマイナス記号でしか parse できない
new GroovyTestCase().shouldFail(NumberFormatException) {
  assert Long.parseLong("FF" * 8, 16) == -1
}
assert Long.parseLong( "7FFFFFFFFFFFFFFF", 16) == Long.MAX_VALUE
assert Long.parseLong("-7FFFFFFFFFFFFFFF", 16) == Long.MIN_VALUE + 1

コンパイル時に Wrapper クラスの parse メソッドで変換しているらしく負数の16進数リテラルを指定するとエラーになる。リテラルでは型を指定しないで数値にしてから long にキャストした。

8 queens
// http://foozea.org/2010/05/20/8-queens/ の 8queen.hs を Groovy に翻訳
import static Bitboard.*

// bit 単位に分割してリストにする
List candidate_moves(long bb) {
  if (bb == 0) return []
  long sq = bb & -bb // most right bit
  [sq, *candidate_moves(bb & (bb^sq))]
}

// @n   n 列目
// @bb  Queen を置ける場所 (1のところ)
// @xs  Queen を置いた場所 (列ごと)
List<long[]> search(int n, long bb, long[] xs) {
  if (n  == 0) return [xs]
  if (bb == 0) return []
  // n 列目で Queen を置ける場所を探す
  def cm = candidate_moves(bb & file_mask[n-1])
  cm.collect { x ->
    // Queen を置ける場所を更新して次の列を調べる
    search(n-1, bb & ~(attack_table[hash(x)]) as long, [x, *xs] as long[])
  }.inject([]) { acc, v ->
    acc += v
  }
}

def solve() {
  search(8, -1L, [] as long[]).collect {
    it.inject(0L) { acc, v ->
      acc |= v
    }
  }
}

def solutions = solve()
assert solutions.size() == 92
// println solutions.collect { toString(it) }.join("\n\n")

ビットを分割する操作は再利用できそうなので BitBoard 側でもいいかも。
candidate_moves は自分で思いつけそうにない。

2011-06-02 追記

kenken 氏のエントリによると部分集合も取得できるそうだ。

デクリメントへの代入演算子は Groovy では使えなかった。

///// 部分集合を列挙する /////
// http://techtipshoge.blogspot.com/2011/05/blog-post_28.html
def subsets(int x) {
  def rs = []
  for (int y = x; y > 0; y = --y & x) rs << y
  rs
}
assert subsets(Integer.parseInt("11001010",2)).collect {
  Integer.toBinaryString(it).padLeft(8, '0')
} == [
  "11001010",
  "11001000",
  "11000010",
  "11000000",
  "10001010",
  "10001000",
  "10000010",
  "10000000",
  "01001010",
  "01001000",
  "01000010",
  "01000000",
  "00001010",
  "00001000",
  "00000010",
]


ついでに bit を列挙するものも同じ形式で

///// ビットを列挙する /////
// http://foozea.org/2010/05/20/8-queens/
def bits(int x) {
  def rs = []
  while (x != 0) {
    int y = x & -x
    rs << y
    // x = x & (x ^ y)
    x ^= y
  }
  rs
}
assert bits(Integer.parseInt("11101101",2)).collect {
  Integer.toBinaryString(it).padLeft(8, '0')
} == [
  "00000001",
  "00000100",
  "00001000",
  "00100000",
  "01000000",
  "10000000",
]

x の mask を取ってみたがよいのだろうか？


2011-06-04 追記

Bitboard の操作などがまとまっていた。
ぱっと見ただけだけど Operator の方法も載っている。

*1:C はできなかった気がする

*2:Google ブックスでは読めなかった