- 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
- 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 ]
- ダンゴさんが連投するとスレが引き締まるな
- 621 名前：デフォルトの名無しさん [2007/12/18(火) 11:30:40 ]
- ダンゴage
- 622 名前：デフォルトの名無しさん mailto:sage [2007/12/18(火) 20:46:31 ]
- test
- 623 名前：デフォルトの名無しさん [2007/12/21(金) 07:08:36 ]
- test
- 624 名前：デフォルトの名無しさん [2007/12/21(金) 07:18:07 ]
- www.nicovideo.jp/watch/sm1779811
- 625 名前：デフォルトの名無しさん [2007/12/30(日) 10:37:00 ]
- 年末あげ
- 626 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 18:36:52 ]
- ttp://itl.jisakuita.net/core2_mossari/1162381694.html
ダンゴさんすげえな
- 627 名前：デフォルトの名無しさん [2008/01/09(水) 19:20:08 ]
- sge
- 628 名前：デフォルトの名無しさん [2008/01/14(月) 22:47:23 ]
- V(･∀･)V
- 629 名前：デフォルトの名無しさん [2008/01/21(月) 23:54:19 ]
- あげ
- 630 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 00:09:06 ]
- 以下の2つの値があったとします。
x1 = 0xFF842144
x2 = 0x5400FF33
ユーザからの入力u1、u2が入力された場合
考えられるケースは以下の4つになると思います。
・u1=x1、u2=x2一致
・u1=x1一致
・u2=x2一致
・どちらとも一致しない
最低3回比較しないとどのケースか判断できないって
思い込んでるのですが
何かいいアイディアくれる人いませんか？
- 631 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 00:46:32 ]
- 愚問だと思いますが。。
しかし、そんあ80年代前半のBASICの論理式みたいなアナクロな発想をするって
今日日奇特な人だね。
- 632 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 00:50:58 ]
- u1がx1と一致するケースに
・u1=x1一致、u2=x2一致
・u1=x1一致、u2=x2不一致
がある
u1がx1と一致しないケースに
・u1=x1不一致、u2=x2一致
・u1=x1不一致、u2=x2不一致
がある
つまり４通り
比較は最大２回
- 633 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 01:21:29 ]
- その比較を10^12回通りくらい計算するつもりなら最適化もあり
- 634 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 01:30:35 ]
- あらかじめ
p = x1 XOR x2
の値を取得しておく
q1 = p XOR u1
q2 = p XOR u2
を得る
- 635 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/01/22(火) 01:30:56 ]
- SSE4のptest使えば一回で済む
- 636 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 01:54:14 ]
- >>634
得た後はどうすればいいのw？
q1とq2をどうやって使うの？
- 637 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 02:56:20 ]
- >>632
＞・u1=x1一致、u2=x2一致
あんた馬鹿?
- 638 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 11:10:15 ]
- >>635
無理だろ，あれは and と andnot だから．pcmpeqd の方が良さげ
- 639 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 11:49:49 ]
- 632ってこういうことだろ？
if( u1 == x1 ) {
if( u2 == x2 ) {
//ryouhou
} else {
//u1 nomi
}
} else {// not
if( u2 == x2 ) {
//u2 nomi
} else {
//ryouhou itti sinai
}
}
どこも間違ってるように思えないんだが。
- 640 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 12:34:57 ]
- しかし、BY（文脈読めない）な奴が多いな。
ここがどういうスレかを考えれば、>>630が何を聞きたいか
多少説明不足でもだいたい分かるだろ普通w
- 641 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 13:13:10 ]
- ほうほう。それでそれで?
- 642 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 18:32:50 ]
- int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
b1 = (u1 == x1)
b2 = (u2 == x2)
return a[(b1 << 1) | b2];
- 643 名前：642 mailto:sage [2008/01/22(火) 18:33:45 ]
- × int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
○ int a[] = {一致しない, 片方一致, 片方一致, 両方一致};
- 644 名前：デフォルトの名無しさん mailto:sage [2008/01/23(水) 10:32:39 ]
- ゼロフラグでレジスタに0,1をセットする命令があるならソレが効率的だね。
それがないと、減算して、さらに１引いてキャリーを出してローテートしなくちゃいけない
アキュムレータが2個しかないCPUなら
AccA := u1-x1-1;
RotWithC(AccB);
AccA := AccA+x1+1-x2-1;
RotWithC(AccB);
AccB := AccB and 3;
結局、そのあたり何が効率的かはアセンブラで見ないといけないけど
アセンブラで出来る高速化は、リニアにしか効かないから、そんなに意味ないんだよね
- 645 名前：デフォルトの名無しさん mailto:sage [2008/01/23(水) 20:55:34 ]
- 全面的に同意．ただ２倍位速くなることもあるから最後の手としては有効．まぁ今は可能 intrinsic 使うけど．
- 646 名前：デフォルトの名無しさん [2008/01/23(水) 21:06:35 ]
- 割り算を掛け算とビットシフトに置き換える計算式求めるプログラムできた
#include <iostream>
using namespace std;
main(){
unsigned int N,n,k;
for(N=2; N<65000 ; N++){
for(n=0; (1<<n)<N ; n++); n+=15;
double X=(pow(2,n)/N);
unsigned int Y=(unsigned int)X;
unsigned int d=0;
if(X-Y<=Y+1-X)d=(unsigned int)(pow(2,n)- (N-1)*Y)-1; else Y++;
printf("x /%5d = ( x * %5d + %5d ) >> %2d",N,Y,d,n);
for(k=1; k<(1<<16) ; k++) if(k/N != ((k*Y+d)>>n))break;
if(k==(1<<16))printf(" OK\n"); else printf(" ERR\n");
}}
- 647 名前：646 [2008/01/24(木) 15:42:18 ]
- 64bit機か、内部で64bitまで計算結果を保持しているなら
32bitの割り算も出来るけど646は16bit同士です
- 648 名前：デフォルトの名無しさん mailto:sage [2008/01/24(木) 15:52:26 ]
- GCC の中見りゃあるんじゃね？
- 649 名前：デフォルトの名無しさん mailto:sage [2008/01/24(木) 17:46:02 ]
- >>648
gcc のカオス・スパゲッティ状態を知らぬようだな。
勧めるならせめて Small-C くらいにしとけ。
このルーチンなら 工学社から出ていた
Small-C ハンドブックにもちゃんと説明されていたんだし。
- 650 名前：デフォルトの名無しさん mailto:sage [2008/02/04(月) 20:42:37 ]
- ハッカーの楽しみ買ってきました〜
これから読みますﾉｼ
- 651 名前：デフォルトの名無しさん mailto:sage [2008/02/05(火) 23:53:51 ]
- Hacker's Delight やっと届いた
- 652 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/02/06(水) 01:12:31 ]
- 俺もアレ訳本出る前ネットショップで買ったわ
- 653 名前：デフォルトの名無しさん [2008/02/22(金) 06:50:56 ]
- a
- 654 名前：デフォルトの名無しさん [2008/02/28(木) 07:49:51 ]
- a
- 655 名前：デフォルトの名無しさん mailto:sage [2008/03/01(土) 13:50:55 ]
- a << 1
- 656 名前：デフォルトの名無しさん [2008/03/05(水) 07:05:43 ]
- a
- 657 名前：デフォルトの名無しさん [2008/03/11(火) 07:43:25 ]
- あげ
- 658 名前：デフォルトの名無しさん [2008/03/24(月) 22:44:22 ]
- あげ
- 659 名前：デフォルトの名無しさん [2008/03/30(日) 21:00:53 ]
- あげ
- 660 名前：デフォルトの名無しさん mailto:sage [2008/03/30(日) 21:42:47 ]
- なにこのスレきもい。
でも懐かしい。
- 661 名前：デフォルトの名無しさん [2008/04/06(日) 18:17:38 ]
- |
|
／￣￣￣￣￣￣
＜⌒／ヽ-、_＿_
／＜_/＿＿＿＿／
- 662 名前：デフォルトの名無しさん mailto:sage [2008/04/06(日) 18:41:01 ]
- ダンゴさんを称えるスレというわけではありませんが、まあ、KY。
- 663 名前：デフォルトの名無しさん mailto:sage [2008/04/06(日) 19:46:30 ]
- GCAの作者のページにビット演算が載ってたけど今いちわからん
- 664 名前：デフォルトの名無しさん mailto:sage [2008/04/07(月) 17:04:46 ]
- ViViの作者のページにもビット演算が載ってたけどだいたい理解した
vivi.dyndns.org/W/254
- 665 名前：デフォルトの名無しさん mailto:sage [2008/04/07(月) 19:44:18 ]
- >配列による状態表現よりも処理が高速になる場合が多い
この表現は凶悪だな。何故なら、高速にならなかった場合にはかなり遅くなる可能性があるからだ。
- 666 名前：デフォルトの名無しさん [2008/04/17(木) 06:42:52 ]
- age
- 667 名前：デフォルトの名無しさん [2008/05/01(木) 06:01:45 ]
- age
- 668 名前：デフォルトの名無しさん mailto:sage [2008/05/01(木) 08:02:29 ]
- 燃料がないな
- 669 名前：デフォルトの名無しさん mailto:sage [2008/05/01(木) 08:50:52 ]
- 16bitカラーで 5：5：5 とか 5：6：5 とか の時代なら色々やったけどな
- 670 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/01(木) 18:55:25 ]
- AltiVecにも16bitカラー用の演算があったな
- 671 名前：デフォルトの名無しさん mailto:sage [2008/05/09(金) 19:08:22 ]
- こちらのスレから誘導されて参りました。よろしくお願いします。
スレ立てるまでもない質問はここで 第91刷
pc11.2ch.net/test/read.cgi/tech/1209716212/171
以下の条件で、32bit値のハミングウェイトが素数か否かを判定する
出来るだけ高速な方法を探しています
・入力はランダム
・（最悪ではなく）平均速度が速いことが望ましい
・0、1は素数ではない（偽になって欲しい）
・ハミングウェイトそのものの値は必要ない
・64bit拡張などは必要ない。32bit決め打ちで良い
・外部メモリはあまり使いたくない
皆様のお知恵を貸していただけませんでしょうか
- 672 名前：デフォルトの名無しさん mailto:sage [2008/05/09(金) 19:25:44 ]
- 一応、今はこんな感じです
ベタな実装で恥ずかしいですが…
int hw_is_prime(unsigned long x)
{
x = ( (x & 0xAAAAAAAA) >> 1 ) + (x & 0x55555555) ;
x = ( (x & 0xCCCCCCCC) >> 2 ) + (x & 0x33333333) ;
x = ( (x & 0xF0F0F0F0) >> 4 ) + (x & 0x0F0F0F0F) ;
x = ( (x & 0xFF00FF00) >> 8 ) + (x & 0x00FF00FF) ;
x = ( (x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF) ;
return (1 << x) & 0xA08A28AC;
}
- 673 名前：デフォルトの名無しさん mailto:sage [2008/05/09(金) 21:56:14 ]
- 1 << 32 の結果って決まってたっけ
- 674 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 10:32:41 ]
- 処理系定義かな。0ビットシフトになる場合と32ビットシフトになる場合が一般的だと思う。
- 675 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 18:51:02 ]
- まぁ 8bit, 16bit, 32bit が int の場合と、
64bit が int の場合では結果は明らかに異なるよな
- 676 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 20:19:59 ]
- 8bitがintになることってありえるっけ
- 677 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 20:51:31 ]
- 規格は一応-32767〜32767だからないんじゃね？
|
 |
