【関数化】ビット演算　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 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