Javaのビット演算いろいろ（１）

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単位の反転を行っています。