Search on the blog

2013年10月1日火曜日

Javaのビット演算いろいろ(1)

Integerクラスにはビット演算の良質な使用例がたくさんあります。
そのうちのいくつかを簡単な解説と一緒に載せておきます。

highestOneBit
public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}
最初の5行(コメントは抜かして)で、1になっている桁より右の桁をすべて1にします。
そして最後の行で1だけ右シフトしたものを引くと、hightest one bitがえられます。

lowestOneBit
public static int lowestOneBit(int i) {
    // HD, Section 2-1
    return i & -i;
}
これは有名。プログラミング(競技プログラミング?)をやっている人なら何度も見たことがあると思います。iを「negateする=ビット反転して1を足す」なので、lowestOneBitだけが1になります。

reverse
public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}
ビット反転処理(順序の反転)です。FFTのプログラムを書くときに使うかもしれません。

これはDivide and Conquerです。
最初の3行(コメントは抜かして)は、以下のような1byte内の反転処理をしています。
次の行では、byte単位の反転を行っています。

0 件のコメント:

コメントを投稿