- 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
- 520 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 08:53:19 ]
- 32bitレジスタ持ってるような16bit以上のCPUを想定してるんだろ
x386なら32x32bit掛け算の結果が２つのレジスタに判られるから 32bitシフトは上位のレジスタを採用するだけになる。
- 521 名前：デフォルトの名無しさん mailto:sage [2007/11/15(木) 11:57:03 ]
- >>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)
- 597 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:50:04 ]
- >>596
マシン語レベルでは結局0比較に変換されるから同じ程度じゃないかな。
でもCレベルではそっちの方が短くていいと思う。
- 598 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 01:17:11 ]
- >>597
ちょっと前まで主流だった某CPUではシフトは加減算の
8倍遅かったし、それ以外のCPUでも演算器の関係で
シフトの方が並列化されにくいかも、とかそういう話。
- 599 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 01:19:21 ]
- で、何億回呼ぶのよ
- 600 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 02:05:25 ]
- シフトのほうが速いと思ってたのに・・・
- 601 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 03:12:30 ]
- >>599
そんなこと言うならこのスレの意義って一体なんなのさ。
確かにWindows APIをそんなアホみたいに呼ぶ事はないだろうが、
こんな風に一般化してみれば、それなりに使い道はあるだろ。
_Bool bounds_check(int n, int lower, int upper)
{
return (unsigned)(n - lower) < (unsigned)(upper - lower);
}
>>600
加減算よりシフトの方が速いCPUなんてあるのかな？
演算の頻度からいっても普通は加減算を最速に設計すると思うけど。
x86系を数種類しか触った事ないから、他にはあるのかも知れないが。
- 602 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 04:47:19 ]
- ハードウェアの構造上加減算よりシフトの方が圧倒的に単純なんだよ
小さい加算器を作ったことがあればわかるはず
クロック数が一緒ってことはあるかもしれんが、
シフトの方が遅いってことはまずないだろう
- 603 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/17(月) 05:39:05 ]
- ARMだと全命令にプレディケーション使えるからCレベルの単純な分岐は直列化できるよ
分岐は極端に遅いなんていうのはCellプログラマだけにしてください。
- 604 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 07:41:05 ]
- >>602
このケースは1bitだからその通りだけど
x86の8086-286までは、2bit以上のシフトは遅かったんだよ。
最初は直接bit数指定のインストラクションすらなかったし。
- 605 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 13:11:19 ]
- ttp://answers.google.com/answers/threadview?id=388350
- 606 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 13:13:10 ]
- >>603
単純な分岐なら、if文使ってコンパイラに任せた方が速いね。
絶対値求める時とか、NULLならreturnするとか、分岐コストかからなくていい。
- 607 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 14:37:02 ]
- むしろif文にbool型しかとらないJava/C#が異端なんじゃねーの？
俺もbool型オンリーの方が好きだが、スクリプト言語してるとそうじゃない方が多い気がする。
- 608 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 18:27:51 ]
- ifの選択肢にTrueとFalse以外なんてあり得るの？
- 609 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 18:33:36 ]
- if(666){//実行されます。}
- 610 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 19:02:56 ]
- コメントに括弧閉じ書いて意味あんの
- 611 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 21:34:17 ]
- if (GetMessage(...) <= 0)
で充分でね?
- 612 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 21:49:47 ]
- >>602
シフタってのはデータセレクタの塊だから多ビットのシフトは
シリコンの面積を喰うのよ
- 613 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 23:54:21 ]
- >>611
-1以外の負の値が未定義
- 614 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 23:54:34 ]
- シフタのないプロセッサには出会ったことが無いけどね。
- 615 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 23:58:16 ]
- if (bResult == 0 || bResult == -1)
は
if (((uint32_t)bResult + 1) <= 1)
と同じコードになったぞ。
gcc賢いな。
ちなにみRISCでどうなるか見たかったので団子の嫌いなCELLのgccでコンパイルしたw
ちなみにCELL(SPE)もヒントブランチあるから。
むしろARMのプリディケーションいまいちだと思うけど。
- 616 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/18(火) 00:11:17 ]
- 知ってるが
Cellのスカラ性能が
気に食わない
- 617 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/18(火) 00:45:11 ]
- 分岐ヒントもBranchの15クロックくらい前くらいに入れないと駄目じゃなかったっけ
しかも二重に使うとハングする致命的なバグ持ちだから始末に困る
- 618 名前：デフォルトの名無しさん [2007/12/18(火) 00:47:47 ]
- if (bResult == 0 || bResult == -1) こんなん対して食わないだろ゜
- 619 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/18(火) 00:52:15 ]
- SSE4.1のXMMに対する比較命令が加わったから4条件同時判定とかも便利そうだね
- 620 名前：デフォルトの名無しさん mailto:sage [2007/12/18(火) 08:10:08 ]
- ダンゴさんが連投するとスレが引き締まるな
|
 |
