【関数化】ビット演算　0x03

1 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 20:32:00 ] 前スレ 【高速化】ビット演算　0x02 pc11.2ch.net/test/read.cgi/tech/1158367586/ 過去スレ 0x01. 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 96 名前：デフォルトの名無しさん [2009/03/20(金) 21:41:48 ] 2進数や16進数の為の代数学とか無いのかな？ 例えば32bit符号付き整数の絶対値を求める式を、定理を使って単純に変形するだけで、 andとかshiftとかmulみたいな単純な操作のみで構成された式に変形できる公理系とかそういうの x < 0 ? -x : x ={なんか、分岐の融合法則とかそういうの} (n ^ (n >> 31)) - (n >> 31) こういう等式変換の形でアルゴリズムを計算でできれば、 勘だけではできないときに色々と役立つんじゃないかなーと思うだけど つーか絶対ある筈なんだけど、俺はそういう噂すら知らないんで 97 名前：デフォルトの名無しさん mailto:sage [2009/03/20(金) 22:39:46 ] 合同式のことかと思ったが、もっと低レベルな話みたいだ。 ビット演算で絶対値を求めたいなら、２の補数を調べるといい。 2進数とか16進数を難しいと思ってるかもしれないが、他の人は誰も そう思ってないから。 98 名前：96 mailto:sage [2009/03/21(土) 00:45:51 ] n < 0 ? -n : n ={ 2の補数 : -n = ~n + 1 } n < 0 ? ~n+1 : n ={ n+0 = n } n < 0 ? ~n+1 : n+0 ={ --x = x, - 0 = 0 } n < 0 ? ~n-(-1) : n - 0 ={ n < 0 ? -1 : 0 <=> (n>>31) …(*} (n < 0 ? ~n : n) - (n >>31) ={ ~n = n^(-1), n^0 = n} (n < 0 ? n^(-1) : n^0) - (n >>31) ={ (*) } (n^(n>>31)) - (n>>31) ? : 演算子の単調性とか一部証明無しで決め打ちしてますができました 4番目の変形以降は知ってないとできませんね、恐らく常識なんでしょうけど >>96はその常識をまとめてあったり、こういう演算の性質について 群とかそういった代数学の概念での議論とかが載ってる文献などありませんかという意味でした 99 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:25:32 ] 右シフトが論理シフトだったら (n^-(n>>31))+(n>>31) かな？ nが1の補数だったらどうなるんだろう 100 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:27:42 ] nが1の補数だったら n<0?~n:n →n<0?n^-1:n^0 →n^(n>>31) かな。 101 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:38:12 ] 一般変形としてはこんな感じか。 x<y?z:w →x-y<0?z:w →z&(x-y>>31)|w&(~(x-y>>31)) x<=y?z:w →y<x?w:z x>y?z:w →y<x?z:w x>=y?z:w →x<y?w:z x=y?z:w →x-y=0?z:w →x-y<0&y-x<0?w:z →w&((x-y>>31)&(y-x>>31))|z&(~((x-y>>31)&(y-x>>31))) 102 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 04:39:43 ] x<0?y:y+z →y+(z&(x>>31)) 103 名前：デフォルトの名無しさん mailto:sage [2009/03/25(水) 05:50:18 ] 条件式使うならビットシフトまで落とす意味ない。 104 名前：デフォルトの名無しさん mailto:sage [2009/03/26(木) 18:53:33 ] 3項演算子を使うとx86だと式の計算以外に少なくとも3〜4クロック余計にかかるから、 他で4クロック以上重くなるというのでなければビットシフトまで落とす意味は十分にある。 105 名前：デフォルトの名無しさん mailto:sage [2009/03/26(木) 19:34:12 ] ジャンプはvだということを考慮すると2〜4クロックだぞ。 106 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/26(木) 19:37:54 ] CMOVって重たかったっけ？ y + ((x < 0)? 0 : z)に変形すれば mov eax, dword ptr [y] mov edx, dword ptr [x] xor ecx, ecx cmp eax, 0 cmovae ecx, dword ptr [z] add eax, ecx 107 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/26(木) 19:45:46 ] もしくはこうかｗ y + srl(x, 31) * z 108 名前：デフォルトの名無しさん mailto:sage [2009/03/26(木) 20:08:02 ] いや、それは逆に遅くならないか？ cmov系はフラグが確定するまで待機するから。 109 名前：108 mailto:sage [2009/03/26(木) 20:08:44 ] >>107 それはないｗ 110 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/03/26(木) 20:17:24 ] じゃあこれで movd xmm0, dword ptr [y] movd xmm1, dword ptr [x] pxor xmm2, xmm2 movd xmm4, dword ptr [z] pcmpgtd xmm2, xmm0 pand xmm2, xmm3 paddd xmm0, xmm2 movd eax, xmm0 どうみてもネタです。本当にありがとうございました。 111 名前：デフォルトの名無しさん [2009/04/18(土) 06:06:04 ] a 112 名前：デフォルトの名無しさん [2009/04/28(火) 19:50:17 ] ほしゅ 113 名前：ほしゅ [2009/05/15(金) 16:34:50 ] >>58 daa を使ったのは、 add a,0x90; daa; adc a,0x40; daa といった感じ。 dasを使ったのは cmp a,10; sbc a,0x69; das といった感じ。 das方式の 参考ページは www.df.lth.se/~john_e/gems/gem003a.html 114 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/15(金) 20:53:01 ] BCD演算ってそもそも遅くね？ 115 名前：デフォルトの名無しさん mailto:sage [2009/05/15(金) 22:00:47 ] あんまり変わらなかった 116 名前：デフォルトの名無しさん mailto:sage [2009/05/17(日) 23:45:35 ] これさ、○○与えると△△返すビット演算教えてください、みたいな感じで それに人間が答えてるけどさ、 一般的に反復深化の自動計算でビット演算はじき出すフリーソフトとかないんだっけ？ 117 名前：デフォルトの名無しさん mailto:sage [2009/05/17(日) 23:49:36 ] 反復深化？ 118 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/18(月) 00:15:38 ] サブネットマスクでも計算するの？ てかその手のは社内ツールであったな。 119 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/18(月) 00:17:55 ] tmkk氏がBerkeleyのSISってツールがあるって言ってたな 120 名前：デフォルトの名無しさん mailto:sage [2009/05/19(火) 02:55:16 ] 記憶が正しければ、今はBCD系はMMX系統の余った回路使って演算してる筈。 121 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/19(火) 03:53:50 ] ないない。 BCDって64ビットで無効命令だぜ？ Core 2あたりで除算回路そのものが高速化されてるあたり、IDIVと同じようなことやってんだろ 122 名前：デフォルトの名無しさん [2009/05/24(日) 21:17:29 ] あ 123 名前：デフォルトの名無しさん mailto:sage [2009/05/29(金) 06:15:50 ] //INVERSEはビットの左右を反転する処理 c = INVERSE(a); d = INVERSE(b); e = c + d; f = INVERSE(e); このようにaとbからfを求める処理があるとき INVERSEを無くしたり減らしたりはできるでしょうか 124 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/29(金) 07:25:25 ] キャリーの逆ができる回路があるならな。 大ヒント a + b = (a & b) + ((a ^ b) << 1) 125 名前：デフォルトの名無しさん mailto:sage [2009/05/31(日) 10:10:12 ] unsigned reverse_add(unsigned x, unsigned y) { do { unsigned c=x&y; x^=y; y=c>>1; } while(c!=0); return x; } 126 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/05/31(日) 10:47:55 ] ARMとかならアンロールしてプレディケートすれば上手い具合に分岐除去できるな 127 名前：デフォルトの名無しさん mailto:sage [2009/06/06(土) 18:55:12 ] >>124 a+b = (a^b) + ((a&b)<<1) の間違い？ 128 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/06/12(金) 01:37:04 ] >>127 そーでしたorz 129 名前：デフォルトの名無しさん mailto:sage [2009/06/20(土) 16:18:05 ] 952 名前：デフォルトの名無しさん 投稿日：2009/06/13(土) 22:16 C言語をはじめたばかりであまりわからないのですが、 ビットシフトはなんの役に立つのでしょうか？ 953 名前：デフォルトの名無しさん 投稿日：2009/06/13(土) 22:32 >>952 例えば、32bit符号無し整数の変数があり、 先頭から8bitごとにARGBを表しているとする。 (32bit画像の1画素) すると例えば、値を使用する前に2つを分離しなければならないから、 以下のようにする。 a = (x >> 24); r = 0xFF & (x >> 16); g = 0xFF & (x >> 8); b = 0xFF & x; 130 名前： ◆0uxK91AxII mailto:sage [2009/06/20(土) 17:41:04 ] >>129 a = *((unsigned char *)&c+3); 以下略。 131 名前：デフォルトの名無しさん mailto:sage [2009/06/21(日) 00:01:18 ] エンディアン依存のコードはお行儀悪いんじゃなかった？ 132 名前： ◆0uxK91AxII mailto:sage [2009/06/21(日) 08:04:17 ] ぐはぁ。 133 名前：デフォルトの名無しさん mailto:sage [2009/06/30(火) 01:49:31 ] >>123 本質的に難しいね 通常の加算の出力の MSB が入力の全ビットに依存するところを 加算命令が全部１命令でやってるわけで、 その左右反転の LSB が入力の全ビットに依存するような演算はバラすと結構かかる。 反転と再反転やりながら同時に加算もする方法を考えてみたけど 結局加算をバラすしかなくてだめだった。 (c & 0xAAAAAAAA)+(d & 0xAAAAAAAA) とかいろいろ考えたんだが。 逆演算の減算命令使うかなあと思ったけど、それも結局 「MSB が他のすべてのビットに影響を与える力」しかないし、 LSB に対する計算力が全くない。 結局やってることも補数の足し算だしね。 残るは特定係数の乗算？ それでもやっぱり基本的に LSB が上位ビットに無視されちゃう構造だし…。 なんか出力の LSB が入力の複数の上位ビットに依存するような便利な命令ないっすか？ 右シフトくらいしか思いつかない… 134 名前：133 mailto:sage [2009/06/30(火) 03:39:26 ] >>123 左右反転加算 ３による除算命令を使って何かできないか？ b = a/3 の演算は次のような演算とみてよい。 c = a[MSB]; //逆キャリー for(i=MSB-1;i<LSB;i--){ // 以下はいわゆる「筆算」による除算 b[i] = (c<<1 & a[i]) >= 3; c = (c<<1 & a[i]) % 3; } 一方加算 b = a0 + a1 は次の通り。 c = 0; for(i=LSB;i<MSB;i++){ b[i] = a0[i]^a1[i]^c; c = a0[i]&a1[i] | a0[i]&c | a1[i]&c; } 結構構造が似てる気がするのだが。 それでいて a/3 は LSB へ向かって結果が伝搬し、下位からの影響はない。 a/3 が１入力演算なので２入力演算な左右反転加算にはまだ遠いが… なにか道が開けるかもしれない。 135 名前：133 mailto:sage [2009/06/30(火) 03:42:52 ] >>134 訂正 b[i] = (c<<1 & a[i]) >= 3; ↓ b[i] = (c<<1 | a[i]) >= 3; 136 名前：デフォルトの名無しさん [2009/07/01(水) 13:27:12 ] >>123 難しい 無理な気がする 137 名前：デフォルトの名無しさん mailto:sage [2009/07/01(水) 20:33:21 ] おいおい、どうして>>125を無視する inverseせずに出来てるじゃないか 138 名前：デフォルトの名無しさん mailto:sage [2009/07/01(水) 20:50:37 ] ああ、ごめん 無視してないよ コードも実行してみたよ >>125よりいいのを考えてて思いつかなかった 139 名前：デフォルトの名無しさん mailto:sage [2009/07/02(木) 02:33:25 ] >>125 は面白くていいんだけど ちょっと最悪計算量が大きくない？ 0x00000001 = reverse_add(0x80000000, 0xFFFFFFFE) とか。 64ビットとかだったら64回くらいループしそうだし。 140 名前：デフォルトの名無しさん [2009/07/05(日) 21:53:38 ] >>116 そんなソフトあるんか・・・ 世界は広いな 141 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 18:55:03 ] 60で割った余りが0かどうか調べるにはどうすればいい？ 142 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 19:20:07 ] 60で引いていって60以下になったらそれが答えです 143 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 19:54:13 ] 以下じゃなくて未満ですた 144 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 20:01:13 ] if(0 == (n + 4) >> 6) { } 145 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 20:58:51 ] >>144 nを60にしても1なんですけどー 146 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 03:43:18 ] >>141 if( (n%60) ) { ０じゃないほう } else { ０のほう } ％は言語によって MOD とかもある。 147 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 04:08:05 ] え、マジで言ってる？ このスレの住人にも不可能なの？ 148 名前：,,・´∀｀・,,）っ-○○○ mailto:sage [2009/07/07(火) 20:47:14 ] 分岐のオーバーヘッドは高くないと仮定して、除算の平均回数を減らすほうがいいだろ if ((n & 3) || (n % 60)) 149 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 00:49:59 ] 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 の時だけ割り算か。1/4になったね。 4の倍数に注目したらもうちょっとなんとかならない？ 150 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 00:52:29 ] >>148 if(n & 3) return 0; x=((n>>2)*0x01111111)>>12; return !x || x==0xf; まあ掛け算で桁あふれのない n<16444 どまりだけどね。 151 名前：150 mailto:sage [2009/07/08(水) 01:14:43 ] x=(((n>>2)*0x01111111)>>12 & 0xf); & 0xf を忘れてた 152 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 02:54:49 ] すげー乗算になってさっぱり判らん 153 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 03:00:32 ] 最近このスレを読み始めた新参だが、気になったので倍数判定法の作り方を探してみたらニコニコがひかっかった。 ttp://www.nicovideo.jp/watch/sm5910890 ニコ動も馬鹿に出来んな・・・これをベースに展開してみた。 const unsigned int m18=(1<<18)-1; const unsigned int m10=(1<<10)-1; const unsigned int m6=(1<<6)-1; n=((n>>18)<<2)+(n&m18); n=((n>>10)<<2)+(n&m10); n=((n>>6)<<2)+(n&m6); int cal_res=((n)!=(0xff&("\xF0\xB4\x78\x3C"[((n>>2)&3)+4-((((n+0xff))&0x100)>>6)])))?0:1; //int cal_res=((n)!=(0xff&("\x00\x00\x00\x00\xF0\xB4\x78\x3C"[(n>>2)&7])))?0:1; //またはswitchやif-elseなど パイプラインが浅いCPUや乗除命令をサポートするCPUでは微妙かもな。 まだ最適化できる気がするが飽きた。 154 名前：153 mailto:sage [2009/07/08(水) 03:19:13 ] エラーで>>150の投稿に気づかなかった・・・ まぁこっちもビット数の制限がゆるいって利点はあるか >>150-151 定数での乗算を加算とビットシフトで置き換える操作はコンパイラ任せってことでしょうか 155 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 03:09:01 ] 8bit値を10進文字列に変換するこんな感じの関数を作ったのですが、 もっと小さくならないでしょうか？ 8bitのマイコン(AVR)用なので、大きなテーブルを使ったり 除算したりは無しでお願いします。掛け算は可です。 関数の戻りは、関数で入れた文字列の次のポインタを返してますが、 最後にヌル文字を入れたり1〜3の値を返すなど、次の位置が判れば 変更してもいいです。 char *itoa_next(unsigned char n, char *buf) { uint8_t c, len; if (n >= 100) { n -= 100; c = '1'; if (n >= 100) { n -= 100; c++; } *buf++ = c; len = 1; } else { len = 0; } for (c = 0; n >= 10 && c < 9; c++, n-=10) { } if (c || len) { *buf++ = c + '0'; } *buf++ = n + '0'; return buf; } 156 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 03:40:25 ] sprintf(buf,"%d",(int)n) を実装したいわけね。 小さくしたいなら、百の位からforループで回すべき。早くしたいなら、百の位を処理した後の forループは1，2回しか回らないのだから、ifのがいい。bufの頭は呼び出し側で知っている のだから、そこを返すのはムダだと思う。呼び出し側で役に立つ情報：文字列長を返すとか、 末尾nullをつけてｃ標準の文字列にしておいたほうがいい。 157 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 09:59:43 ] 俺が使ってのはこんなの。 char *itoa_next(unsigned char n, char * const buf) {  unsigned char * p = buf;  const unsigned char dec_columns[3] = {100,10,1};  const int tbllen = sizeof(dec_columns)/sizeof(dec_columns[0]);  int col;  /*不要桁スキップ*/  for(col=0;col<tbllen-1;col++){   if(n>=dec_columns[col])    break;  }  /*存在する桁から出力開始*/  for(;col<tbllen-1;col++){   const unsigned char column = dec_columns[col];   *p = 0x30;   while(n>=column){    (*p)++;    n-=column;   }   p++;  }  *p++ = n | 0x30;  return p; } 158 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 21:50:37 ] それだと他のbitにする場合もcolumnsや型を調整するだけで楽ですね。 159 名前：デフォルトの名無しさん mailto:sage [2009/07/11(土) 17:59:06 ] 今更だけど x86でeaxにn>>2が入っているとして (n>>2)*0x01111111 をちょっと手動で最適化してみてるんだけど、誰か8クロック未満になった人居る？ 160 名前：デフォルトの名無しさん mailto:sage [2009/07/12(日) 01:22:15 ] >>159 クロック計測はもうムリゲじゃ・・・？ 161 名前：154 mailto:sage [2009/07/12(日) 01:47:25 ] >>159 >>150-151の部分を最適化してるんだよな？ n>>=2; x=(n+(n<<4)); n=(n<<24)+(x<<16)+(x<<8)+x; x=(n>>12 & 0xf); 自分はこれが精一杯で、命令数調べるのが面倒だったからコンパイルしたら吹いたｗｗｗ 最適化切るとregister指定に関係なくスタック使うわ、最適化すると乗算命令に戻るわｗｗ 乗算の展開は乗除命令を持たないCPUでないとあんまり意味が無いって示唆なのかね？ >>154で加算とビットシフトで置き換えって書きましたが、逆効果かもしれませんゴメンナサイ。 162 名前：154 mailto:sage [2009/07/12(日) 02:36:34 ] 自分で書いたほう、ここが限界か・・・？ const unsigned int m18=(1<<18)-1; const unsigned int m10=(1<<10)-1; const unsigned int m6=(1<<6)-1; n=((n>>18)<<2)+(n&m18); n=((n>>10)<<2)+(n&m10); n=((n>>6)<<2)+(n&m6); n=((n>>6)<<2)+(n&m6); return ((((n^0x3C)+0xFF)^(n+0xFF))&0x100)?1:0; 163 名前：デフォルトの名無しさん [2009/07/12(日) 15:41:36 ] ビット演算は面白いし頭の体操になるし高速化することも多いけど 可読性は馬鹿みたいに低下するよね。 ビット演算を使うことで可読性があがって保守性が高まるいい例ってあるかな。 164 名前：デフォルトの名無しさん mailto:sage [2009/07/12(日) 15:59:57 ] 適切なコメントをつける。

---

---

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

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