- 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
- 2 名前：デフォルトの名無しさん [2008/11/08(土) 21:17:08 ]
- 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 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 21:42:00 ]
- Intelはともかく、テーブル作ればいいんじゃない？
8ビット分のテーブルがあるとして
return
table[ n & 0xff ] << 24
| table [ (n >> 8) & 0xff ] << 16
| table [ (n >> 16) & 0xff ] << 8
| table [ (n >> 24) & 0xff ] ;
- 4 名前：デフォルトの名無しさん mailto:sage [2008/11/08(土) 23:20:46 ]
- >>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 名前：デフォルトの名無しさん mailto:sage [2008/11/10(月) 21:12:23 ]
- 整数演算だけで高速に平方根を近似したいんだけど、どうすればいい？
- 6 名前：デフォルトの名無しさん mailto:sage [2008/11/10(月) 22:13:25 ]
- 良く知られてるあのやり方しか思いつかん。
- 7 名前：デフォルトの名無しさん mailto:sage [2008/11/11(火) 01:29:17 ]
- ああ、あれね。
- 8 名前：デフォルトの名無しさん [2008/11/11(火) 10:25:57 ]
- 将棋の盤面をビットボードにしたいんだけど、具体的にどうやったらいいの？
- 9 名前：デフォルトの名無しさん mailto:sage [2008/11/11(火) 13:33:27 ]
- 128bit変数のうち、81bitを使う
- 10 名前：デフォルトの名無しさん mailto:sage [2008/11/11(火) 19:48:41 ]
- 駒の識別に4bit程必要では？
- 11 名前：デフォルトの名無しさん mailto:sage [2008/11/11(火) 20:25:26 ]
- 駒のあるbit、先手のbit、成っているbit、あと歩、香、桂、銀、金、角、飛、王、のそれぞれが81bit有ればいいのでは？＞ビットボード
斜めビットボードもありか？
持ち駒は、どう表現すんのかわかんね。
- 12 名前：デフォルトの名無しさん mailto:sage [2008/11/12(水) 16:56:20 ]
- 持ち駒は駒ごとに持ち駒数を表す配列 or 32ビットにパックした整数で十分だろ
ビットボードにする必要はない
- 13 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 21:33:03 ]
- if((hr == DIERR_INPUTLOST) || (hr == DIERR_NOTACQUIRED))
この文はもっと縮まないですか？
- 14 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2008/11/13(木) 21:46:15 ]
- >>2
Intelを前提にするならなぜ_bswap()を使わない
- 15 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 21:52:47 ]
- if(hr == DIERR_INPUTLOST || hr == DIERR_NOTACQUIRED)
- 16 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2008/11/13(木) 21:54:17 ]
- 更に6バイト縮んだぜ
if(hr==DIERR_INPUTLOST||hr==DIERR_NOTACQUIRED)
- 17 名前：って書けるようにならんもんか mailto:sage [2008/11/13(木) 22:04:50 ]
- if(hr == (DIERR_INPUTLOST || DIERR_NOTACQUIRED))
- 18 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2008/11/13(木) 22:07:35 ]
- >>4
32ビット即値を命令レベルでサポートするのってx86くらいしかないんだよね
定数ロードのオーバーヘッドがかる。
PPCなんかだと16ビットずつならロードできるんだけど。
- 19 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2008/11/13(木) 22:10:40 ]
- >>17
MSに頼めよ
各エラーを表現するビットが独立してるならこれでいけるんだけどな
if(hr & (DIERR_INPUTLOST | DIERR_NOTACQUIRED))
- 20 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 22:11:12 ]
- hrを1回だけにするなら、
switch(hr) {
case DIERR_INPUTLOST:
case DIERR_NOTACQUIRED:
}
だが、ifで書くのより格段に長くなるのと、DIERR_... が整数のときしか
使えない。
- 21 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2008/11/13(木) 22:22:48 ]
- いっそマクロでもインライン関数でも作れよ
#define EQUAL_OR2(X, N1, N2) (((X) == (N1)) || ((X) == (N2)))
- 22 名前：デフォルトの名無しさん [2008/11/14(金) 23:05:27 ]
- >>18
組込みなら幾らでもあるぞ
有名どころでH8とかTLCS900とか
- 23 名前：デフォルトの名無しさん [2008/12/08(月) 00:02:32 ]
- 保守あげ
- 24 名前：捕手 mailto:sage [2008/12/28(日) 20:16:06 ]
- 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 名前：もひとつ捕手 mailto:sage [2008/12/28(日) 20:28:34 ]
- 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 名前：デフォルトの名無しさん [2009/01/03(土) 15:46:49 ]
- 以下のような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 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 16:31:08 ]
- 短くと言うのは、ソースの行数なのか実行文のサイズなのか？
ソースなら
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 名前：デフォルトの名無しさん [2009/01/03(土) 18:10:41 ]
- AVR用なので、コード、メモリサイズともに小さければ可です。
大きなテーブル使うとかは無理です。
すいません。
- 29 名前：デフォルトの名無しさん [2009/01/03(土) 18:17:42 ]
- ソースの文字数とバイナリに変換したサイズは違うと思うが? どうなの?
- 30 名前：デフォルトの名無しさん [2009/01/03(土) 18:19:12 ]
- バイナリ命令文とメモリの合計の最小値ですか
- 31 名前：デフォルトの名無しさん [2009/01/03(土) 18:21:03 ]
- 0-9の場合 A-Fの場合 それ以外 で分岐して値を返すのが最小とは思う。
- 32 名前：デフォルトの名無しさん [2009/01/03(土) 18:30:37 ]
- 0-9 A-Fしか入力無いとすると、A-Fは6bit目が1であることは利用できそう・
分岐と配列なしで値を返せるとは思うが計算時間の方が掛かる。
- 33 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 18:32:33 ]
- 小文字の英字は考慮外でいいのか？
- 34 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 18:33:21 ]
- 文字コードはASCIIでええのん？
それとも別？
- 35 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 18:39:15 ]
- >>28
なら、>>26 もしくは >>27 の上側でいいと思う。
(今時のコンパイラなら、ほぼ似たようなコードを吐くはず。)
それ以上を期待するなら、アセンブリコード出して手で最適化。
ただ、最適化する余地はそんなにないと思う。
- 36 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 18:42:18 ]
- AVR 用のコンパイラでもそんなに賢いのかしらん？
- 37 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 18:55:24 ]
- gccだよ>AVR
- 38 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 18:58:55 ]
- なるほろ。そりゃ賢いわ。
- 39 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 20:59:05 ]
- 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 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 21:10:10 ]
- テーブルも分岐も使わないならこうかな。
h &= ~0x20;
h -= (h > '9') * ('A'-('9'+1));
return h - '0';
乗算があるけど7倍ならコンパイラがよろしくやってくれるだろ。
- 41 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 22:50:29 ]
- 適当に命令セットを見ながら速そうに書いてみた。
とはいえAVRは使ったこと無いからどうすれば速いかよく分からんけど。
unsigned char d;
h &= 0x1F;
d = (h>>4|h<<4);//swap 命令使ってほしいなっと
d = d-1 & 9;
h = h+d & 0xF;
return h;
- 42 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 22:58:53 ]
- 除算が素直に可能ならこれでいいんだがな・・・。
return (h & ~48) % 55;
- 43 名前：41 mailto:sage [2009/01/03(土) 23:26:34 ]
- あー事前にマスクしなければ1命令減らせた。
unsigned char d = (h >> 4 | h << 4);
d = (d&1)-1 & 9;
h = h+d & 0xF;
>>42
除算がサポートされてても速度が微妙じゃね？
でも格好良いなそれ。
- 44 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 23:29:00 ]
- 要求はサイズだけだったし。
まあ除算できないから無理なんだけどね・・・。
- 45 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 23:48:54 ]
- みなさんありがとうございました。
AVRには乗除算命令は一部のモデルにしかなく、
ない場合はコンパイラが適当に変換するようになっています。
>>40は>>28と全く同じコードサイズでした。
>>43が1ワード減って、最も小さくなりました。
>>39は上記に比べて50バイト程増えました。
strtol等ライブラリ関数は一応用意されてますが、
リンクするとサイズがとんでもないことになるので使えません。
>>42の割り算は、内部ルーチンが大きいため
テーブルを使うのとと同程度でした。
- 46 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 23:49:44 ]
- >>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 名前：デフォルトの名無しさん mailto:sage [2009/01/03(土) 23:59:04 ]
- unsigned char d = h + 0xC0;
unsigned char e = (d << 4 | d >> 4);
return (9 & ~e) + (h & 15);
これでどうだ？
- 48 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 00:05:24 ]
- >>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 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 00:11:07 ]
- ああ、これはひどいな・・・。
- 50 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 00:35:44 ]
- もう無理ぽ。
eori さえあれば・・・。
- 51 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 01:00:01 ]
- >>40は被乗数が比較の0または1だから、
乗算自体なくなって0か7になるのか。
かしこいな。
- 52 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 09:42:34 ]
- ていうか、この方が短くなるんじゃないか？
if (h > '9') h -= 7;
return h & 0xF;
これを分岐無しにするともっと長くなりそうだが。
int n = (h > '9');
h += n;
n <<= 3;
h -= n;
return h & 0xF;
- 53 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 12:41:25 ]
- 分岐は気になるけど確かに減るね・・・。
cpi, brvs, subi, andi, ret
の５命令でいけそうだ。
分岐なしの方は 1 ビットシフトしかないのでかなり長くなるはず。
- 54 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 21:44:08 ]
- お世話になっております。
>>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 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 22:50:41 ]
- h &= ~0x20; って必要？
- 56 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 23:43:33 ]
- 要らないはず。
むかーし、Z80のプログラムを逆アセンブルしてたら
同じように16進ASCII2桁を数値に直すサブルーチンがあって
正確には覚えてないが
push af
a >>= 4
call half
pop af
half:
以下1桁分の計算
ret
のような感じの、半再帰的な造りに感動した覚えがある。
- 57 名前：デフォルトの名無しさん mailto:sage [2009/01/04(日) 23:46:02 ]
- ん、2桁がAに入るわけないな。
まあとにかく、サブルーチン内のわずか先を一度callするやり方、ってことで。
- 58 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 00:56:37 ]
- 俺はそこで、半桁分変換するのに
DAAだかDADだかのBCD演算用の命令を使って、キャリーをうまく使って
分岐無しにしたような気がした。
どこか探せばあるかもね。
- 59 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 19:16:06 ]
- 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 名前：デフォルトの名無しさん mailto:sage [2009/01/05(月) 19:17:38 ]
- 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 名前：デフォルトの名無しさん mailto:sage [2009/01/06(火) 01:24:17 ]
- 分岐無しのほうを頭捻って1命令 短くしたつもり
しかし分岐使うほうにまだ1命令負けてるのがなぁ
unsigned char d;
h = h + 0x41 & 0x9F;
d = (h >> 4) | (h << 4);
h = h - d & 0xF;
return h;
- 62 名前：デフォルトの名無しさん [2009/01/27(火) 21:18:44 ]
- あげ
- 63 名前：デフォルトの名無しさん [2009/02/21(土) 23:38:22 ]
- あげ
- 64 名前：デフォルトの名無しさん [2009/02/26(木) 16:00:28 ]
- 符号なし整数値について、1となっている
ビットのうちで、最下位のビット番号を
求める方法はありますか？
0x00000010 → 1
0x00100000 → 5
みたいな。
1のビット数は任意がいいですけど、
高速なら1ビット限定でもかまいません。
- 65 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 16:22:20 ]
- シフトしながらカウントか、テーブル参照かな。
x に入ってるとすると、x ^ (x - 1) とか x & (x ^ (x - 1)) とか、
最下位の立ってるビット関係の値を取り出せる演算はあるけど、
ビット位置がうまく出てくる方法はないんじゃないかな。
- 66 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 16:32:15 ]
- すべて、 テーブルにすればいいんじゃない？ で終わり。
- 67 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 16:46:49 ]
- 最下位ビットを抜き出して、それから 1 を引いてビットを数える、とか
- 68 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 17:25:41 ]
- ハッカーのたのしみp90
- 69 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 20:58:20 ]
- これとかwww.nminoru.jp/~nminoru/programming/bitcount.html
あと、CPUによっては命令を持っていることもある。x86のbsfみたいに。
- 70 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 21:45:26 ]
- 1bit限定なら、前スレにあったテーブル参照での逆算が使えるかもね
- 71 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 21:47:50 ]
- >>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 名前：デフォルトの名無しさん mailto:sage [2009/02/26(木) 22:58:47 ]
- >>69は>>1にあるんだがなぁ…
- 73 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 00:03:32 ]
- ＞＞71
なんでそんなのがわかるの？
天才ですか？
俺にはさっぱり・・・
returnで返しているのも何をしているのかわからん・・・
何かお勧めの本はありますか？
体育大学卒で組込みやってるあんぽんたんですが、
本を読む努力はします。
- 74 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 00:33:06 ]
- 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 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 00:33:45 ]
- "0123456789"[i%10]
みたいな書き方、
自分で積極的に使う必要は無いが
読めるようになっておく必要はあると思うぞ。
- 76 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 07:28:19 ]
- (i%10)["0123456789"]
- 77 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 07:32:13 ]
- >>74
同じじゃないだろ
char配列の終端に冗長な0が必要だ
- 78 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 08:06:47 ]
- 同じだよ。
- 79 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 10:14:24 ]
- >>73
組込み系か。
とりあえず「ハッカーのたのしみ」読んどけ。
あと、先輩や同業者が、計算機科学や情報系をバカにするかもしれないが、
話半分に聞いておくこと。
- 80 名前：デフォルトの名無しさん mailto:sage [2009/02/27(金) 12:27:36 ]
- >>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だけ追加すればおｋ。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
↓この文字列リテラルの部分な。
"xxxxxxx"[(ハッシュ計算式)]
すると、>>762-763になりますよ、と。ビット溢れによるマスクなども組み合わせているが。
- 81 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 08:23:45 ]
- >>78
同じじゃない
実行時のメモリが1バイト冗長だ
- 82 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 08:37:37 ]
- 大抵は4バイト違ってくるだろうな。
- 83 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 08:42:16 ]
- ところが大抵はページサイズで区切られるので、
- 84 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 09:03:18 ]
- 同じだよ。
- 85 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 09:47:38 ]
- 似たような感じでNLZはできないものか？
- 86 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 10:08:47 ]
- NLZって？
- 87 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 10:13:31 ]
- ニュージーランド
- 88 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 13:51:09 ]
- Number of Leading Zero だろう。頭からゼロが何個続いてるか数える。
シフトしてって数えるとか、浮動小数点フォーマット変換でとかあるけどあまりスマートな方法がないよね。
- 89 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 14:14:26 ]
- ないからわざわざそういう命令があったりするんだろうね。POWERとかだっけ？
DSPとかだとビット並びを反転させる命令があるから、それと組み合わせるか。
- 90 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 16:03:40 ]
- DSPだと、小数正規化用の命令が使える
- 91 名前：デフォルトの名無しさん mailto:sage [2009/02/28(土) 16:42:35 ]
- 体育会系で組込みはまだいるかもしれないが、
体育大学で組込みは希少だよな。日本全国探してもレア？
- 92 名前：64 mailto:sage [2009/03/01(日) 21:54:40 ]
- レスくれたひと、どーも。
簡単に言うと>>67なんですね。
ビットカウントのアレは知ってたんですが、
応用ができませんでした。
- 93 名前：デフォルトの名無しさん [2009/03/08(日) 10:14:52 ]
- あげ
- 94 名前：デフォルトの名無しさん mailto:sage [2009/03/13(金) 05:58:26 ]
- 1つかまたは0個のビットが立っている時に何番目のビットが立っているか。(上からでも下からでも、より速い方)
お願いします。
- 95 名前：デフォルトの名無しさん mailto:sage [2009/03/13(金) 06:05:16 ]
- すぐ上にありました。すみません。
- 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)
かな。
|
 |
