【高速化】ビット演算　0x02

1 名前：デフォルトの名無しさん [2006/09/16(土) 09:46:26 ] 前スレ ビット演算 pc8.2ch.net/test/read.cgi/tech/1123918075/ 関連スレ アセンブラ…　(゜□゜) ↑アッー！↓ pc8.2ch.net/test/read.cgi/tech/1148402614/ 関連情報 Hacker's Delight ttp://www.hackersdelight.org/ ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか ttp://www.amazon.co.jp/exec/obidos/ASIN/4434046683 ビットを数える・探すアルゴリズム ttp://www.nminoru.jp/~nminoru/programming/bitcount.html Bitboard ttp://en.wikipedia.org/wiki/Bitboard 367 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 09:51:15 ] インテルのコンパイラで a=a%56 の出力はこんな感じ(aはunsigned int)。 LARGE_INTEGER li; li.QuadPart = UInt32x32To64(a>>3,0x24924925); int d = li.HighPart; a -= ((d<<3)-d)<<3; aがsigned intの場合は、もう少し複雑。 368 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:11:46 ] なるほど、>366の数値が0x92492493だからシフト量が違う同じビットパターンなのか。 369 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:17:29 ] でもまあPCのCPUみたいに掛算が高速だったらって前提だな。 1チップとかだと　掛算はビットサイズに応じたサイクル数かかるし 掛け算持ってないＣＰＵもあるし 370 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:21:39 ] 大丈夫、そういうCPUは割り算も遅い。 371 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:26:29 ] a = ( (a>>18)<<3 ) + a & ((1<<18)-1); a = ( (a>>12)<<3 ) + a & 4095; a = ( (a>>9)<<3 ) + a & 511 a = ( (a>>6) <<3 ) + a & 63; a = ( (a>>6) <<3 ) + a & 63; while(a>=56) a-=56; これならどうだろ？ 372 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:34:31 ] 演算子の数が20を超えてるな。 素直にdiv使った方が速いかもしれない。 373 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:45:50 ] もうちょっとバランスをうまく取れば、1行減らせるかもな 374 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:08:06 ] 結局　3bit　単位だからなあ 最初は a = ( (a>>15)&(-7) ) + a & ((1<<18)-1); か a = ( (a>>12)&(-7)) + a & ((1<<15)-1); のどっちかで、どっちも32->18.4bit 次は a = ( (a>>6)&(-7) ) + a & 511 　でも12.5bit a = ( (a>>9)&(-7) ) + a & 4095; でも12.5bit あとは3ビットづつしか落とせない。　無理 375 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:17:53 ] あ、 a = ( (a>>18)<<3 ) + a & ((1<<18)-1); a = ( (a>>12)<<3 ) + a & 4095; a = ( (a>>6) <<3 ) + a & 63; a = ( (a>>6) <<3 ) + a & 63; while(a>=56) a-=56; とやれば、最後の　while はせいぜい3回のループでいいか 376 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:26:49 ] >>372 div 命令は、持っていてもbit数のサイクルかかるのが殆どだよ。　だから >>366-367 のような最適化がされるんだし 377 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:33:21 ] ただ PC の場合はレイテンシがかかるだけだから、divを使った方が速いかもしれないな。 378 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:37:09 ] >>367 ここまでしても idiv より速いのか・・・。 379 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:48:18 ] Pentium II およびPentium III プロセッサの実行ユニット 整数乗算は　レイテンシ4、スループット1/ サイクル 除算は浮動小数点ユニットで行われ FDIV 命令　レイテンシ: 単精度17 サイクル、倍精度36 サイクル、拡張精度56 サイクル だから、桁違いにレイテンシが大きい。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef