【高速化】ビット演算　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 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];

---

---

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

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