1read 100read
2012年4月プログラム163: 【関数化】ビット演算 0x03 (880)
TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▼
【コボル】COBOL不要論【ただのDSLだよね?】 (331)
【SICP】計算機プログラムの構造と解釈 Part3 (332)
【入門】Common Lisp その9【質問よろず】 (211)
【node.js】サーバサイドjavascript【Rhino】 (717)
[Java]JBuilder5[Java] (775)
EAを語るスレ (227)
【関数化】ビット演算 0x03
1 :08/11/08 〜 最終レス :12/04/20 前スレ 【高速化】ビット演算 0x02 http://pc11.2ch.net/test/read.cgi/tech/1158367586/ 過去スレ 0x01. http://pc8.2ch.net/test/read.cgi/tech/1123918075/ 関連スレ アセンブラ… (゜□゜) ↑アッー!↓ http://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
2 : Intel系を前提として、 bitの逆転ってどんなコード組んだら一番速い? int rev(int n){n=(n<<16)|(n>>16 ); n=((n&0x00ff00ff)<<8)|((n&0xff00ff00)>>8 ); n=((n&0x0f0f0f0f)<<4)|((n&0xf0f0f0f0)>>4 ); n=((n&0x33333333)<<2)|((n&0xcccccccc)>>2 ); return((n&0x55555555)<<1)|((n&0xaaaaaaaa)>>1 );} より速いのがありそうな気がしてならない
3 : Intelはともかく、テーブル作ればいいんじゃない? 8ビット分のテーブルがあるとして return table[ n & 0xff ] << 24 | table [ (n >> 8) & 0xff ] << 16 | table [ (n >> 16) & 0xff ] << 8 | table [ (n >> 24) & 0xff ] ;
4 : >>2 とりあえず命令の並列度を高めてみた。 unsigned rev(unsigned n){ n = (n<<24) |(n<<8&0x00FF0000) | (n>>8 &0x0000FF00) |(n >> 24); n = (n<<6&0xC0C0C0C0) | (n<<2&0x30303030) | (n>>2 &0x0C0C0C0C) | (n>>6 &0x03030303); n = (n<<1&0xAAAAAAAA) | (n>>1 &0x55555555); return n; }
5 : 整数演算だけで高速に平方根を近似したいんだけど、どうすればいい?
6 : 良く知られてるあのやり方しか思いつかん。
7 : ああ、あれね。
8 : 将棋の盤面をビットボードにしたいんだけど、具体的にどうやったらいいの?
9 : 128bit変数のうち、81bitを使う
10 : 駒の識別に4bit程必要では?
11 : 駒のあるbit、先手のbit、成っているbit、あと歩、香、桂、銀、金、角、飛、王、のそれぞれが81bit有ればいいのでは?>ビットボード 斜めビットボードもありか? 持ち駒は、どう表現すんのかわかんね。
12 : 持ち駒は駒ごとに持ち駒数を表す配列 or 32ビットにパックした整数で十分だろ ビットボードにする必要はない
13 : if((hr == DIERR_INPUTLOST) || (hr == DIERR_NOTACQUIRED)) この文はもっと縮まないですか?
14 : >>2 Intelを前提にするならなぜ_bswap()を使わない
15 : if(hr == DIERR_INPUTLOST || hr == DIERR_NOTACQUIRED)
16 : 更に6バイト縮んだぜ if(hr==DIERR_INPUTLOST||hr==DIERR_NOTACQUIRED)
17 : if(hr == (DIERR_INPUTLOST || DIERR_NOTACQUIRED))
18 : >>4 32ビット即値を命令レベルでサポートするのってx86くらいしかないんだよね 定数ロードのオーバーヘッドがかる。 PPCなんかだと16ビットずつならロードできるんだけど。
19 : >>17 MSに頼めよ 各エラーを表現するビットが独立してるならこれでいけるんだけどな if(hr & (DIERR_INPUTLOST | DIERR_NOTACQUIRED))
20 : hrを1回だけにするなら、 switch(hr) { case DIERR_INPUTLOST: case DIERR_NOTACQUIRED: } だが、ifで書くのより格段に長くなるのと、DIERR_... が整数のときしか 使えない。
21 : いっそマクロでもインライン関数でも作れよ #define EQUAL_OR2(X, N1, N2) (((X) == (N1)) || ((X) == (N2)))
22 : >>18 組込みなら幾らでもあるぞ 有名どころでH8とかTLCS900とか
23 : 保守あげ
24 : template <typename charT> static inline charT xorcmp(const charT *s, charT d0, charT d1) { return (s[0]^d0) | (s[1]^d1); } template <typename charT> static inline charT xorcmp(const charT *s, charT d0, charT d1, charT d2) { return (s[0]^d0) | (s[1]^d1) | (s[2]^d2); } template <typename charT> static inline charT xorcmp(const charT *s, charT d0, charT d1, charT d2, charT d3) { return (s[0]^d0) | (s[1]^d1) | (s[2]^d2) | (s[3]^d3); } template <typename charT> static inline charT xorcmp2(const charT *s, const charT *d) { return xorcmp(s, d[0], d[1]); } template <typename charT> static inline charT xorcmp3(const charT *s, const charT *d) { return xorcmp(s, d[0], d[1], d[2]); } template <typename charT> static inline charT xorcmp4(const charT *s, const charT *d) { return xorcmp(s, d[0], d[1], d[2], d[3]); }
25 : template <typename intT> struct Flags { intT value; intT get(intT mask) const { return value & mask; } void set(intT mask) { value |= mask; } void reset(intT mask) { value &= ~mask; } void assign(intT mask, intT/*bool*/ cond) { cond = -(cond != 0); value = (value | (mask & cond)) & (~mask | cond); } };
26 : 以下のような16進文字を値に変換する処理を書いているのですが、 もっと短くする方法がありましたら教えてください。 (引数のhには16進文字しか入ってきません) unsigned char ascii2hex(unsigned char h) { if (h <= '9') { h -= '0'; } else { if (h > 'F') { h -= 0x20; } h -= 'A' - 10; } return h; }
27 : 短くと言うのは、ソースの行数なのか実行文のサイズなのか? ソースなら unsigned char ascii2hex(unsigned char h) { return h - (h <= '9' ? '0' : (h <= 'F' ? 'A' - 10 : 'a' - 10)); } 実行文なら unsigned char ascii2hex(unsigned char h) { static const unsigned char *const t = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,10,11,12,13,14,15 }; return t[h]; }
28 : AVR用なので、コード、メモリサイズともに小さければ可です。 大きなテーブル使うとかは無理です。 すいません。
29 : ソースの文字数とバイナリに変換したサイズは違うと思うが? どうなの?
30 : バイナリ命令文とメモリの合計の最小値ですか
31 : 0-9の場合 A-Fの場合 それ以外 で分岐して値を返すのが最小とは思う。
32 : 0-9 A-Fしか入力無いとすると、A-Fは6bit目が1であることは利用できそう・ 分岐と配列なしで値を返せるとは思うが計算時間の方が掛かる。
33 : 小文字の英字は考慮外でいいのか?
34 : 文字コードはASCIIでええのん? それとも別?
35 : >>28 なら、>>26 もしくは >>27 の上側でいいと思う。 (今時のコンパイラなら、ほぼ似たようなコードを吐くはず。) それ以上を期待するなら、アセンブリコード出して手で最適化。 ただ、最適化する余地はそんなにないと思う。
36 : AVR 用のコンパイラでもそんなに賢いのかしらん?
37 : gccだよ>AVR
38 : なるほろ。そりゃ賢いわ。
39 : 16進文字以外が無くてASCII限定ならこんなもんじゃねーの。 static unsigned char table[] = {0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,10,11,12,13,14,15,}; return table[(h & ~0x20) - '0']; 速度無視すりゃこっちの方がコードサイズ短くなるかもな。 static char a[2]; a[0] = h; return strtol(a, NULL, 16);
40 : テーブルも分岐も使わないならこうかな。 h &= ~0x20; h -= (h > '9') * ('A'-('9'+1)); return h - '0'; 乗算があるけど7倍ならコンパイラがよろしくやってくれるだろ。
41 : 適当に命令セットを見ながら速そうに書いてみた。 とはいえAVRは使ったこと無いからどうすれば速いかよく分からんけど。 unsigned char d; h &= 0x1F; d = (h>>4 |h<<4);//swap 命令使ってほしいなっと d = d-1 & 9; h = h+d & 0xF; return h;
42 : 除算が素直に可能ならこれでいいんだがな・・・。 return (h & ~48) % 55;
43 : あー事前にマスクしなければ1命令減らせた。 unsigned char d = (h >> 4 | h << 4); d = (d&1)-1 & 9; h = h+d & 0xF; >>42 除算がサポートされてても速度が微妙じゃね? でも格好良いなそれ。
44 : 要求はサイズだけだったし。 まあ除算できないから無理なんだけどね・・・。
45 : みなさんありがとうございました。 AVRには乗除算命令は一部のモデルにしかなく、 ない場合はコンパイラが適当に変換するようになっています。 >>40 は>>28 と全く同じコードサイズでした。 >>43 が1ワード減って、最も小さくなりました。 >>39 は上記に比べて50バイト程増えました。 strtol等ライブラリ関数は一応用意されてますが、 リンクするとサイズがとんでもないことになるので使えません。 >>42 の割り算は、内部ルーチンが大きいため テーブルを使うのとと同程度でした。
46 : >>28 の出力コード 8a 33 cpi r24, 0x3A ; 58 28 f0 brcs .+10 87 34 cpi r24, 0x47 ; 71 08 f0 brcs .+2 80 52 subi r24, 0x20 ; 32 87 53 subi r24, 0x37 ; 55 08 95 ret 80 53 subi r24, 0x30 ; 48 08 95 ret >>40 の出力コード 8f 7d andi r24, 0xDF ; 223 8a 33 cpi r24, 0x3A ; 58 10 f4 brcc .+4 90 e0 ldi r25, 0x00 ; 0 01 c0 rjmp .+2 97 e0 ldi r25, 0x07 ; 7 80 53 subi r24, 0x30 ; 48 89 1b sub r24, r25 08 95 ret >>43 の出力コ−ド 98 2f mov r25, r24 82 95 swap r24 81 70 andi r24, 0x01 ; 1 81 50 subi r24, 0x01 ; 1 89 70 andi r24, 0x09 ; 9 89 0f add r24, r25 8f 70 andi r24, 0x0F ; 15 08 95 ret きちんとスワップされました
47 : unsigned char d = h + 0xC0; unsigned char e = (d << 4 | d >> 4); return (9 & ~e) + (h & 15); これでどうだ?
48 : >>47 13ワードになってしましました。 28 2f mov r18, r24 20 54 subi r18, 0x40 ; 64 92 2f mov r25, r18 92 95 swap r25 9f 70 andi r25, 0x0F ; 15 22 95 swap r18 20 7f andi r18, 0xF0 ; 240 92 2b or r25, r18 90 95 com r25 99 70 andi r25, 0x09 ; 9 8f 70 andi r24, 0x0F ; 15 89 0f add r24, r25 08 95 ret
49 : ああ、これはひどいな・・・。
50 : もう無理ぽ。 eori さえあれば・・・。
51 : >>40 は被乗数が比較の0または1だから、 乗算自体なくなって0か7になるのか。 かしこいな。
52 : ていうか、この方が短くなるんじゃないか? if (h > '9') h -= 7; return h & 0xF; これを分岐無しにするともっと長くなりそうだが。 int n = (h > '9'); h += n; n <<= 3; h -= n; return h & 0xF;
53 : 分岐は気になるけど確かに減るね・・・。 cpi, brvs, subi, andi, ret の5命令でいけそうだ。 分岐なしの方は 1 ビットシフトしかないのでかなり長くなるはず。
54 : お世話になっております。 >>52 unsigned char ascii2hex(unsigned char h) { h &= ~0x20; if (h > '9') h -= 7; return h & 0xF; } として、6ワードになりました。 8f 7d andi r24, 0xDF ; 223 8a 33 cpi r24, 0x3A ; 58 08 f0 brcs .+2 87 50 subi r24, 0x07 ; 7 8f 70 andi r24, 0x0F ; 15 08 95 ret すばらしいです。
55 : h &= ~0x20; って必要?
56 : 要らないはず。 むかーし、Z80のプログラムを逆アセンブルしてたら 同じように16進ASCII2桁を数値に直すサブルーチンがあって 正確には覚えてないが push af a >>= 4 call half pop af half: 以下1桁分の計算 ret のような感じの、半再帰的な造りに感動した覚えがある。
57 : ん、2桁がAに入るわけないな。 まあとにかく、サブルーチン内のわずか先を一度callするやり方、ってことで。
58 : 俺はそこで、半桁分変換するのに DAAだかDADだかのBCD演算用の命令を使って、キャリーをうまく使って 分岐無しにしたような気がした。 どこか探せばあるかもね。
59 : h &= ~0x20はいらないですね。 5ワードの間違いでした。 >>56 試しに再帰で作ってみました。 unsigned char htoi(unsigned char h, unsigned char l); 2桁の16進文字を値にする関数をこのように宣言すると、 AVRの場合h はr24、 l はr22に入り、戻り値はr24になります。 Cから呼ばれる関数はr0,r18〜r27,r30,r31が破壊を気にせず使えます。 htoi: // 半再帰を使ってみる→ 11ワード mov r23, r24 // tmp <= h ldi r24, 0 // 戻り値を0へ初期化 rcall half // 相対コール(tmpの処理) swap r24 // ニブルを交換 mov r23, r22 // tmp <= l half: cpi r23, 0x3A ; 58 brcs .+2 subi r23, 0x07 ; 7 andi r23, 0x0F ; 15 or r24, r23 // 結果をr24へor ret
60 : htoi: // 普通にhlを処理した場合→11ワード cpi r24, 0x3A ; 58 brcs .+2 subi r24, 0x07 ; 7 cpi r22, 0x3A ; 58 brcs .+2 subi r22, 0x07 ; 7 andi r22, 0x0F ; 15 swap r24 andi r24, 0xF0 ; 240 or r24, r22 ret ワード数的には変わりませんでした。 movとかldiが無駄のような、必要なような。
61 : 分岐無しのほうを頭捻って1命令 短くしたつもり しかし分岐使うほうにまだ1命令負けてるのがなぁ unsigned char d; h = h + 0x41 & 0x9F; d = (h >> 4) | (h << 4); h = h - d & 0xF; return h;
62 : あげ
63 : あげ
64 : 符号なし整数値について、1となっている ビットのうちで、最下位のビット番号を 求める方法はありますか? 0x00000010 → 1 0x00100000 → 5 みたいな。 1のビット数は任意がいいですけど、 高速なら1ビット限定でもかまいません。
65 : シフトしながらカウントか、テーブル参照かな。 x に入ってるとすると、x ^ (x - 1) とか x & (x ^ (x - 1)) とか、 最下位の立ってるビット関係の値を取り出せる演算はあるけど、 ビット位置がうまく出てくる方法はないんじゃないかな。
66 : すべて、 テーブルにすればいいんじゃない? で終わり。
67 : 最下位ビットを抜き出して、それから 1 を引いてビットを数える、とか
68 : ハッカーのたのしみp90
69 : これとかhttp://www.nminoru.jp/~nminoru/programming/bitcount.html あと、CPUによっては命令を持っていることもある。x86のbsfみたいに。
70 : 1bit限定なら、前スレにあったテーブル参照での逆算が使えるかもね
71 : >>70 まぁx&-xで最下位ビット抽出してからやればなんとかなるかも int f(unsigned x){ x = x & -x; //x = (x * 0x0722BED3) >> 27; // 64ビット乗算がないならこっち x = (x * (0x0722BED3ULL<<5)) >> 32 & 31; return "\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"[x]; }
72 : >>69 は>>1 にあるんだがなぁ…
73 : >>71 なんでそんなのがわかるの? 天才ですか? 俺にはさっぱり・・・ returnで返しているのも何をしているのかわからん・・・ 何かお勧めの本はありますか? 体育大学卒で組込みやってるあんぽんたんですが、 本を読む努力はします。
74 : return "\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"[x]; こう書くから判りにくいんだよ。 こう書き直したらどうだ?w return x["\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"]; ギャグはさておき。 static const char table[] = { 0, 1, 11, 2, 8, 12, 28, 3, 9, 26, 13, 15, 29, 23, 4, 17, 31, 10, 7, 27, 25, 14, 22, 16, 30, 6, 24, 21, 5, 20, 19, 18 }; return table[x]; と同じだよ。
75 : "0123456789"[i%10] みたいな書き方、 自分で積極的に使う必要は無いが 読めるようになっておく必要はあると思うぞ。
76 : (i%10)["0123456789"]
77 : >>74 同じじゃないだろ char配列の終端に冗長な0が必要だ
78 : 同じだよ。
79 : >>73 組込み系か。 とりあえず「ハッカーのたのしみ」読んどけ。 あと、先輩や同業者が、計算機科学や情報系をバカにするかもしれないが、 話半分に聞いておくこと。
80 : >>73 文法周りはみんなが言ってくれたから計算回りだけ。 とりあえず前スレに分かりやすく書いてた人が居たから引用 前スレとの違いはp=5になった事ぐらい ここから引用 周期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だけ追加すればおk。 これだけだと順番がバラバラなので、テーブルと組み合わせる。 ↓この文字列リテラルの部分な。 "xxxxxxx"[(ハッシュ計算式)] すると、>>762-763 になりますよ、と。ビット溢れによるマスクなども組み合わせているが。
81 : >>78 同じじゃない 実行時のメモリが1バイト冗長だ
82 : 大抵は4バイト違ってくるだろうな。
83 : ところが大抵はページサイズで区切られるので、
84 : 同じだよ。
85 : 似たような感じでNLZはできないものか?
86 : NLZって?
87 : ニュージーランド
88 : Number of Leading Zero だろう。頭からゼロが何個続いてるか数える。 シフトしてって数えるとか、浮動小数点フォーマット変換でとかあるけどあまりスマートな方法がないよね。
89 : ないからわざわざそういう命令があったりするんだろうね。POWERとかだっけ? DSPとかだとビット並びを反転させる命令があるから、それと組み合わせるか。
90 : DSPだと、小数正規化用の命令が使える
91 : 体育会系で組込みはまだいるかもしれないが、 体育大学で組込みは希少だよな。日本全国探してもレア?
92 : レスくれたひと、どーも。 簡単に言うと>>67 なんですね。 ビットカウントのアレは知ってたんですが、 応用ができませんでした。
93 : あげ
94 : 1つかまたは0個のビットが立っている時に何番目のビットが立っているか。(上からでも下からでも、より速い方) お願いします。
95 : すぐ上にありました。すみません。
96 : 2進数や16進数の為の代数学とか無いのかな? 例えば32bit符号付き整数の絶対値を求める式を、定理を使って単純に変形するだけで、 andとかshiftとかmulみたいな単純な操作のみで構成された式に変形できる公理系とかそういうの x < 0 ? -x : x ={なんか、分岐の融合法則とかそういうの} (n ^ (n >> 31)) - (n >> 31) こういう等式変換の形でアルゴリズムを計算でできれば、 勘だけではできないときに色々と役立つんじゃないかなーと思うだけど つーか絶対ある筈なんだけど、俺はそういう噂すら知らないんで
97 : 合同式のことかと思ったが、もっと低レベルな話みたいだ。 ビット演算で絶対値を求めたいなら、2の補数を調べるといい。 2進数とか16進数を難しいと思ってるかもしれないが、他の人は誰も そう思ってないから。
98 : 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 : 右シフトが論理シフトだったら (n^-(n>>31 ))+(n>>31 ) かな? nが1の補数だったらどうなるんだろう
100read 1read
1read 100read
TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▲
J言語 (194)
MATLABプログラミング 質問箱 その3 (745)
ニートの俺が何か開発して食いつなぐスレ (797)
CPPUnitについて少し話そうかい (282)
【3DS】プチコンを語るスレ【DSi】 (597)
J#って何のためにあるの? (152)
--log9.info------------------
大槻真希を語るスレ (487)
【異邦人】久保田早紀を語ろうよ Part-4 (348)
坂本九について語れ! (594)
所ジョージ【あれは剥き出さない】 (757)
郷ひろみコンサートで歌って欲しい曲 (210)
古関裕而 (361)
【'60初期】カバーポップスを語ろう【日本語詞】 (650)
青春歌年鑑スレ (369)
元DEENのドラマー宇津本直紀 2 (336)
ふきのとうファンはおらんか 3 (672)
【17才】南沙織☆シンシア Part4【Ms.】 (691)
【OHH】大橋純子【BOY】 (350)
★フィンガー5★について語る 4 (124)
【A BOY】 大滝裕子 【ミリオンキッス】 (182)
ツイスト、世良公則、GUILD9を語れ3 (153)
(*  ̄▼ ̄ *) REVこと出口雅之(*  ̄▼ ̄ *) (849)
--log55.com------------------
【速報】菅官房長官「病院以外で死亡したコロナ感染者の数、今後把握していく」★2
【小池都知事】岡江久美子さん訃報に「決して人ごとではない」
【逆戻り】採用のプロが大予測「コロナ不況で、再び就職超氷河期がやってくるのか」
【自民】#三原じゅん子議員 「言っていい事と悪い事がある」…岡江久美子さんへの追悼ツイートに「あんた達が殺したんだよ」と中傷
【新型肺炎】WHOが草案文書を誤って公表→FTが「ギリアド、初期臨床試験が失敗」と報道→ギリアドの株下落
【新型コロナ】埼玉で自宅待機の50代男性死亡、県は「緊急性認められず」 ★4
リーマン以来の景気“悪化” 関係者「これ以下を知らない」 ★2
【新型コロナ】 都市部では人口の5%前後がすでに感染か・・・慶應義塾大学病院が 「市中感染の割合」を示唆