【高速化】ビット演算　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 29 名前：デフォルトの名無しさん mailto:sage [2006/09/28(木) 07:42:57 ] 1マスが2ビット（黒：01, 白：10, 空：00）で、8マス分の情報が下位16ビットに並んでいれば 分割統治法が使えそうだ t = x & 0xcccc; x = (x & 0x3333) + (t >>= 1); x += t >>2; t = x & 0xf0f0; x = (x & 0x0f0f) + (t >>= 3); x += t >> 4; t = x & 0xff00; x = (x & 0x00ff) + (t >>= 7); x += t >> 8; 論理演算 6回、シフト 6回、加算 6回 3倍して足していく方法は、乗算 7回、加算7回 なので、少し速そう 30 名前：デフォルトの名無しさん mailto:sage [2006/09/28(木) 08:12:34 ] t = x & 0xcccccccc; x = (x & 0x33333333) + (t >>= 1); x += t >> 2; t = x & 0xf0f0f0f0; x = (x & 0x0f0f0f0f) + (t >>= 3); x += t >> 4; t = x & 0xff00ff00; x = (x & 0x00ff00ff) + (t >>= 7); x += t >> 8; ix1 = x >> 16; ix2 = x & 0xffff; とすれば、2行分のインデックスを同時にもとめることができる。 64ビット変数を使えば4行分をまとめて計算できる。 それならかなり高速になりそう しかし、ビットボードは白黒別々なので、それを2ビットごとにまとめなくてはいけない その処理に時間がかかりそうだ 31 名前：デフォルトの名無しさん mailto:sage [2006/09/28(木) 08:34:46 ] 2ビットごとにまとめる処理は、いわゆるシャフルだ 下位32ビットについて、 b = black & 0xffffffff; b = ((b & 0xffff0000) << 16) | (b & 0xffff); b = ((b & 0xff00ff00ff00) << 8) | (b & 0xff00ff00ff); b = ((b << 4) | b) & 0x0f0f0f0f0f0f0f0f; b = ((b << 2) | b) & 0x3333333333333333; b = ((b << 1) | b) & 0x5555555555555555; で間に０を入れ、白も同様に処理し、 x = b | (w << 1); とすれば、2ビットごとにまとめることができる。 あとは >>30 の処理を行えば、下4行分のインデックスが求まる。 32 名前：デフォルトの名無しさん mailto:sage [2006/10/06(金) 12:00:35 ] >>29 間違ってない？ 33 名前：デフォルトの名無しさん mailto:sage [2006/10/06(金) 13:43:55 ] ビット演算だけで四則演算ってできるの？ 34 名前：デフォルトの名無しさん mailto:sage [2006/10/06(金) 22:17:36 ] それはギャグで言ってるのか 35 名前：デフォルトの名無しさん [2006/10/08(日) 11:28:06 ] 加算器って基本はビット演算だそ。 回路図や真理値表は以下のページにあるぞ。 ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8 いわゆるCPUだとかマイクロ・プロセッサつーのは、 その奥深くに 加算器に演算レジスタがあって、 ノイマン型にプログラム通りに計算をするためのものなんだから。 減算 や 負の数を扱うには「2の補数」 ja.wikipedia.org/wiki/2%E3%81%AE%E8%A3%9C%E6%95%B0 と言った捉え方で数を扱うのだ。 36 名前：デフォルトの名無しさん mailto:sage [2006/10/08(日) 11:38:50 ] ビット演算だけで発明ってできるの？ 37 名前：デフォルトの名無しさん [2006/10/10(火) 23:41:36 ] ビット演算があれば、何でもできる。 38 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 23:46:16 ] ビット演算ができれば、僕にも彼女ができたりしますか？ 39 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 23:49:48 ] 当たり前。 40 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 23:51:57 ] or and not があれば全ての演算ができる？ 41 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 23:57:28 ] NANDがあれば、何でもできる。 42 名前：デフォルトの名無しさん mailto:sage [2006/10/10(火) 23:58:38 ] NORでもいいぞ 43 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 00:21:23 ] わかってないな 44 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 01:00:10 ] 元気ががあれば、何でもできる。 45 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 01:01:30 ] 行けば分かるさ 46 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 02:06:14 ] やっぱ、NANDとNORのハイブリットが良い？ 47 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 06:57:09 ] Trががあれば、何でもできる。 48 名前：デフォルトの名無しさん [2006/10/11(水) 13:16:09 ] Magic Algorithm aggregate.org/MAGIC/ 49 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 16:56:33 ] >>48 ひょっとしてradiumあたりで見た輩か？ >>1のサイトでとりあげられてる。 せめて>>1のサイトくらいみればよいのに・・・ 50 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 23:15:53 ] C++やJavaだとどちらかというと保守性重視だから 性能改善要求出る前にビット演算使うと白い目で見られる。 51 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 23:18:57 ] >>50 例え処理が１行だけであっても、関数（インラインで良い）にしとけば文句でないはず。 52 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 23:26:39 ] >>51 勿論明瞭なコメント付きでな。 53 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 23:36:36 ] >>51 ついでに代替コードを書いておくとなお良い。 54 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 04:27:35 ] ゴリゴリのチューニングが求めらるような場面でもなければ、たいていはコンパイラの最適化だけで事足りるわけだが。 55 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 05:31:51 ] スクリプトでマスかいてろ 56 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 09:38:47 ] >>54 確かにそれで文句が出ないどころかメンテしやすければ褒められるべきところではあるが 多少の遊び心があってもそれはそれで許される。 >>51-53のようなことをしてあれば。 （代替コードのテストも必要なことは当然なので、プログラマの負担はアップするが） 57 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 13:48:49 ] ビット演算による最適化が必要で パフォーマンス的に代替が効かないからこそ そういうコードを書くわけだから 同等以上の速度が出た上に読みやすいコードを出せなければ 批難する事はできない。 もちろん意味もなくビット演算するアホの話は別として。 58 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 16:28:36 ] でも普通インラインアセンブラ使うよね。そういうビット演算だと。 上で出てるようなCでなんて書かないよ。 59 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 16:34:33 ] いや、俺はループアンローリングだとかプロセッサのスケジューリング管理 なんか考えたくないからC言語で書くけどね。 まぁ、どうしてもビット回転(rotate)が必要ならインラインアセンブラの 使用も検討するが。 60 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 16:41:08 ] インラインアセンブラはアセンブラとは違うよ 61 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 18:52:45 ] >>60 いや、当たり前の事実を主張されてもなぁ。 しかもなぜにこのタイミングで？わけわからん。 62 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 21:02:46 ] >>60 何が違うの？ 63 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 21:26:25 ] ものほんのアセンブラならそもそも命令セットの数が違うみたいな？ 64 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 23:34:07 ] なんつー理屈だ。 寧ろインラインアセンブラだとCコード部とのI/Fが簡単に書けるメリットはあるね。 65 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 00:47:40 ] ネイティブアセンブラ 　C言語との連携は関数呼び出しの形でのみによって実現される。 　殆どのメモリアクセスはシンボルではなくオフセット値での指定となるからめんどい。 　最適化の善し悪しはすべて自分の腕にかかっている。 インラインアセンブラ 　Cのソースに埋め込むことが出来るので、必要な箇所を個別に関数化する必要がない。 　関数内の局所変数にシンボリックにアクセスできる。 　一部のコンパイラはインラインアセンブラで書いた箇所も勝手に最適化してくれやがる。 66 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 00:56:32 ] スレ違いだ。他所でやれ。 67 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 13:52:46 ] 論理演算部分をインラインアセンブラ化するのに、 どうして「プロセッサのスケジューリング管理」なんて話が出てくるのか誰か教えて！ 68 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 16:26:53 ] 「プロセッサのスケジューリング管理」の意味はわかっているか？ 69 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 17:04:37 ] 大方タイムスライスと勘違いしているんだろうけど。 70 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 17:27:16 ] >>67 パイプラインでな、処理を円滑に進めるためには、命令の実行順序を適切に 並び替える必要があるんだ。命令実行順序の決定をスケジューリングという。 命令実行スケジューリングはふつうコンパイラが最適化の一環として施すが インラインアセンブラで記述した部分はそのままの順序で出力されて最適化 されないことが多い。 71 名前：デフォルトの名無しさん [2006/10/26(木) 23:04:23 ] ！ 72 名前：デフォルトの名無しさん [2006/10/30(月) 22:09:37 ] あげ 73 名前：デフォルトの名無しさん mailto:sage [2006/10/30(月) 22:39:25 ] テンプレにある ＞ハッカーのたのしみ は、アマゾンで評価が高いみたいですが 本当に読んで面白い本なんですか？ 74 名前：デフォルトの名無しさん mailto:sage [2006/10/30(月) 22:47:16 ] >>73 それはお前がビット演算を楽しめるかどうかによる。 75 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 03:09:00 ] >>73 もしもあなたが書き溜めたソースコードを持っているのなら… 76 名前：デフォルトの名無しさん mailto:age [2006/11/15(水) 19:13:21 ] ビット演算で絶対値を求めることってできますかね？ 条件分岐をしないで絶対値を求めたいのですが… 77 名前：デフォルトの名無しさん [2006/11/15(水) 20:26:02 ] >>76 このへん見てみたら？ www.thescripts.com/forum/thread212935.html 78 名前：デフォルトの名無しさん mailto:sage [2006/11/15(水) 21:53:55 ] int y=x>>31; return (x^y)-y; か。 今ならcmovのほうが速いだろうけど 79 名前：デフォルトの名無しさん mailto:sage [2006/11/15(水) 22:56:58 ] ふーむ… とりあえずリンク先を参考に試してみようと思います ありがとうございました 80 名前：デフォルトの名無しさん [2006/11/26(日) 15:29:11 ] age 81 名前：デフォルトの名無しさん [2006/12/02(土) 22:52:42 ] age 82 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 07:55:42 ] とにかく徹底的にｉｆ文使いたくないんだけど、 根本的に排除する方法ってないんですか？ こういう場合はできるよってのがあったらそれも知りたいです。 もうビット演算のこと以外考えたくないんです。 83 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 08:40:06 ] >>82 論理回路にｉｆ演算器はない。 84 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 08:40:31 ] if(a){ 　x; } else { 　y; } ⇒ switch(a){ default: 　x; 　break; case 0: 　y; } 85 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 08:50:26 ] じゃあ僕は条件分岐と一生付き合わなきゃいけないんですか？ 一生、縁が切れないんですか？？ もう勘弁しいてほしいんです。 ソース読みにくいのってみんなｉｆ文の所為じゃないですか。 この絶望のまま生きていたくない。 並列計算がうまくいかないのだってきっと条件分岐のせいですよ。 諸悪の根源と思っていますよ、もう。 ところで、論理シフトとかってあれは論理演算が関係してるんですか？ 86 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 09:38:32 ] if(a>b){ 　x=c; } else { 　x=d; } x=(a>b)*c; x+=!(a>b)*d; こんな感じかな？ ビット演算じゃ無いけど 87 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 10:20:41 ] if(a){ 　x; } else { 　y; } ⇒ n_if(a){ 　x && a || y && !a; } 88 名前：デフォルトの名無しさん mailto:sage [2006/12/04(月) 17:34:01 ] 平凡にジャンプテーブル void f(); void g(); int hoge;   before: if (hoge != 0)   f(); else   g();   after: typedef (*func_t)(); func_t table[] = {f, g}; table[hoge != 0](); 89 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 mailto:sage [2006/12/04(月) 22:59:51 ] 関数コールのペナルティ＞＞＞分岐予測ミスのペナルティ d = a ? b : c; とかでも使えば？組み込みのCMOV命令に展開してくれたりするし SIMD系の命令セットは比較命令はマスク生成のことが多い 90 名前：デフォルトの名無しさん mailto:sage [2006/12/04(月) 23:03:57 ] P4だと、テーブル参照方式はペナルティが信じられんほど凄い。 命令20ぐらいをズラスラ書いたのより、テーブル参照1つの方が遅かったりする。 91 名前：デフォルトの名無しさん mailto:sage [2006/12/07(木) 00:04:36 ] 最近それ経験した。 switchで振り分けた方が遥かに速かったわ。恐るべし分岐予測。 92 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 mailto:sage [2006/12/07(木) 00:39:10 ] >>82はPS3かなんかの開発やらされてるゲームプログラマなんじゃね？ 93 名前：82 mailto:sage [2006/12/11(月) 04:57:32 ] もうジャンプするのも嫌になりました。 ｉｆ文なしのジャンプなしで何とかならないでしょうか？？ 94 名前：デフォルトの名無しさん mailto:sage [2006/12/11(月) 18:38:36 ] てきとーに制限つけてその条件内で考えさせたいだけでしょ。 95 名前：デフォルトの名無しさん [2006/12/18(月) 22:14:18 ] age 96 名前：デフォルトの名無しさん mailto:sage [2006/12/25(月) 20:04:45 ] sub a, b adc pc, a 97 名前：デフォルトの名無しさん [2006/12/30(土) 23:15:58 ] あげ 98 名前： 【大吉】 [2007/01/01(月) 00:23:58 ] あけまして、おめでとうごｚぁいます 99 名前：デフォルトの名無しさん mailto:sage [2007/01/01(月) 13:31:16 ] 要は皆さんパズル好きだと 100 名前：デフォルトの名無しさん mailto:sage [2007/01/03(水) 13:42:06 ] プログラミング自体が、言語変わってもパーツの組合せのパズルに過ぎない訳で。 101 名前：デフォルトの名無しさん mailto:sage [2007/01/03(水) 19:31:35 ] >>82 >根本的に排除する方法ってないんですか？ >こういう場合はできるよってのがあったらそれも知りたいです。 ビット演算以外の仕事は「引き受けない」 102 名前：デフォルトの名無しさん mailto:sage [2007/01/03(水) 23:21:49 ] >82 まずプロセッサから設計した方がいいんじゃないか 103 名前：デフォルトの名無しさん mailto:sage [2007/01/04(木) 00:46:05 ] >>93 cmp+jeの組み合わせがいやならsub+jneでどうだろうか。 104 名前：デフォルトの名無しさん [2007/01/06(土) 15:01:25 ] Cです int i;として iが0以外なら1を、iが0なら0を返すビット演算は i!=0以上にコンパクトにできるのでしょうか？ n = i!=0;と括弧つけてもやや読みづらいので。 (bool)iならば可読的なので喜んで使いたいのですが、Cなので残念ながら… 105 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 15:03:57 ] !!i なんてどう？ 106 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 21:00:27 ] typedef enum{false, true} bool; (bool)i 107 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 22:58:09 ] 問題は、Cではenum型にキャストした値がenum値に制限されるかどうかだね。 108 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 mailto:sage [2007/01/06(土) 23:02:40 ] めんどくさい #define TO_BOOL(x) ((x) != 0) 109 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 23:04:45 ] 阿呆なマクロを使うくらいなら>105でいいじゃん。 110 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 23:07:38 ] >>108 C、C++の最適化について語るスレ pc10.2ch.net/test/read.cgi/tech/1084676298/ 団子ちゃん、↑こっちのスレの結果はどうなったの？ やっぱり、団子ちゃんが適当なこと吹いてただけなの？ 111 名前：デフォルトの名無しさん mailto:sage [2007/01/07(日) 07:00:18 ] っつーかどうしても1にしたい状況ってそんなないだろ 0/!0で充分だから 112 名前：デフォルトの名無しさん mailto:sage [2007/01/07(日) 22:11:55 ] ビット演算でも高速化でもないな。 113 名前：デフォルトの名無しさん mailto:sage [2007/01/14(日) 00:16:55 ] #define BITTOENNZANN(dayo) ((dayo)!=0) これでビット演算だお^ω^ 114 名前：デフォルトの名無しさん mailto:sage [2007/01/18(木) 00:08:57 ] >>33 加算器ってこんな感じじゃない？(ちょっと冗長かも) int ADD(int x, int y, int c) { return (x | y | c) ? (((x & 1) ^ (y & 1) ^ (c & 1)) | (ADD(x >> 1, y >> 1, (( !(x & 1) & (y & 1) & (c & 1)) | ( (x & 1) & !(y & 1) & (c & 1)) | ( (x & 1) & (y & 1) & !(c & 1)) | ( (x & 1) & (y & 1) & (c & 1)))) << 1)) : 0; } 誰か減算器↓ 115 名前：デフォルトの名無しさん mailto:sage [2007/01/18(木) 00:48:41 ] int ADD_(int x,int y){return x?ADD_((x&y)<<1,x^y):y;} int ADD(int x,int y,int c){return ADD_((x&y)<<1|c,x^y);} int SUB(int x,int y,int c){return ADD(x,~y,c^1);} 116 名前：デフォルトの名無しさん mailto:sage [2007/01/18(木) 16:58:05 ] >>109 ! がオーバーロードされてたら、二回も呼ばれることになるぜ。 117 名前：デフォルトの名無しさん mailto:sage [2007/01/19(金) 01:20:26 ] オーバーロードまで考慮したら ! 二回より != の方が遅いことも 十分ありえるけどな。 118 名前：デフォルトの名無しさん [2007/01/19(金) 14:36:23 ] 64bitのビットを数えるのは外出？ 119 名前：デフォルトの名無しさん mailto:sage [2007/01/19(金) 18:41:42 ] >>118 ビットを数えるってのがよくあるpop関数のことなら死ぬほど既出。 120 名前：デフォルトの名無しさん [2007/01/23(火) 07:38:25 ] あげ 121 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 10:19:53 ] レス４は絶対ここの住民だろ笑 pc10.2ch.net/test/read.cgi/tech/1169104637/l50 122 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 23:52:21 ] >>121 こいつのせいでビット操作のスレになってるじゃないか 123 名前：デフォルトの名無しさん mailto:sage [2007/01/29(月) 12:22:02 ] ビット演算でbranch freeなmagic incrementは可能かね？ 124 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 18:20:58 ] Bit Twiddling Hacks ttp://graphics.stanford.edu/~seander/bithacks.html こんなサイトが（英語だけど） テンプレに入れる？ 125 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 21:33:10 ] 入れるのはいいけど、それまで続くんか? 126 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 22:46:32 ] コンパイル時には>>124をテンプレとしてオーバーライドします。 127 名前：デフォルトの名無しさん [2007/02/13(火) 07:43:07 ] もうこのスレも息切れみたいだね。 128 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 23:14:23 ] だいたいビット演算ごときでときめいちゃうのは厨房までだろw 煽りぬきで 129 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 23:51:38 ] ていうか、パズルみたいなもんだろ。 さすがに、ネタ切れにて閉店でいいと思うよ。

---

---

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

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