【高速化】ビット演算　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 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 ] ダンゴさんが連投するとスレが引き締まるな 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だからないんじゃね？ 678 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/12(月) 21:34:45 ] 1ビットマシンとか4ビットマシンとかってCでプログラミング可能なの？ 679 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 21:44:21 ] CHAR_BIT >= 8 だけど、 別に変数１つをレジスタ１つで扱えないといけないわけじゃないし 問題ないんじゃね？ 680 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 21:47:55 ] ダンゴさんのカキコでスレが加熱したな 681 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/12(月) 21:59:19 ] レス番飛んでるな 682 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 11:50:54 ] ダとかンとかゴとか入ると飛ぶんだよな。 683 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 11:56:23 ] 実は見えてる 684 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 12:39:16 ] ダンゴって名前を嫌がるのは、 体型が肉団子だからだよな。 685 名前：ヽ・´∀｀・,,）っ-○◎● mailto:sage [2008/05/13(火) 12:47:46 ] だんごはこれだろ ━━━━━━┓がどうみたらだんごに見えるねん あたまわるいんとちゃうか 686 名前：ヽ・´∀｀・,,）っ鹵〜＜巛巛巛 mailto:sage [2008/05/13(火) 12:50:40 ] 虫除けのようなものだよ 687 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 14:33:31 ] ダンゴさんってどんな仕事してるの? 688 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 16:51:03 ] 名無しさんの書き込みでスレがヒートアップしたな。 689 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 18:15:31 ] 他愛もない雑談だけどな。 と、だけ書くのもなんだから、ちょこっとマジレス。 ANSI C での int の定義は処理系依存で、CPUのレジスタ幅によるらしい。 なので、Z80 なら 8bit の筈だけど、 大体のZ80 C処理系では char=8bit, int=16bit と扱う。 なんで int は 16bit より大きいという誤解があるんだろうなぁ。 その昔は char=7bit なんで処理系もあったというので、 油断は出来ないように思うんだよ。 690 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 18:38:03 ] INT_MINは-32767以下、INT_MAXは+32767以上じゃないといけないと決まってる 昔の話は知らん 691 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/13(火) 19:01:17 ] 1ビットCPUは実際にあった www.d1.dion.ne.jp/~ytera/1bitcpu.htm 692 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 21:12:11 ] 昔はやりたい放題だったかも知れないが、 今は規格に準拠した処理系であれば int >= 16 bits なのは真理。 あと、int のサイズの定義は CPU のレジスタ幅にして欲しそうな定義ではあるけど、 そう断言している訳じゃない。 実際最近でも 64-bit マシンで int = 32-bit のことがある。 693 名前： ◆0uxK91AxII mailto:sage [2008/05/14(水) 01:14:15 ] >>689 ＞その昔は char=7bit なんで処理系もあったというので、 無い。 694 名前： ◆0uxK91AxII mailto:sage [2008/05/14(水) 01:21:20 ] ごめん、間違い。 695 名前：デフォルトの名無しさん mailto:sage [2008/05/14(水) 03:04:09 ] uartと間違えたんだな 696 名前：デフォルトの名無しさん mailto:sage [2008/05/14(水) 23:42:41 ] ハネウェルの昔のマシンとかは 6bit 単位のマシンとかがあったから、 それとの勘違いだろ。(7bit があったかどうかは知らん。) まあ単位が 6bit なのは uart と同じ理由だが。 697 名前：デフォルトの名無しさん mailto:sage [2008/05/15(木) 02:07:52 ] >>691 それはCPUと言うよりリレーの置き換えみたいなもの Connection Machineのはまともな1bit CPUだけどbit sliceだから何bitにでも 化ける 698 名前：デフォルトの名無しさん [2008/05/28(水) 00:29:01 ] あげ 699 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:17:23 ] 11100111 こんなビットがあったとき、0が4と5ビット目に 存在するってどうやって調べるのが効率いいのかな？ 個数はわかるけど位置はどうすりゃいいんだろう 700 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:34:24 ] Hacker's Delight 嫁 701 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 02:40:11 ] >>699 11100111 and 00011000 702 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 02:41:22 ] 8bitなら256個のﾃｰﾌﾞﾙ持てば最速じゃね？　16bit以上なら、シフトして端のbitの0/1と シフト回数で判別。 703 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 02:50:48 ] >>699 ループ 704 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 09:37:40 ] >>703 >>701 aビット目とbビット目が動的に変わるなら、マスク作ってandとった方が良いかもしれない。 705 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 09:47:01 ] >>699 問題文は正確に 706 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 11:48:47 ] >>699 ４、５ビット目というのは変わりうるのよね？ あと個数が２個というのも変わりうるのよね？ 707 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 11:51:01 ] >>699 ああ、あと、いつもがそんな風に左右対称とは限らないのよね？ 708 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 12:36:25 ] 一番下の0のビットだけを１にするのなら y := ( not x ) and ( x +1) で出来るから、ビットが1の個数が判る命令BitCount があるんなら BitCount( y-1 ) で求まるよ で x:= x or y; として一番下の0だったビットを1にしてから $FF になるまで繰り返せばいい 709 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:25:23 ] >>708 それって並列にできないですかね 無理ですよね..... 710 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:30:28 ] bit演算で128、64、32bitを扱う場合 みんなどんなふうに宣言しますか？ C/C++でのバターな方法が解りません 711 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:34:46 ] まずトラを数匹用意します。 712 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:41:57 ] あるプログラムで実際にあったコード。 普通ループではカウンタを＋＋していくと思うけど、 （iを1,2,3・・・と加算） 一回処理するごとに左に1ビットシフトしていた。 （iを1,2,4,8・・・とシフト） 普通こういうコード書きます？仕事で。 713 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:49:43 ] >>712 1989年ぐらいに見た記憶があるｗ 714 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:15:51 ] グレイコードを扱うような貧弱なCPUに対するコードなら在り得る。 715 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:26:18 ] １ビットずつスキャンしていく場合には使う。 716 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:27:14 ] >>712 普通にあるし、速度面だけでなく、その方が可読性があるものもある。 717 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:28:54 ] 終了条件でいつも悩むんだけどね。 718 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 07:07:30 ] for( bit=1 ; bit ; bit<<=1 ) cnt += ( ( data & bit) >0 ); こういうの？ 719 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 22:51:52 ] アセンブラで１〜８回のループをシフト+キャリーでやることはあったな。 720 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 23:56:44 ] もしかしたらループ回数が３２かいを超えたら・・・ どうするの？ 721 名前：デフォルトの名無しさん mailto:sage [2008/06/13(金) 08:21:14 ] >>720 普通にカウントしろよｗ 722 名前：デフォルトの名無しさん mailto:sage [2008/06/13(金) 11:54:06 ] 正直別にどうでもいい 泣くしかない 723 名前：デフォルトの名無しさん [2008/06/25(水) 13:20:16 ] 0xC89664 の１バイト目・２バイト目の値を求める方法をお願いします。 724 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 13:24:45 ] >>723 貴方の小人は頭から食べるのですか？　お尻から食べるのですか？ www.aozora.gr.jp/cards/000912/files/4673_9768.html 725 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 19:29:14 ] 囲碁（9路盤）のbitboardを作ろうとしています。 9x9なのでSSE2使えば128ビットレジスタ一個に収まるのでかなりの高速化が出来ると思っています。 囲碁のルールに上下左右を全て囲まれた石の塊は盤から取り除かれるというのがありますが、 これを高速に行うにはどうしたらよいでしょうか。 問題はSSE2は128ビットを一塊としたシフトが行えないことで、これのせいでどうしたらよいかわからなくなっています。 よろしくお願いします。 726 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 19:48:23 ] モンテカルロ木の実験ですか? 727 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 20:02:15 ] >>726 そうです。 モンテカルロはスピード命らしいので、SSEを使えないかと思っています。 728 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 21:11:08 ] 左シフトなら paddq である程度代用出来るだろ 729 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 21:49:09 ] paddqって64ビットの境目で切れ目が出来てしまいませんか。 730 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 21:53:24 ] 128ビット丸々だとバイト単位の命令しかないからねぇ。 x64環境を使っていいのならビット単位をやめてバイト単位にして 16本のXMMレジスタを9本使って9x9にした方がいいんじゃないかな？ 731 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 22:23:24 ] それならビット単位でshort[9]でもよさそうですが、 バイト単位にしたほうが有利なんですか？ 732 名前：デフォルトの名無しさん mailto:sage [2008/06/25(水) 23:18:33 ] ビット単位で操作できないから困ってたんじゃなかったの？ 733 名前：デフォルトの名無しさん mailto:sage [2008/06/26(木) 06:48:29 ] レジスタを9本も使うなら32ビットのレジスタでも9x9の盤は収まってしまいます。 その場合、ビット単位の操作は可能です。 x64でレジスタが16本あったとしても通常のレジスタを9本も占めるというのは考えにくいですが、 ＸＭＭレジスタなら9本使っても支障ないということでしょうか？ 734 名前：デフォルトの名無しさん mailto:sage [2008/06/26(木) 09:01:44 ] >>729 最大9bitしかシフトしないでしょ？　なら　境界にデータを置かなければいいでしょ あるいは16bitを１列にしてレジスタ２つにしたらどう？ 735 名前：デフォルトの名無しさん mailto:sage [2008/06/26(木) 10:08:36 ] >>733 x64で汎用レジスタが増えたとはいえ9本も使えばループや分岐に支障が出ると思うよ。 その点XMMレジスタなら浮動小数点演算しなければ基本的に空いてる。 736 名前：725 mailto:sage [2008/06/26(木) 19:15:01 ] 725です。 すいません。 皆さんにレスしていただいておいて申し訳ないのですが、 高速化について調べていたらGPGPUというのが見つかりました。 グラボに計算をさせるというものなのですが、上手くツボにはまれば CPUの何十倍もの速度がでるそうです。 囲碁がはたしてグラボに計算させるのに向いてるのかどうかわかりませんが、 SSEは一旦忘れて、GPGPUについて調べてみようと思います。 グラボも３〜４万だせば結構いいのが買えるみたいです。 とりあえずGPGPUスレとCUDAスレにいって雰囲気つかんできます。 皆さんのレスには感謝しています。 失礼しました。 737 名前：デフォルトの名無しさん mailto:sage [2008/06/26(木) 19:47:50 ] そっち行ってもいいならFPGAっていうテもあるかもしれん。 738 名前：デフォルトの名無しさん mailto:sage [2008/06/26(木) 21:47:07 ] 5年ほど前にFPGAでオセロの石を返す部分を作ったが 普通にCPUで計算するより遅かった 739 名前：デフォルトの名無しさん mailto:sage [2008/06/26(木) 22:43:05 ] >>736 CUDAするなら前もって、GPUに計算させたい部分 設計しておけ わしは今日から3日でモンテカルロをCUDAで解けるように 勉強する 740 名前：725 mailto:sage [2008/06/27(金) 00:03:02 ] >>739 どもです。 ところで最新ハイエンドGPUはピーク性能1TFLOPS超えるらしいですね。 ＨＤＤもテラバイトの物が出てるし、時代はもうテラなんですねぇ。 741 名前：デフォルトの名無しさん mailto:sage [2008/06/27(金) 00:18:19 ] >>740 Radeon HD3870とGeforce9800GTXもってるけど 両方とも労せず2000スレッド以上生成して並列に計算できるよ 742 名前：デフォルトの名無しさん mailto:sage [2008/06/27(金) 00:32:16 ] >>725 一命令ではできないが，シフトしたいビット数を n として n/8 と n%8 とに分けてシフト命令使って後で合成すれば可能 743 名前：デフォルトの名無しさん mailto:sage [2008/06/27(金) 04:00:39 ] >>738 enumの様に贅沢にintを丸々一つ石に配分した方が良かったかもしれないね。 744 名前：デフォルトの名無しさん mailto:sage [2008/06/27(金) 07:18:19 ] ベクトル演算を利用するなら　閉曲線の内側か外側の判定で巻付判定法を応用するといいように思うな ビット演算じゃないけど 745 名前：デフォルトの名無しさん [2008/07/11(金) 01:01:51 ] あげ 746 名前：デフォルトの名無しさん [2008/07/20(日) 15:56:27 ] う 747 名前：デフォルトの名無しさん mailto:sage [2008/07/20(日) 20:41:05 ] 今どきビット演算で高速化とかｗ 748 名前：デフォルトの名無しさん mailto:sage [2008/07/20(日) 23:07:22 ] プログラミングマニュアル1・基本仕様ガイド の ・式 ってとこに詳しく書いてるだろ...読みもしないで不思議とか言うな 749 名前：デフォルトの名無しさん mailto:sage [2008/07/20(日) 23:07:59 ] 誤爆すいません 750 名前：デフォルトの名無しさん mailto:sage [2008/07/22(火) 10:17:23 ] こやつめ! 751 名前：デフォルトの名無しさん [2008/08/01(金) 03:07:44 ] 2^a　を渡されたときaを求める方法で何かいい物はありませんか？ なるべくループやlogを使わない物がいいです 752 名前：750 mailto:sage [2008/08/01(金) 03:26:58 ] >>751 追記、1≦a≦9 753 名前：デフォルトの名無しさん [2008/08/01(金) 03:27:44 ] >>752 自分の名前間違えた>>750じゃなくて>>751 754 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 04:04:46 ] ５１３個の配列持って、その中に１〜９を入れておく。[1]=なし、[2]=1、[3]=なし、[4]=2、・・・ [512]=9　演算はこれが最速。 755 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 04:06:47 ] サイズが問題なら、 if( n & 0x200 ) return 9; if( n & 0x100 ) return 8; ・・・ if( n & 0x002 ) return 1; 756 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 04:15:16 ] x86ならBSF 757 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 04:39:50 ] char bit[256] = {1,2,0,3,0,0,0,4, 略 }; bsf(int n) { int r; if ((r = bit[n&255])) return r; n >>= 8; if ((r = bit[n&255])) return r + 8; n >>= 8; if ((r = bit[n&255])) return r + 16; n >>= 8; if ((r = bit[n&255])) return r + 24; return 0; //解なし } 758 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 04:41:33 ] こんなのどうよ? bsf(bits){ bits-=1; int num; num = (bits >> 1) & 03333333333; num = bits - num - ((num >> 1) & 03333333333); num = ((num + (num >> 3)) & 0707070707) % 077; return num; } 759 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 04:52:26 ] >>754-758 ありがとうございます。みんなカッコイイ 760 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 05:52:52 ] >>757は char bit[256] = { 0,1,2,0,3,0,0,0, 4,0,0,0,0,0,0,0, 略 }; の間違いだった。 んで結果を-1すれば合うんじゃないかな。 761 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 06:23:57 ] こんなんでどよ int f(unsigned n){     int a=1;     unsigned b;     n>>=2;     b = n>>4;if(b)a+=4,n=b;     b = n>>2;if(b)a+=2,n=b;     return a+n; } 762 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 10:45:43 ] "_\0\5\1\10\6\2__\4\7_\3"[n*0xCA030FF>>28]; 763 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 14:50:59 ] お前頭いいなー、でも "_\1\6\2\011\7\3__\5\010_\4" じゃないか もう少し小さいハッシュもあった "\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28]; 764 名前：762 mailto:sage [2008/08/01(金) 16:32:34 ] あー間違えてたーthx そしてそっちのハッシュのほうが優れているね。 765 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 16:55:45 ] なるほど、ハッシュってそういう使い方するんだ。 766 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 17:47:48 ] >>762-763 異次元過ぎてついて行けないのだが解説頼む 767 名前：デフォルトの名無しさん mailto:sage [2008/08/01(金) 21:25:31 ] 俺もわかってないが gperfとかで完全ハッシュ関数を作るのと同じように (文字列ではなく)特定の数字から対応する特定の数値への完全ハッシュ関数を作っているんだと思う。 どうやって導いたかなんて知らん。 768 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 01:40:13 ] へええ 左シフトしたときに あるビット範囲（この例だと28ビット目から31ビット目）が シフト回数ごとにバラけるようにしているのか シフト回数　　(n*0x5300000)のbit28〜31の値 　　1　　　　　　　　0 　　2　　　　　　　　1 　　3　　　　　　　　2 　　4　　　　　　　　5 　　5　　　　　　　　10 　　6　　　　　　　　4 　　7　　　　　　　　9 　　8　　　　　　　　3 　　9　　　　　　　　6 んで配列テーブルをlookupすると。 完全ハッシュ関数って、元が異なれば必ず先が異なる関数のことだっけ。 じゃないとこれ使えないよな。 小さいというのは先の範囲、つまり今回は28〜31の４ビットのことか。 確かに小さいほうがメモリとキャッシュに優しいですな。 という感じであってますか。 >どうやって導いたかなんて知らん。 俺も知りたい。 769 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 01:52:05 ] 頭良すぎる 770 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 01:56:27 ] 2chってすげーな 771 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 10:03:58 ] ビット演算ってたしかにすごいけど、 ソースに組み込むときは、その演算の意味とメリットなど ビット演算を導入した経緯や思想も書いてほしい・・・ ソース理解に時間がかかったり、修正が大変・・・ まあ、俺がお馬鹿なのかもしれないけど。 あと、763って751からの流れなんですか？ それとも別の流れ？ 772 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 10:14:13 ] 最後の2行から見ても明らかに >まあ、俺がお馬鹿なのかもしれないけど。 が正解。 773 名前：デフォルトの名無しさん [2008/08/02(土) 10:17:05 ] このスレって頭のいい奴もいるけど、 771みたいなバカもいる。 バカはROMっていろ！死ね771！！ 774 名前：それは俺か (w mailto:sage [2008/08/02(土) 10:59:13 ] まあ、バカにレスする奴はもっとバカだけどな。 775 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 11:02:09 ] 1、2、4、8、16、32、64、128、256、512の完全最小ハッシュ値を作る。 ttp://www.ic-net.or.jp/home/takaken/nt/slide/hash.html これか？ >>762は本当に頭がいい。>>763の書き込みがなかったら 意味も解らずスルーするところだった。 776 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 12:58:48 ] 512の完全ハッシュを作ってそれを1〜9のテーブルに掛けるって事？ 分かった気がする。 777 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 13:59:12 ] >>775 でも、保守する奴が >>762 みたいに頭いいとは限らんから、 仕事のプログラムなら >>754-755 あたりのほうがいいと思う。 778 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 14:04:14 ] 当たり前。こんなのは所詮パズル。商用コードでこんなの書けない。 >>762みたいなのが許されるのは趣味のプログラミングだけだよ。 779 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 16:19:14 ] 後は極端に処理速度がネックになってるところとか、 ビックリするほど容量が無いプラットフォームとか、 コンパイラが準備されてなくてアセンブラで書かなきゃいけないような場合、 更にRISCみたいに見た目と実行順が違うような環境だと 読む量が少ない短いコードが逆に役に立つ。 自慢を理由に書くと間違いなく死を招く。 780 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 16:20:19 ] コメントで書いておけば十分じゃないかな。 今でもまだまだ、速度やサイズ重視の分野はあるし。だいぶ少なくはなっているけど。 781 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 16:32:12 ] 現状、用途として大きそうなのはシェーダー周りか。 782 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 16:36:45 ] 画像処理ならいくらでも速度欲しいけどな 783 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 16:49:03 ] 昔、VUアセンブラの実装をしたが、ライブラリの増加により俺の約700byteのプログラムが 入らなくなり削りに削って「400byteだけ下さい！」と上司に嘆願したのは懐かしい思い出。 784 名前：デフォルトの名無しさん mailto:sage [2008/08/02(土) 18:57:37 ] >>777 それは同意だけど、 >>762 のエッセンスを抜き出して、わかりやすくすれば いいんじゃないかな おそらく、2^a を掛けると aビット左シフトする、というのは誰にも自明だけど １〜９の値にマップするマジック定数がややトリッキーかと なら、見た目にわかりやすいようシフト数を４倍にして、（ついでに右シフトにして） こんな感じでどうだろうかね(64ビット整数が使えることが前提だけど＾＾） /* assume that n is 2^a (1<=a<=9) */ 　return (0x9876543210LL / ( n * n * n * n )) & 0xf; 785 名前：デフォルトの名無しさん [2008/08/03(日) 02:24:01 ] 一番右の1を探すとき~a&(a-1)でできますよね、じゃあ一番左の1を探すときは何かありませんか? 786 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 02:37:33 ] 掛け算が４回・割り算が１回ってのが、演算量的に・・・　俺が8bitに慣れてるからかな？ 64bit整数があるにしても、nが32bitならn*nで64bitでしょ。中間結果でbitが失われるんじゃ？ 787 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 02:40:55 ] >>785 754とか755じゃダメなの？もっと速い／小さいのってこと？ 788 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 02:55:56 ] >>785 関係ないがa&(-a)で右端の一ビットを得られるぞ、左端は無理じゃないか 789 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 03:17:47 ] www.nminoru.jp/~nminoru/programming/bitcount.html 790 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 03:41:51 ] >>787-789 どうもです、今見た資料に左端を操作する命令列は存在しないって書いてあったorz 791 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 03:56:21 ] 左右反転するビット演算子でもあればね 792 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 03:59:50 ] a = ( ( a >> 16 ) & 0x0000ffff ) | ( ( a << 16 ) & 0xffff0000 ); a = ( ( a >> 8 ) & 0x00ff00ff ) | ( ( a << 8 ) & 0xff00ff00 ); a = ( ( a >> 4 ) & 0x0f0f0f0f ) | ( ( a << 4 ) & 0xf0f0f0f0 ); a = ( ( a >> 2 ) & 0x33333333 ) | ( ( a << 2 ) & 0xCCCCCCCC ); a = ( ( a >> 1 ) & 0x55555555 ) | ( ( a << 1 ) & 0xAAAAAAAA ); 793 名前：784 mailto:sage [2008/08/03(日) 17:00:12 ] >>786 もちろん変数n は64ビット長 LP64なら long型だと思ってもらえばいいです 演算量については、いまどきの投機実行するCPUなら 下手に条件判定入るよりは速いと思うけど、・・・まあ状況次第ですね 794 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 17:25:07 ] ｎが64bitでも、n*n*n*n の中間結果はbit失われるでそ。 795 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 18:31:31 ] でも、仕事に使うとなると、 「シンプルにしようや」 で終わってしまうんですよね〜 そうすると、754や755に落ち着くのかな・・・ 796 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 19:39:21 ] そりゃそうだよ。 よほど特段の理由が無い限り、シンプルが一番。 797 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 19:51:28 ] 裸が一番いいのと一緒だ 798 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 21:10:39 ] >>794 2^9まででしょ？ 799 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 21:12:54 ] は？ 800 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 21:51:46 ] 0x1 * 0x1 => 1 0x3 * 0x3 => 9 0x7 * 0x7 => 0x31 0xf * 0xf => 0xe1 0xff * 0xff => 0xfe01 0xfff * 0xfff => 0xffe001 0xffff * 0xffff => 0xfffe0001 0xfffff * 0xfffff => 0xffffe00001 これに規則性みたいなものを感じるんですが、 何か法則があるんでしょうか？ 801 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 21:54:51 ] 初めの3つはともかく、 9*9=81 99*99=9801 999*999=998001 と同じようなもんだろ 802 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 22:06:41 ] よくわからんが、ビット演算とかって、日本人よりも インド人のほうが面白い発想しそうだね 803 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 22:09:36 ] >>800-801 ２進数に考えれば、最初から綺麗に並ぶよ。 1 * 1 = 1 11 * 11 = 1001 111 * 111 = 11001 1111 * 1111 = 11100001 11111 * 1111 = 1111000001 804 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 22:16:49 ] 0xffff * 0x10000 => 0xffff0000 0xffff0000 - 0xffff => 0xfffe0001 特に面白い事実はなさそうだが 805 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 22:21:59 ] 99*99=9801 これが国民機ナンバーの正体かー すると8801は？ 93.8136 * 93.8136 = 8800.99 収束しないのか 806 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 22:22:36 ] 収束？ 807 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 22:25:25 ] ごめん適当言った 808 名前：デフォルトの名無しさん [2008/08/03(日) 22:34:48 ] 無理数ね。 809 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 23:10:51 ] λ... PC-8001, PC8201, PC-6001, &c. ... 810 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 23:48:03 ] 獣の数字にまつわる屁理屈と同じようなもんだな あえて8801に意味を見出すなら99*99-1100とかなんとか 811 名前：デフォルトの名無しさん mailto:sage [2008/08/03(日) 23:49:53 ] 9801-1100 = 8701だな 俺頭大丈夫ｋ 812 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 00:08:26 ] PC9801が長いこと繁栄したのは99*99=9801 こういった力(ちから)を持つ数字が隠されていた影響に違いない。 その証拠に型番が9821に変わろうとしたとたん没落した。 きっと9801のままなら永遠の存在だったんだよ。 813 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 00:11:55 ] >>798 そうか、9bitのハッシュのエレガントな解法だったのね。ごめん。 ハッシュって、必要の都度、bit数見極めて作らなきゃいけないんだな・・・ 814 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 01:24:27 ] 実際に仕事でも使用可能な、 1.実用性がある 2.比較的わかりやすい ビット演算のアルゴリズムって何だろうね・・・ 815 名前：デフォルトの名無しさん [2008/08/04(月) 01:50:11 ] 名前がつくぐらい有名になればいいんじゃないかな。 例えばコメントに // 762氏ハッシュ とか書けるぐらいに。 816 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 01:56:23 ] すみません、 ＞"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28]; の頭の"\1\2\3\010\6\4\011__\7\5"がいまいち良くわかりません。 817 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 02:06:28 ] ただの文字列リテラルだよ 818 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 02:06:59 ] コメントに、「ハッシュがどうの」なんて書く奴ばっかだからダメなんだよ。 コメントに絶対に書かなきゃいけないのは、>>751-752だよ。 どういう実装をしたかのコメントなんて二の次三の次。 それなのに仕様のコメントを怠ったままで「すげーテクニック使ってるんだぜ」的なコメントを残しても意味なし。 そんなものを残すぐらいなら、(最低限の>>751-752の他に)assertでも使った範囲チェック入れとけ。 もちろん、>>762のやり方に対するコメント(完全ハッシュ関数とテーブル)はあった方が良い。 けど、仕様についてのコメントの方がはるかに重要。 819 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 03:06:57 ] 日本語でおｋ 820 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 03:45:03 ] 日本人でおｋ 821 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 04:32:52 ] 二本イレマスカ？ 822 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 04:59:25 ] イマレス 823 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 08:02:17 ] #if 0 // オリジナルのロジック ...; #else // 速度重視で書き換え ...; #endif 824 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 08:15:04 ] "..."[...]という書き方をこの流れで始めて知った 何でこのスレにいるかって？ 知るために見ているのさ 825 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 09:53:07 ] K&Rの頃のCをやってた人間からすれば常識 826 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 12:37:57 ] >>816 文字リテラル "abc"とかならキャラ型の配列だって判るでしょ。 スペース（0x20）より小さい値のcharは 「\８進数」 で書く約束になってる。 "\1\2\3・・・"は、char xxx[ ]={ 1, 2, 3, ・・・, 0 };という配列が生成される。 827 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 13:33:40 ] >>826 ＞スペース（0x20）より小さい値のcharは 「\８進数」 で書く約束になってる。 なってない。 828 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 17:24:05 ] \001 \002 \017 とかだよ。　Hexの場合は \xhh と書く約束になってる。 俺のはLSIC85とか adUc51とか、クミコ系ばっかりで、ANSIは知らないけど。 829 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 18:13:00 ] 0x20以上の値で使ってはいけないという決まりもないわけで。 830 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 22:15:16 ] 最下位8bitについてなら左右を逆転するコードあった筈 こんな感じだったと思うけど、よく覚えてないや x:src y:dest s=(x*0x02020202)&0x84422010 t=(x<<3)&0x420 y=(s+t)%1023 831 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 22:49:39 ] >>792で既出だべ。 832 名前：デフォルトの名無しさん mailto:sage [2008/08/04(月) 23:59:20 ] >>828 \n \t \r とかもあるわけで。 833 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 00:45:34 ] >>832 は？ 834 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 01:21:35 ] 文字リテラルが配列の名前？？？ どうも「文字リテラル＋[]」が良くわからん。 ビット演算うんぬんではなく・・・ C言語でこれを書いてコンパイルが通るのか？ どうもこのスレに付き合うには、大学などできちんと学ぶか 元々、この手のことが好きじゃないとついていけませんね・・・ 社会人になってから、プログラムを覚えたアホアホな俺の プリンみたいな脳みそでは、だめかorz 835 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 01:37:17 ] なんでワカラン？？？　大学とか関係ないぞ。 char * buf = "01234567"; char a = buf[0]; が判れば、 char a = "01234567"[0]; だって判るだろ。 836 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 01:41:46 ] char a = 0["01234567"]; こんなのもある。これが直感的に納得しづらいというのはワカランでもないけど、 char a = "01234567"[0]; こっちは普通だべ。 837 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 09:00:56 ] >>834 >元々、この手のことが好きじゃないとついていけませんね・・・ 当たり前だと思うんだが。 838 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 10:50:52 ] 文字列定数がメモリ空間に配置されている状態をイメージできていないんだな。 プロセスメモリエディタかバイナリエディタと睨めっこでもしてみればいいんじゃね。 839 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 12:25:02 ] 文字列リテラルは、コンパイラがDATAやTEXTのようなセグメントに配置して プログラムの中に埋め込まれるちょっと特殊なchar[]にすぎん。 "hoge"とか書いた場合、これはそういう配列を暗黙にどっかに確保しろよと コンパイラに言っているのと同時に、式の中で評価されるときは、その（無名の） char配列の名前と同等に扱われる。 要はchar[]なのだから、char*な変数に文字列リテラルを代入したり printf()のような関数に文字列リテラルを引数として渡したり、ということは 普通に・当然のようにやっているはずだ。 さすがにprintf("hello, world"); というコードを見たことが無いとは言わせない。 ならば、[]演算子を適用できるということも当然分かるはずだな。 多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。 840 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 12:32:50 ] >>834 []を特殊なものだと思うからいけない。ただの演算子だ。 a[b]とあったら必ず*(a+b)と置き換えが可能だから、ただのポインタ演算とデリファレンスに成り下がるだろ。 デリファレンスするために、aかbのどちらかはポインタでもう一方は整数でないといけないだけだ。 例えばchar a = 0["01234567"]とあったらchar a = *(0 + "01234567")になり、即ちchar a = *("01234567")であり、char a = "01234567"[0]だ。 これでも理解しにくかったら、全部一時変数にしてしまえばいい。 const char * p = "01234567"; int i = 0; として、char a = p[i]; ならわかるだろ。。 841 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 13:15:16 ] おそらくは、 　配列の名前[インデックス] のように教えてる参考書の類が悪いんだろう。 842 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 15:15:59 ] >>834 このスレ開いただけでも望みはある！ 843 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 18:04:55 ] すごいな。叩きが日常の2chで、ｼﾛｰﾄにここまで優しいのは、久しぶりに見た。 844 名前：デフォルトの名無しさん [2008/08/05(火) 19:53:06 ] >>838 メモリをイメージする訓練も大切だが、 もっと抽象的に捉える訓練も忘れないで欲しいな。 845 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 20:05:18 ] そうだなー、最近そういうトレーニング怠ってるかも…俺。 846 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 21:13:44 ] >>841 真の文法を書いてる本は稀少なのかね。 847 名前：デフォルトの名無しさん [2008/08/05(火) 21:27:48 ] >>846 真の文法を書いている本でも、いでおしんくらてっぃくなところは はしょっているか、読み取れないようにしてるのが多いと思う。 実際、俺なんか、 int typedef integer; なんて構文が許されるなどとはイソターネットで初めて知った。 848 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 21:44:04 ] なるほど、許されない理由がないから許されるんだな。 849 名前：デフォルトの名無しさん mailto:sage [2008/08/05(火) 21:47:55 ] もしかして：void main(void) 850 名前：デフォルトの名無しさん [2008/08/05(火) 22:11:34 ] >>846 真の文法をサポートする本とはLinuxのことである。 Linux以外は紛い物である。 851 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 00:58:33 ] >>833 いや、意味が理解できないなら別にいいんだ。 >>839-841 C/C++ に毒されすぎ (w 文字列と文字の配列が互換の言語はあまり多くないから、 "abcd"[0] を >>834 が奇異に感じるのも無理は無いよ。 852 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 00:59:35 ] []はmonadの一種でしょ 853 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 01:15:22 ] みなさん、あほな俺に丁寧にありがとう。 さすがに理解できました。 ＞多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。 そうですね。はじめてみました。 なんかすっきりしました。 皆さんありがとうございました。 なんかビット演算って難しそうですけど、面白そうですね。 私も、最近処理速度を意識したコードを書く機会があるので 色々参考にします。 （クロックが25KHzなので、処理速度を意識しないといけないんですよ） 854 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 01:31:44 ] ずいぶん遅くない？　8ビット機のときもMHzだったが。。。 855 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 09:28:35 ] ケルビン・ヘルツという単位は寡聞にして知らない。 856 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 21:19:11 ] ＞ずいぶん遅くない？ そうなんですよ。1サイクル40usなので、ビット操作（ビットクリアやビットセット）で 7サイクル取られるので、7*40=280us=0.28msもかかるんですよね・・・ 857 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 21:30:37 ] えー！　そりゃ遅い。なんだろ。FPGAかなんかか。 最近は組み込みの分野でもJAVAだったりするが、まだまだCの出番はあるってことか。 858 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 22:00:42 ] ボタン電池1個で半年動かすようなものなんじゃね？ 859 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 22:06:20 ] >>857 > まだまだCの出番はあるってことか。 て言うか、アセンブラの出番だと思うけど。 860 名前：デフォルトの名無しさん mailto:sage [2008/08/06(水) 22:17:37 ] Cで書く予定です。アセンブラでは保守のことを考えると難しいので。 如何にCで効率の良いコードを書くか。 クロックを遅くしているのは消費電流の低減のためです。 普段は32MHzで動作しますよ。 861 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 17:23:46 ] >>767-768 ちょっと遅くなったが、求め方が解った。 今回は2^1〜2^9だからちょっと変則的なんだが、概念としてはM系列の応用みたい。 なるほどねー。 slashdot.jp/~Tellur52/journal/448479 862 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 17:25:18 ] >>861 お前ここに糞スラのURL張るの禁止されていること しらんのか？ 863 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 17:27:12 ] スラッシュドット禁止ってどんだけ情報弱者なんだよ。 え？あっちから拒絶してんの？ 864 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 17:27:38 ] あれ？　板ルール？ スマンかった。忘れて。 865 名前：861 mailto:sage [2008/08/09(土) 17:31:07 ] >>863 あっちも出入りしているけど、そういうことはないと思う。 ここの板ローカルのルールなのかね？ ここも長年見ているが、あまり聞いたことないけど。 866 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 18:01:21 ] >>862はさすがに釣りだろお前ら釣られ杉 867 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 18:40:27 ] ぐぐってもあまりいいページがないんだが、どこかに解説ない？＞M系列 868 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 02:54:03 ] 周期2^p-1ビットの列があって、そこからpビットを切り出すと、オール0以外の全てのパターンが現れる p=3の場合のM系列は例えばこう。 0011101 ↓ (周期2^3-1=7で同じパターンの繰り返し) 001110100111010011101... 上の桁から3ビットを切り出すと、 001 (1) _011 (3) __111 (7) ___110 (6) ____101 (5) _____010 (2) ______100 (4) 1〜7まで全部出るだろ。これに000だけ追加すればおｋ。 これだけだと順番がバラバラなので、テーブルと組み合わせる。 ↓この文字列リテラルの部分な。 "xxxxxxx"[(ハッシュ計算式)] すると、>>762-763になりますよ、と。ビット溢れによるマスクなども組み合わせているが。 869 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 03:11:08 ] 任意の長さのシフトレジスタで適当なタップを選んでフィードバックすれば 最長系列（Ｍ系列）が得られるんだが， このタップが整数論の方の原始多項式から求められるというのは覚えてる 870 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 16:08:47 ] Cで保守の事を考えずに書いたときに保守しやすいのかといわれればもちろんNOだろ 素人が下手にCで最速コード書くと後で自分で読めないから、最初からアセンブリでやったほうがいいと思う マクロが使えれば読みやすくなるのも事実だしな MASMだと、アセンブリの癖にIFだのELSEだの使える。マクロがなければCでプリアセンブラを書けばいいし 871 名前：870 mailto:sage [2008/08/10(日) 16:10:30 ] 安価書き忘れ >>860 872 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 17:38:03 ] CPU換えたときの心配してるんだったらC 873 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 17:55:59 ] スレタイも読めないバカが多いね。 移植性や保守性を犠牲にしてでも高速化しようってのが趣旨なのに。 874 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:16:42 ] 書かれてもいない事が見えるバカが居るんだね 875 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:25:56 ] 【高速化】ビット演算　0x02 876 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:31:54 ] やばいですやばいです ちょっと暴走して勃起が止まりません リセットできないどうしよう 877 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:35:44 ] 適切な勃起フラグを提げろ。 878 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 19:02:20 ] トシなのでフラグ立ちません！　どうしよう！ 879 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 19:20:29 ] (´･ω･`)知らんがな 880 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 19:20:34 ] ＞ 移植性や保守性を犠牲にしてでも そりゃビット演算すれば多少は移植性が犠牲になるだろうけど、 それだけならぜんぜん問題にはならない。 所詮フラグなんて１本しかないんだからな。 ただまあ、 大きさはいろいろだから互換性がない場合も確かにある。 881 名前：デフォルトの名無しさん [2008/08/26(火) 15:29:02 ] 　＊　 　　　+　　　　巛 ヽ 　　　　　　　　　　　　〒　!　　　+　　　　。　　　　　+　　　　。　　　　　＊　 　　　。 　 　　　　+　　　　。　 | 　| 　　　＊　 　　　+　　 /　/　　　イヤッッホォォォオオォオウ！ 　　　　　　 ∧＿∧ /　/ 　　　　　　（´∀｀　/　/　+　　　　。　　　　　+　　　　。　　　＊　 　　　。 　　　　　　,-　　　　　ｆ 　　　　　 / ュヘ　　　　| ＊　 　　　+　　　　。　　　　　+　　　。　+ 　　　　　〈＿｝ ）　　　| 　　　　　　　 /　　　　! +　　　　。　　　　　+　　　　+　　　　　＊ 　　　　　　 ./　　,ヘ　 |　　　　　　このスレッドは８８０を超えました。 　ガタン　||| j　　/　|　 | |||　　　　　　　　次レスも…BITクオリティ！！ ――――――――――――　　　　　　 　 pc8.2ch.net/tech/ ああ暇だ 882 名前：デフォルトの名無しさん mailto:sage [2008/08/27(水) 20:01:38 ] ちょっとリンク張らせてクレ。 science6.2ch.net/test/read.cgi/math/1209732803/ の427に問題を投稿したんで、暇ならチャレンジしておくれ。 883 名前：デフォルトの名無しさん mailto:sage [2008/08/27(水) 20:36:01 ] 算数得意だけど数学は苦手 884 名前：デフォルトの名無しさん mailto:sage [2008/09/04(木) 14:51:58 ] chessprogramming.wikispaces.com/Bitboards ここまでくると、なにがなにやら 885 名前：デフォルトの名無しさん mailto:sage [2008/09/04(木) 15:15:42 ] 簡単じゃん 886 名前：デフォルトの名無しさん [2008/09/13(土) 20:24:38 ] (･∀･) ｶﾞｯｰ 887 名前：デフォルトの名無しさん mailto:sage [2008/09/14(日) 13:55:19 ] 発音できません＞＜ 888 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 23:19:16 ] ん？ヌルポはどこ？ 889 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 01:25:58 ] >>888 888 890 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 16:29:38 ] 又ﾉﾚ木ﾟ 891 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 16:31:31 ] ガッ 892 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 17:12:10 ] 力ﾞっ 893 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 19:24:05 ] >>890 その表記、キモすぎるｗ 894 名前：デフォルトの名無しさん [2008/09/27(土) 11:01:16 ] 整数間のキャスト演算について教えてください。 例えば、2の補数で表される4bitの値を8bitに変換する場合、 正の値： 0001 -> 0000 0001 # 最上位bitが0なら上位bitに0000を補う 負の値： 1110 -> 1111 1110 # 最上位bitが1なら上位bitに1111を補う bit8 = (bit4 & 0x8) ? (bit4 | 0xF0) : bit4; 逆の変換は、 正の値： 0000 0001 -> 0001 # 上位4bitを削除 負の値： 1111 1110 -> 1110 # 上位4bitを削除 bit4 = bit8 & 0xF; という考え方で合ってます？ 895 名前：デフォルトの名無しさん [2008/09/27(土) 11:13:01 ] 合ってる。 896 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 11:29:26 ] どうも 897 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 12:16:50 ] >>894 ARMならプレディケートに展開されるのでそれで十分速いんだが 欲をいえばこっちのほうが命令数とかレジスタ節約できるかもしれないね。 bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0; また、比較命令はall 1 か all 0のビットマスクを生成するタイプのCPUなら、 ビットマスクと0xF0との論理積をとるだけで加算する値を取得できる。 しかし、2項選択は多くのＣＰＵ分岐命令に一般的には遅い。 シフトが遅くないならこっちを試してもいい bit8 = (signed char)bit4 << 4 >> 4; 現実には多くの32ビットCPUはレジスタサイズ未満のビット演算は遅いのでこっちのほうがいいかも bit8 = (signed char)(((signed int)bit4 << 28) >> 28); 要はネイティブで算術シフト命令のできる最小単位ならなんでもいい。 同じロジックでbit16でもbit32でも展開できる。 898 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 12:31:00 ] しかし、2項選択は多くのＣＰＵでは分岐命令に展開されるので一般的には遅い。 日本語しゃべれ俺 899 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 13:06:59 ] > bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0; バグってるぞ。 900 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 13:13:06 ] bit8 = bit4 | ((bit4 & 0x8) ? 0xF0 : 0); これでいいのか？ 901 名前：894 mailto:sage [2008/09/27(土) 13:35:56 ] なるほどsingned型って右シフトで上位ビットを補ってくれるのね。 CPUは普通のPCのIntel x86系です。 902 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 13:49:08 ] x86ならシフト使う方法のほうが有効だろうね（Pentium 4はシフト遅いけど） bit4 = ecx bit8 = eax と仮定して mov eax, ecx sal eax, 28 sar eax, 28 and eax, 0xFF たった4命令で済む。bit4を破壊していいなら3命令。 903 名前：デフォルトの名無しさん [2008/09/27(土) 19:47:32 ] >>895 ちがうだろ 算術シフトか論理シフトかはコンパイラ依存 904 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 19:50:09 ] 100レスくらいで終わってもよさそうなのに実によく伸びるなこのスレ。 905 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 22:02:58 ] まあメジャーなコンパイラならsignedで算術シフトになるけどね。 //でコメントにならないコンパイラ並みには非互換問題あるのかな？ ローテートくらいまではC/C++標準仕様に入れておいて欲しいものだ 906 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 22:19:03 ] 分岐は 907 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 22:26:53 ] >>903 > 算術シフトか論理シフトかはコンパイラ依存 負数の右シフトの動作のことを言ってるのか？ >> 2の補数で表される4bitの値を8bitに変換する場合 という条件下なら >>894 の内容に誤りはないと思うが。 そもそも、>>894 のレスにシフトのコードなんてないし。 # レスアンカーが >>897 なら同意するけど、あまり # 触らない方がいいと思う。 908 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 22:33:18 ] もうこれでええやん static const signed char table[] = { 0, 1, 2, 3, 4, 5, 6, 7, -8, -7, -6, -5, -4, -3, -2, -1 }; bit8 = table[bit4 & 15]; 909 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 22:33:41 ] ダンゴさんの星が落ち着いてきたな 910 名前：デフォルトの名無しさん mailto:sage [2008/09/28(日) 12:15:36 ] 表引きもいいけど、キャッシュ容量とかミスヒットとか気になるし、 算術シフトもちょっと……という場合にはこっちがいいのでは。 bit8 = -(bit4 & 0x8) | bit4 911 名前：デフォルトの名無しさん mailto:sage [2008/09/28(日) 12:29:09 ] 上の動作の流れはこんな感じ。 等幅じゃないと見にくいけど分かってもらえるかな。 src　　　　　temp　　　　dst ????mxyz 00000000 00000000 ????mxyz 0000m000 00000000 # temp = src & 0x8 ????mxyz 0000m000 mmmmm000 # dst -= temp ????mxyz 0000m000 mmmmmxyz # dst |= src 912 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/28(日) 12:34:50 ] この程度の小さいテーブルなら表引きは割と効果あるよ。 SSSE3のpshufbやAltiVecのvpermで16並列化もできるし。 913 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/10/02(木) 00:50:06 ] >>910 x86で4命令だな。 mov eax, ecx and eax, 0x08 neg eax or eax, ecx ちなみに>>902の方法はこれなら3命令。 mov al, cl sal al, 4 sar, al 4 ただ、とてつもなくパーシャルレジスタストールの臭いがするぜ 914 名前：デフォルトの名無しさん [2008/10/11(土) 16:18:31 ] Cで上手いことローテート命令に割り当てられるような書き方って何かある？ 今は、8ビットローテートの場合は (val << num) | (val >> (8-num) ) って書いてるけど、アセンブラ見てもまんまシフトとORで作られるんだよな 最後の手段でインラインアセンブラ使ってるけど、誰かＣでいい書き方知ってたら教えてくれ 915 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 16:23:26 ] そもそもローテート演算子がないからローテートを出力するコンパイラがないんじゃ 916 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 16:30:52 ] gccなら unsigned foo(unsigned x, int n) { return (x << n) | (x >> (32 - n)); } で↓になったよ _foo: movl 4(%esp), %eax movl 8(%esp), %ecx roll %cl, %eax ret 8ビットは無理だた 917 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 16:48:33 ] ダンゴさんならローテートの速度について一言ありそうだな 918 名前：914 [2008/10/11(土) 16:51:22 ] あぁ、コンパイラのオプション弄ったらちゃんとローテートになったわ ちなみにCPUはARM、コンパイラはARM製のコンパイラです 速度に関しては何ビットローテートしても1クロックで済む、RISC万歳 919 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 17:56:35 ] >>914 インラインアセンブラで書いたものを、インライン展開できるようにしておくのはダメなの？ インラインの関数呼び出しでは不満？ 演算子でやりたいなら、演算子をインライン展開できるように定義すればいいだけだと思うが。 920 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/10/12(日) 14:47:04 ] >><とか <<>とかみたいな演算子を逆輸入してくれれば良いんだがねぇ 921 名前：デフォルトの名無しさん mailto:sage [2008/10/13(月) 21:04:47 ] 無理に演算子にしなくても、 コンパイラが認識する組込関数にすれば十分だよ。 922 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 21:43:35 ] このほうがローテートっぽい @> <@ 923 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 21:49:25 ] >reg> <reg< 924 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 22:01:01 ] �� �� 925 名前：デフォルトの名無しさん mailto:sage [2008/10/20(月) 01:05:00 ] _lrotr _lrotl 926 名前：デフォルトの名無しさん mailto:sage [2008/10/20(月) 15:43:41 ] |> <| 927 名前：デフォルトの名無しさん mailto:sage [2008/10/20(月) 22:06:50 ] >>925 指輪物語? >>926 シュレディンガー音頭? 928 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 08:56:43 ] 記号の演算子じゃなくて普通に単語使えばいいのに ばかでしょ 929 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 23:59:57 ] 指輪物語はlotrだなｗ 930 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:38:04 ] >>929 tlotr 931 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:46:10 ] 公式はLOTR 932 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:53:09 ] なんで指輪物語スレになってんの・・・ 933 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:56:14 ] >>931 tlotr ググれば一目瞭然。 934 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 04:08:26 ] The Lord of the Rings だし。 935 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 08:55:55 ] Lordsな。両方複数系。 936 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 12:18:22 ] www.lordoftherings.net/ つまり、オフィシャルサイトは間違っていると。 937 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 12:34:52 ] >>935 Lordが正しい。 >>936 「the」がないのは、ドメイン取得の問題じゃないかな。 938 名前：デフォルトの名無しさん [2008/10/22(水) 16:44:03 ] 何時の間にか指輪スレ化している流れを豚切。 man gawk を見ると lshift, rshift って内部関数が実装されているんだな。 939 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:50:42 ] >>925もVC++独自のローテート関数なわけだが。 指輪とはあんまり関係ない。 940 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:59:17 ] 指輪物語とまで云うならthe fellowship of the ringだろ 941 名前：,,・´∀｀・,,）っ-○◎○ mailto:sage [2008/10/23(木) 01:44:47 ] lotrをロートルと呼ぼうのスレはここですか？ >>940それ第１章の副題 942 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 08:38:48 ] >>941 何…だと……？ 943 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 00:00:41 ] >>933 lotr の検索結果 約 9,330,000 件中 1 - 10 件目 (0.15 秒) tlotr の検索結果 約 69,400 件中 1 - 10 件目 (0.17 秒) 一体何が一目瞭然なんだか。 >>937 > 「the」がないのは、ドメイン取得の問題じゃないかな。 レスするなら、URL だけじゃなくてちゃんとページ見ろよ。 省略形で定冠詞を省略するのはごく普通。 ２個あるうちの片っぽだけというのはちょっと違和感あるけど。 944 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:12:27 ] 流れぶったぎって次スレ案 【指輪】ビット演算　0x03【物語】 945 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:13:31 ] いや、つまんないから 946 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:17:20 ] つーかもうスレ自体不要 947 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 17:26:25 ] >>944 これはコラだね、俺は騙されんよ。 948 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 18:44:44 ] >>947 >>945 949 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 18:53:14 ] >>948 >947 950 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 21:52:57 ] >>944-950 >>9 951 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 20:50:31 ] >>943 それは省略形であって正式ではない。 テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。 952 名前：デフォルトの名無しさん [2008/10/26(日) 21:00:55 ] 0を移動していくシフト演算っていい方法ある？ 111111011 ↓ 111110111 ↓ 111101111 ↓ 111011111 こう言う感じで 953 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 21:02:22 ] a << 1 a | 1 954 名前：デフォルトの名無しさん [2008/10/26(日) 21:06:31 ] >>953 速レスサントス 955 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2008/10/26(日) 21:10:29 ] 逆に考えるんだ 1のほうを立てて 00000100 ↓ 00001000 ↓ 00010000 ↓ 00100000 参照するときに反転すればいいと考えるんだ 956 名前：デフォルトの名無しさん [2008/10/26(日) 23:24:33 ] ttp://www.amazon.co.jp/gp/product/images/0618002251/ 957 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:41:34 ] >>951 > それは省略形であって正式ではない。 一体何を言ってるんだ？ > テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。 アホはお前だよ、単語の区切ぐらい見てるだろ。 yaho の検索結果 約 2,580,000 件中 1 - 10 件目 (0.06 秒) yahoo の検索結果 約 2,330,000,000 件中 1 - 10 件目 (0.08 秒) そもそも、どうやって「ググれば一目瞭然」なのか >>933 に聞けよ、クズ。 958 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:54:28 ] マジで>>944か>>946でいいような気がしてきた もうどうでもいいよ 959 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 00:08:36 ] それ省略になってないし

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

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