【高速化】ビット演算　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 496 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 21:35:27 ] >>495 アセンブリコードで比較してみると分かるんじゃね？ 497 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 23:12:05 ] 俺には>>486が if(v==2018||v==2019){ }else if(v==4049||v==4050){ }else{ } って条件に読めるんだが 498 名前：デフォルトの名無しさん mailto:sage [2007/10/23(火) 23:17:57 ] 俺も俺も 499 名前：デフォルトの名無しさん mailto:sage [2007/10/24(水) 00:23:34 ] >>486 日本語でおｋ やっと言う側に回れたか 500 名前：デフォルトの名無しさん mailto:sage [2007/10/24(水) 01:05:28 ] >>497 いや、今日きちんとみかか村に出撃して 糞仕様について問い詰めてきたけど case 2018: case 2019: case 4049: case 4050: で正しい どうもみんなありがとう 501 名前：デフォルトの名無しさん mailto:sage [2007/11/02(金) 19:56:43 ] >491 >if (((abs (v - 3034) + 1) & mask) == 1016) return 1; ここら辺の数値の導き方教えてください どいった関係で3034とか出すの？ど素人ですんません 502 名前：デフォルトの名無しさん mailto:sage [2007/11/02(金) 20:15:08 ] >>501 2018+4050=2019+4049=3034+3034 v = [2018 or 2019 or 4049 or 4050] の時 abs(v - 3034) = [1015 or 1016] abs (v - 3034) + 1 = [1016 or 1017] mask=0xfffffffeより奇数はそれを超えない偶数に変換される。 (abs (v - 3034) + 1) & mask = 1016 503 名前：デフォルトの名無しさん mailto:sage [2007/11/02(金) 21:44:43 ] >502 ものっそい感動しました 久しぶりに成長した気がする この括り方すげー 504 名前：デフォルトの名無しさん mailto:sage [2007/11/03(土) 20:48:03 ] もはや逆方向にソースから動作仕様を求めることはほぼ不可能だな 505 名前：デフォルトの名無しさん mailto:sage [2007/11/04(日) 06:35:34 ] かっこいい BIN→BCD は？ 506 名前：デフォルトの名無しさん mailto:sage [2007/11/04(日) 08:47:47 ] 速さなら、00h,01h,02h・・・を表に持ち、binで表引き。 <99のチェックは必要。 サイズなら、((bin/16)<<4) | (bin%16) ・・・バイト版。　<99のチェックは必要。 ワードは、／100の商と余りに分けて、上のを呼び、合成。 自分で書いたのはこんな当たり前の奴だなあ・・・ 507 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 16:03:38 ] しばらく前はメモリアクセスがからむテーブル参照の方が重いって話だったけど、 また状況変った？ 508 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 16:47:46 ] キャッシュの容量 メモリアクセス速度とキャッシュアクセス速度の比率 によって変わるからなあ 細かくいいだすとキャッシュ方式も絡むし 結局「場合による」んじゃねえの 509 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 17:28:19 ] 一般論としては、キャッシュに載っている(=頻繁に呼ばれる)ならテーブルの方が速いんじゃないかね。 ただ、この場合の「一般」というのは、分岐が含まれる(=分岐ミスの可能性がある)という前提。 例えば上の((bin/16)<<4) | (bin%16) の場合だと 依存関係が2箇所あって、その部分は同時実行は出来ないけど キャッシュアクセスに要する数クロック程度の時間と比べてどちらが速いかはわからんね。 テーブルジャンプ(ほぼ同じ値が続く場合以外)は糞だけど。 510 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 17:37:19 ] 掛けたり割ったりすることにものすごい抵抗感がある 511 名前：デフォルトの名無しさん mailto:sage [2007/11/10(土) 18:06:01 ] いや、この場合に限れば、まず間違いなく最適化でシフトやアンドになるよ。 512 名前：506 mailto:sage [2007/11/11(日) 02:32:03 ] 今のチップで乗除算持ってないほうが珍しいよね。俺が書いたのは3MHzの8085だったから、 キャッシュ云々の話はなし。／100だけは除算ルーチン使わないとだめだった。 513 名前：デフォルトの名無しさん mailto:sage [2007/11/11(日) 13:44:02 ] ARMは現役のチップだけど除算命令なかったような 514 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 11:40:49 ] x/100　は　掛け算があるなら 655*( x + x/2048 + x/16384)/ 65536 515 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 14:14:26 ] その掛け算とｼﾌﾄの計算量なら、100=64hだから、分母の<<2と<<5と<<6を引いたほうが・・・ 516 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 15:57:51 ] y = (655*x)>>16 で概算して while ( x-y*100>=100 ) y++; ならせいぜいループ１回だろ 517 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 18:05:59 ] 最低でもx<6557202(≒(1<<32)/655)が言えなければ。 518 名前：デフォルトの名無しさん mailto:sage [2007/11/14(水) 18:34:29 ] >>512 (42949672*x+65536)>>32 519 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 07:36:11 ] シフト演算子がアンカーになってしまう（ｗ >>514-516 は、たぶん数学的には同等なような気がする。 >>518 それ、どういう原理なの？ 32シフトしたら全部なくなっちゃうような気が・・・ 520 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 08:53:19 ] 32bitレジスタ持ってるような16bit以上のCPUを想定してるんだろ x386なら32x32bit掛け算の結果が２つのレジスタに判られるから 32bitシフトは上位のレジスタを採用するだけになる。 521 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 11:57:03 ] &gt;&gt;32 >>32 522 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:18:01 ] >>512 >>‍32 523 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:22:04 ] >>521 >>522 何が言いたいのか意味不明だ。 524 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:29:42 ] >>523 525 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:42:20 ] これでどうだ x >> 32 526 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 12:44:23 ] 俺他人だけど　>>‍523 色が違うだろって言いたいんじゃないのかな？ 527 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 13:11:18 ] >>523 こうすればいいのよ（たぶん） 528 名前：527 mailto:sage [2007/11/15(木) 13:12:44 ] >>‍527 吊ってくるorz 529 名前：518 mailto:sage [2007/11/15(木) 16:36:17 ] >>520 あたり。 あと、>>518のxは0〜65535の範囲である必要がある。 530 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 16:54:12 ] 多少ステップ数がかかるように見えても、まだハードウエア除算は普通の命令２０個分以上に重いからな 1/100 は1/10のルーチンを２度呼んでたな。 1/10は1/2/5 だから１ビットシフトしてから５で割る 65536/5=13107.2 だから13107を係数に使うと誤差は16bitの範囲で１ だけど１ビットシフトしてるから、15bitの範囲になってるから 最大誤差は0.5なんでOK という事で、最大誤差の0.5を足して x = x / 2 x = (13107*x+ 6553) / 2^16 を２度繰り返す 531 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 01:35:07 ] >>518 や、>>530 は余りも一緒に求まるの？ 532 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 08:46:49 ] この話は掛け算が高速ならという話だから 余りは後から　y=x/N を求めた後 x-N*y で求めればいい 余りだけが必要なら355付近から話題が出てる 533 名前：デフォルトの名無しさん [2007/11/16(金) 09:53:08 ] 実測で、ハードウェアまたはCの除算を上回るルーチン作れるの？うｐして 動かしてみる辛さ 534 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 10:26:25 ] どっかのスレでやってたでしょ。 パソコンの除算命令はレイテンシが大きいから連続して実行させるととても重くなる。 ただ整数ユニットでは実行されないから、その間に他の命令を入れられるならＯＫ あ、このスレか、>>367-379 535 名前：デフォルトの名無しさん [2007/11/16(金) 10:59:28 ] int型の除算で標準のものより速いものは作れるのか作れないのか？ 536 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:03:08 ] 分母が固定なら可能。　変数なら無理。　 537 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:04:47 ] まてよ。分子が固定な場合、ニュートン法である程度いけるかな・・・・まあ無理か 538 名前：デフォルトの名無しさん [2007/11/16(金) 11:23:21 ] 分母が固定ならif文などで分岐すれば、総合的には速度が上げられるのか? 作ってくれ 539 名前：デフォルトの名無しさん [2007/11/16(金) 11:26:26 ] 経験上、演算や比較文より代入に時間がかかる気がする たぶんレジスタ動作　+　演算より、メモリ動作は遅いんだろう 540 名前：518 mailto:sage [2007/11/16(金) 11:39:24 ] >>535 ループの中で定数(変数でも変わらなければＯＫ)で除算するのは、 置き換えた方が高速化できるし、それを実際に使っている。 ピクセル操作のような回数の多いループでは劇的な効果がある。 >>539 それは毎回キャッシュから外れた場合の話。 オンキャッシュなら少しでもＣＰＵを止めない方がいい。 541 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:45:08 ] >>538 で、分母はいくらなの？　100の場合はいろいろ出てるよね。 542 名前：デフォルトの名無しさん [2007/11/16(金) 11:46:27 ] 汎用の除算は出来ないか? 例えば2〜500まで定数だけ作って分岐させて使う そのとき高速になるのか? 543 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 11:48:53 ] その分岐の為に時間を使ってしまうから無理だろうね たとえば関数テーブルで分岐したとしても、キャッシュミスを起こすだろう。 544 名前：518 mailto:sage [2007/11/16(金) 11:50:14 ] >>542 できる。 それぐらいなら除数の逆数のテーブルを使って可能。分岐はさせないほうがいい。 ただ、16bit全域とかになると、テーブルの方が不利になるCPUが多い。 545 名前：デフォルトの名無しさん [2007/11/16(金) 11:54:52 ] 逆数で気づいたけど、浮動小数点の掛け算で計算すると鈍いの？ 546 名前：デフォルトの名無しさん [2007/11/16(金) 11:57:24 ] 逆数の2進展開を持っていたらビット演算できそうだけど・・・どうだろ　速いのか？ 547 名前：デフォルトの名無しさん [2007/11/16(金) 12:00:46 ] たびたび連投すまんが、計算でループを使うなら、はじめに分岐させてもコストは同じようなものだな 2〜1024までなら10回の分岐で決定する　10回程度のループを使うなら分岐させた方が良い 548 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 12:01:09 ] >>544 (A*x+B)のＡ，Ｂをテーブルにするの？ でも、たとえば　65535÷３はどうするの？A=21845にしたら、これでは無理だよね 549 名前：デフォルトの名無しさん [2007/11/16(金) 12:10:41 ] x / n = (Ax + B ) >> C ってどうやって求めるの？ 550 名前：518 mailto:sage [2007/11/16(金) 12:12:05 ] >>548 そうそう。Bは固定でいい。 16ビット範囲の X / Dなら、R = 4294967295 / D として、 X / D の値は (R * X + 65536) >> 32となる。 Dが複数あるなら、D→Rのテーブルを作ればＯＫ 551 名前：デフォルトの名無しさん [2007/11/16(金) 12:14:16 ] >>550 BCC5.5だけど、上のやつ計算できなかったよ 552 名前：518 mailto:sage [2007/11/16(金) 12:19:40 ] >>551 __asm{ mov eax, R mul X add eax, 010000h adc edx, 0 mov eax, edx } 553 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 13:04:33 ] >>550 Rが切り捨てなら汎用になるように (R * X + R - 1 ) >> 32 でいいんじゃないの？ 554 名前：518 mailto:sage [2007/11/16(金) 13:09:18 ] >>553 65536より、R - 1のがいい理由は何？ 555 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 13:24:06 ] 理由は、Xが16bitの範囲を超えて入力された時の誤差が多少でも減る事だな 556 名前：518 mailto:sage [2007/11/16(金) 13:36:17 ] >>555 誤差が許される場合はいいかもね。 そうでない場合は、素直に３２ビットに拡張した方が良くないか？ 557 名前：デフォルトの名無しさん mailto:sage [2007/11/16(金) 14:03:01 ] ようするに (A * x + A-1 ) >> B として AのMSBが1になるように B を調整するって事だよね？ Ｂは常に32以上だから、実際には上位ワードだけを>>(B-32) するのだろうけど 558 名前：518 mailto:sage [2007/11/16(金) 17:10:53 ] >>557 いや、そうじゃなくて、余計なA - 1 という演算を使うのではなく、 550の式を32ビットに拡張すればいいってこと。 32ビット範囲の X / Dなら、R = ((1 << 64) - 1) / D として、 X / D の値は (R * X + (1 << 32)) >> 64となる。 559 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 04:25:26 ] >>530 ルネサスのマニュアルによるとシフト演算と割り算に迷ったら割り算の方が大抵速いみたいなことが書いてあったけど 560 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 07:26:50 ] >>558 さすがに64bit掛算はまだ普及してないだろ 561 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 07:28:20 ] >>559 SHが特殊で固定シフト命令が1,2,4,8みたいな飛び飛びのシフトしか１命令で出来なかったりするからじゃないの？ 562 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 12:16:14 ] でも、仕事で使用するとしたら、普通に割り算したほうがソースとして見やすいよね。 2で割るのを1ビットシフトするぐらいはいいけど、あえて複雑な演算にするほど処理能力を求められないでしょ？普通の開発は。 でも、このような議論って技術者としては面白いし、ある意味大切だよね。 563 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 12:40:03 ] >>560 アルゴリズム上の話で、実際に64bit乗算をするわけではないと思う。 元ネタはこれじゃね？ ttp://www.emit.jp/prog/prog_div.html 564 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 13:51:33 ] >>560 コンパイラがやってくれることもしばしば。 まぁ尤も、コンパイラのアセンブリ出力を見たときに「割り算がない」って悩まないためにも 知識はあったほうがいいのだけれどね。 565 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 13:57:31 ] Y = (R * X ) >> 64 って事は 、R = 2^64 / D って事だろ？ Dが16bitの範囲なら Rは　48bitって事になるぞ。　64bitモードに以降しないと効率悪いぞ 566 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 14:00:28 ] もともと D=100の場合 1　: ( x * 4294967200 + 65536) >> 32 2　: ( x * 4294967200 + 4294967199 >> 32 のどっちが 大きな x までまともに計算出来るかって問題でしょ？ 567 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 14:01:49 ] 違うか 1　: ( x * 42949672 + 65536 ) >> 32 2　: ( x * 42949672 + 42949671 ) >> 32 568 名前：デフォルトの名無しさん [2007/11/17(土) 15:24:56 ] BCCで出来ないんだけど・・・CPUのせいかもしれない 内部で32+24ビット程度しか保持していない気がする 569 名前：デフォルトの名無しさん [2007/11/17(土) 15:33:51 ] >>518がちゃんとうごくぱそこんってあるの? テストプログラム作ったけど上位1ビットの値は壊れているようだ #include <iostream> using namespace std; main(){ int n; for(n=50;n<=64;n++) cout<<n<<" "<<(unsigned int)((1<<n)>>(n-1))<<endl; } 570 名前：デフォルトの名無しさん [2007/11/17(土) 15:43:45 ] これっていくつになりますか? 1になるはずですよね? cout << (unsigned int) ( ((1<<64)-2) >> 63 ); 571 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 17:43:47 ] >>570 -1を unsigned にキャストしてるんだからUINT_MAXになると思う。 572 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 18:06:10 ] 符号付整数の右シフトが論理シフトになるか算術シフトになるかは処理系定義 573 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/11/17(土) 19:18:14 ] >>569 unsigned __int64かunsigned long longでおｋ 574 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/11/17(土) 19:20:40 ] >>570 なんで普通のコンピュータで使えるビット数越えたシフト使うんだ。 1 << 64なんてオーバーフローで0になること確定じゃないか。 575 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 20:42:48 ] ~0ULLでおｋ 576 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 23:58:43 ] >>569 >>563のコードと同じだからそっちでやってみればいいんじゃないか。 577 名前：デフォルトの名無しさん [2007/11/18(日) 07:54:51 ] #include <iostream> using namespace std; main(){ unsigned int n; for(n=60;n<64;n++) cout<<n<<" "<<(unsigned int)(((1<<n)-2)>>(n-1))<<endl; cout<<63<<" "<<(unsigned int) ( ((1<<63)-2) >> 62 ); } 63の値が変わるのはなぜ? 578 名前：デフォルトの名無しさん mailto:sage [2007/11/18(日) 08:34:36 ] >>577 サイズを超えるシフトは未定義。 579 名前：デフォルトの名無しさん mailto:sage [2007/11/18(日) 22:48:23 ] ARMは割り算使うと糞遅いから困るな。 580 名前：デフォルトの名無しさん [2007/12/03(月) 22:55:09 ] age 581 名前：デフォルトの名無しさん [2007/12/03(月) 23:13:14 ] 32bitパソコンだと、16*16しか値は保証されないよね a + b * 65536　などと表示して、32bit以上を表現したら ハードウェア搭載の除算よりビット演算のほうが速い? 除算が現れたらintを16bit数に変換して計算する 582 名前：デフォルトの名無しさん [2007/12/04(火) 05:02:29 ] X = 65536 、R = 1/Xとすると (a+bX) / (c+dX) = (b+aR) / (d+cR)であり、 1/(1+R)　のテイラー展開は、　1　-　R + R^2 - ・・・+(-R)^n+ ・・・ Rの巾は非常に小さいため2乗までを採用すると、 (a+bX) / (c+dX)　=　( (b+aR)/d ) * 1/(1 + cR/d) =( (b+aR)/d ) * (1 - cR/d + (cR/d)^2 ) =1/(X^3 * d^3) * (a + bX ) * (c^2 -cdX + d^2X^2 )　となる これで32bit除法を高速化出来るか? 583 名前：582 [2007/12/04(火) 05:12:33 ] 32bit内で処理しようとすると大変だ　普通にCPUに任せた方が楽そう 584 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 20:25:38 ] BOOL bResultの値が 0 か -1 if (bResult == 0 || bResult == -1) じゃなくて、一発で調べる方法はないですか？ 585 名前：デフォルトの名無しさん [2007/12/16(日) 20:42:35 ] BOOLなのに何故数値と比較してるんだ？ 586 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 21:10:40 ] GetMessageじゃね？ 587 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 21:30:22 ] BOOLは偽==0、真==0以外じゃなかったか？ 定義を調べた方が良さそう。 588 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:05:41 ] 世の中には変な使い方する椰子がいるのよ。MSとかw ttp://msdn.microsoft.com/library/ja/default.asp?url=/library/ja/jpwinui/html/_win32_getmessage.asp 589 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:08:46 ] if(bResult^0==-1) 590 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:37:38 ] x^0=x 591 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:42:19 ] if (((((uint32_t)bResult) + 1) >> 1) == 0) 同じ3演算だけど-1をロードしないだけ早いかも？ uint32_tがいいかどうかはよくわからない。 592 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:16:01 ] -1か0、限定なんだからそのまま書いたほうが分かりやすいような。 593 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:26:58 ] >>588 ( ･д⊂ヽ゛ 594 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:29:32 ] >>588 >警告 GetMessage 関数は、0 以外の値、0、-1 のいずれかを返します。したがって、次のようなコードは避けてください。 そもそも… 595 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:30:54 ] まー継ぎ接ぎだからな 596 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:39:34 ] >>591 右シフト・条件分岐より、比較・条件分岐の方が速くない？ if (((uint32_t)bResult + 1) <= 1)

---

---

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

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