プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

ビット列を逆転する

あ〜、無駄だった。本当に無駄だったよ。
java.lang.Integerにreverse関数あったよ!
でもせっかく考えたので記事にしておく。

public static int reverse(int n){
	n = (n&0xffff0000)>>>16|(n&0xffff)<<16;
	n = (n&0xff00ff00)>>>8|(n&0xff00ff)<<8;
	n = (n&0xf0f0f0f0)>>>4|(n&0xf0f0f0f)<<4;
	n = (n&0xcccccccc)>>>2|(n&0x33333333)<<2;
	return (n&0xAAAAAAAA)>>>1|(n&0x55555555)<<1;
}

ビット列をすぱっと二つに半分に割って、順序を入れ替える、という事をしている。
こんな感じ。


ちなみに、JAVAのapiではもうちょっと最適化してあって、私のソースでいうと最初の2行(ちょうど上の図と同じ処理)をひとまとめにしてメモリーへの書き込みを減らしている。

public static int reverse(int n){
	n = n>>>24|(n&0xff0000)>>8|(n&0xff00)<<8|n<<24;
	n = (n&0xf0f0f0f0)>>>4|(n&0xf0f0f0f)<<4;
	n = (n&0xcccccccc)>>>2|(n&0x33333333)<<2;
	return (n&0xAAAAAAAA)>>>1|(n&0x55555555)<<1;
}

java.lang.Integerのreverse関数

public static int reverse(int i) {
	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;
}