上位ビットと下位ビットの入れかえ

　2進32桁(0-31桁)の整数値の0桁目と31桁目、1桁目と30桁目、...、15桁目と16桁目を交換した値を求めたいのですが、うまい方法はありませんか。（ソーティングのためのテストデータの生成に使おうとしています。）

No.1 ベストアンサー 回答者： himajin100000 回答日時： 2009/02/04 18:41

自分で書いてはいませんが，

Doukaku.orgのソースコードは参考になりますか？
(Posted feedbacksから言語を選んでください。)

http://ja.doukaku.org/61/

この回答への補足

参考までに、私の作ったプログラムは以下のとおりです。
unsigned int rbp( unsigned int z ) {
// reverse bit pattern of integer
// Programmed by Akayoroshi on 2009-02-04.
unsigned int m1=1<<16, m2=1<<15;
while( m2 ) {
unsigned int mask=m1|m2;
if ( (z&mask)%3 ) z^=mask;
m1<<=1; m2>>=1;
}
return z;
}
もっとうまい方法はないかと思ってお尋ねしました。

補足日時：2009/02/04 23:29

この回答へのお礼

　ありがとうございました。
　まさに同じことをやっているWebページがあったのですね。
　全部のプログラムを見てはいませんが、いくつか参考になるものがありました。
　ビットごとの処理を繰り返すか、ビットをまとたものを表引きするかのどちらかになるようです。

お礼日時：2009/02/04 23:28

No.6 回答者： Tacosan 回答日時： 2009/02/06 16:29

標準的には #5 のパターンか「表を持っておく」かのどちらかだと思う.

CPU やコンパイラを限定すればもっと早い方法があるかもしれない. bswap ってどのくらいの速度だろ.

この回答へのお礼

回答ありがとうございます。
No.5の回答のプログラム中の5つの代入のうち、最後の2つをbswapに置き換えられないかということですね。
コンパイラの出したアセンブリコードを見ましたが、bswapは使っていませんでした。

お礼日時：2009/02/06 19:35

No.5 回答者： Werner 回答日時： 2009/02/05 20:21

演算回数少なくしたいならよく見るのはこういうやつ。

// 参考ページ（というかそのまんま使ったので引用元か）
// http://graphics.stanford.edu/~seander/bithacks.h …
unsigned int reverse_bits(unsigned int v){
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
v = ( v >> 16 ) | ( v << 16);
return v;
}

No.1のリンク先にも同様の考え方を使っているコードがいくつかありますね。

この回答への補足

1から10,000,000までのすべての整数についてビットパターンを逆転させたときの所要時間を計ってみました。(環境は、Athlon64x2, Windows Vista64, Visual Studio 2008, C++ Release構成, 3回計測の平均値です。)
この回答のプログラムでは、0.0807秒（この回答のプログラム中の5つの代入文は順序を入れ替えても正しく処理できるのように見えますので、文の順序を変えたものも計ってみました。この回答通りの順序が最速でした。）
No.4の回答のプログラムでは、1.2135秒（3項演算子を、お礼の中に示したifに変えると1.0774秒）
No.1に示した私のプログラムでは、3.0733秒でした。みっともないプログラムを掲載してしまいました。

補足日時：2009/02/06 00:09

この回答へのお礼

ありがとうございます。データ数100,000,000位までの処理を予定していました。それほど性能の高くない私のPCでも、1秒かからずに処理できそうです。

お礼日時：2009/02/06 00:19

No.4 回答者： D-Matsu 回答日時： 2009/02/05 14:23

上位下位の入れ替えじゃなくてビットパターンを逆順にするんですよね、これ。

こんな感じでどうでしょう？

unsigned long rbp(unsigned long pattern)
{
int i;
unsigned long ret = 0;
for(i = 0; i < 32; i ++)
{
ret |= (pattern & (1 << i)) ? (1 << (31 - i)) : 0;
}
return ret;
}

……あんまし変わらないか。

この回答へのお礼

ありがとうございます。
ret=0;
for( i=0; i<32; i++ ) {
if ( pattern&(1<<i) ) ret |= 1<<(31-i);
}
と同じですね。たしかに、わかりやすいですね。

お礼日時：2009/02/05 15:32

No.3 回答者： zwi 回答日時： 2009/02/04 21:01

そのまま書くと深く考えないと思うのでヒント形式で。

sに元の値、dに逆の値を設定するとして。
(1)sの最上位ビットをdに加える。
(2)sとdをそれぞれビットシフトする。
(3)繰り返す。
と肝心なことをボカして書いてみました。
とりあえず動かないプログラムでも良いので、プログラムが出来たら補足で書き込んでください。

この回答へのお礼

ありがとうございます。
私の作った、正しく動くものをNo.1の回答の捕捉に載せました。
私のプログラムのほうが、ご回答の方法よりも演算回数は少なくて済むと思います。
予断のない形で、うまい方法を教えていただきたかったので質問にはプログラムを示しませんでした。

お礼日時：2009/02/04 23:44

No.2 回答者： arain 回答日時： 2009/02/04 18:50

>うまい方法はありませんか。

「上位ビットと下位ビットの入れかえを行う」関数を作る。
単純にマスクビットをシフトしながらチェックした結果をビット単位でORするだけなんだし。

で、作ってみて分からない場合にここに質問することだと思うんだけど。

この回答へのお礼

ありがとうございます。
作ってみてわからないのではありません。
私の作ったものをNo.1の回答の捕捉に載せました。
予断のない形で、うまい方法を教えていただきたかったので質問にはプログラムを示しませんでした。

お礼日時：2009/02/04 23:39