08/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:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/11/10 21:12:23
整数演算だけで高速に平方根を近似したいんだけど、どうすればいい？
6:デフォルトの名無しさん
08/11/10 22:13:25
良く知られてるあのやり方しか思いつかん。
7:デフォルトの名無しさん
08/11/11 01:29:17
ああ、あれね。
8:デフォルトの名無しさん
08/11/11 10:25:57
将棋の盤面をビットボードにしたいんだけど、具体的にどうやったらいいの？
9:デフォルトの名無しさん
08/11/11 13:33:27
128bit変数のうち、81bitを使う
10:デフォルトの名無しさん
08/11/11 19:48:41
駒の識別に4bit程必要では？
11:デフォルトの名無しさん
08/11/11 20:25:26
駒のあるbit、先手のbit、成っているbit、あと歩、香、桂、銀、金、角、飛、王、のそれぞれが81bit有ればいいのでは？＞ビットボード
斜めビットボードもありか？
持ち駒は、どう表現すんのかわかんね。
12:デフォルトの名無しさん
08/11/12 16:56:20
持ち駒は駒ごとに持ち駒数を表す配列 or 32ビットにパックした整数で十分だろ
ビットボードにする必要はない
13:デフォルトの名無しさん
08/11/13 21:33:03
if((hr == DIERR_INPUTLOST) || (hr == DIERR_NOTACQUIRED))
この文はもっと縮まないですか？
14:,,・´∀｀・,,）っ-●◎○
08/11/13 21:46:15
>>2
Intelを前提にするならなぜ_bswap()を使わない
15:デフォルトの名無しさん
08/11/13 21:52:47
if(hr == DIERR_INPUTLOST || hr == DIERR_NOTACQUIRED)
16:,,・´∀｀・,,）っ-●◎○
08/11/13 21:54:17
更に6バイト縮んだぜ
if(hr==DIERR_INPUTLOST||hr==DIERR_NOTACQUIRED)
17:って書けるようにならんもんか
08/11/13 22:04:50
if(hr == (DIERR_INPUTLOST || DIERR_NOTACQUIRED))
18:,,・´∀｀・,,）っ-●◎○
08/11/13 22:07:35
>>4
32ビット即値を命令レベルでサポートするのってx86くらいしかないんだよね
定数ロードのオーバーヘッドがかる。
PPCなんかだと16ビットずつならロードできるんだけど。
19:,,・´∀｀・,,）っ-●◎○
08/11/13 22:10:40
>>17
MSに頼めよ
各エラーを表現するビットが独立してるならこれでいけるんだけどな
if(hr & (DIERR_INPUTLOST | DIERR_NOTACQUIRED))
20:デフォルトの名無しさん
08/11/13 22:11:12
hrを1回だけにするなら、
switch(hr) {
case DIERR_INPUTLOST:
case DIERR_NOTACQUIRED:
}
だが、ifで書くのより格段に長くなるのと、DIERR_... が整数のときしか
使えない。
21:,,・´∀｀・,,）っ-●◎○
08/11/13 22:22:48
いっそマクロでもインライン関数でも作れよ
#define EQUAL_OR2(X, N1, N2) (((X) == (N1)) || ((X) == (N2)))
22:デフォルトの名無しさん
08/11/14 23:05:27
>>18
組込みなら幾らでもあるぞ
有名どころでH8とかTLCS900とか
23:デフォルトの名無しさん
08/12/08 00:02:32
保守あげ
24:捕手
08/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:もひとつ捕手
08/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:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/03 18:10:41
AVR用なので、コード、メモリサイズともに小さければ可です。
大きなテーブル使うとかは無理です。
すいません。
29:デフォルトの名無しさん
09/01/03 18:17:42
ソースの文字数とバイナリに変換したサイズは違うと思うが? どうなの?
30:デフォルトの名無しさん
09/01/03 18:19:12
バイナリ命令文とメモリの合計の最小値ですか
31:デフォルトの名無しさん
09/01/03 18:21:03
0-9の場合 A-Fの場合 それ以外 で分岐して値を返すのが最小とは思う。
32:デフォルトの名無しさん
09/01/03 18:30:37
0-9 A-Fしか入力無いとすると、A-Fは6bit目が1であることは利用できそう・
分岐と配列なしで値を返せるとは思うが計算時間の方が掛かる。
33:デフォルトの名無しさん
09/01/03 18:32:33
小文字の英字は考慮外でいいのか？
34:デフォルトの名無しさん
09/01/03 18:33:21
文字コードはASCIIでええのん？
それとも別？
35:デフォルトの名無しさん
09/01/03 18:39:15
>>28
なら、>>26 もしくは >>27 の上側でいいと思う。
(今時のコンパイラなら、ほぼ似たようなコードを吐くはず。)
それ以上を期待するなら、アセンブリコード出して手で最適化。
ただ、最適化する余地はそんなにないと思う。
36:デフォルトの名無しさん
09/01/03 18:42:18
AVR 用のコンパイラでもそんなに賢いのかしらん？
37:デフォルトの名無しさん
09/01/03 18:55:24
gccだよ>AVR
38:デフォルトの名無しさん
09/01/03 18:58:55
なるほろ。そりゃ賢いわ。
39:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/03 21:10:10
テーブルも分岐も使わないならこうかな。
h &= ~0x20;
h -= (h > '9') * ('A'-('9'+1));
return h - '0';
乗算があるけど7倍ならコンパイラがよろしくやってくれるだろ。
41:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/03 22:58:53
除算が素直に可能ならこれでいいんだがな・・・。
return (h & ~48) % 55;
43:41
09/01/03 23:26:34
あー事前にマスクしなければ1命令減らせた。
unsigned char d = (h >> 4 | h << 4);
d = (d&1)-1 & 9;
h = h+d & 0xF;
>>42
除算がサポートされてても速度が微妙じゃね？
でも格好良いなそれ。
44:デフォルトの名無しさん
09/01/03 23:29:00
要求はサイズだけだったし。
まあ除算できないから無理なんだけどね・・・。
45:デフォルトの名無しさん
09/01/03 23:48:54
みなさんありがとうございました。
AVRには乗除算命令は一部のモデルにしかなく、
ない場合はコンパイラが適当に変換するようになっています。
>>40は>>28と全く同じコードサイズでした。
>>43が1ワード減って、最も小さくなりました。
>>39は上記に比べて50バイト程増えました。
strtol等ライブラリ関数は一応用意されてますが、
リンクするとサイズがとんでもないことになるので使えません。
>>42の割り算は、内部ルーチンが大きいため
テーブルを使うのとと同程度でした。
46:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/03 23:59:04
unsigned char d = h + 0xC0;
unsigned char e = (d << 4 | d >> 4);
return (9 & ~e) + (h & 15);
これでどうだ？
48:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/04 00:11:07
ああ、これはひどいな・・・。
50:デフォルトの名無しさん
09/01/04 00:35:44
もう無理ぽ。
eori さえあれば・・・。
51:デフォルトの名無しさん
09/01/04 01:00:01
>>40は被乗数が比較の0または1だから、
乗算自体なくなって0か7になるのか。
かしこいな。
52:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/04 12:41:25
分岐は気になるけど確かに減るね・・・。
cpi, brvs, subi, andi, ret
の５命令でいけそうだ。
分岐なしの方は 1 ビットシフトしかないのでかなり長くなるはず。
54:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/04 22:50:41
h &= ~0x20; って必要？
56:デフォルトの名無しさん
09/01/04 23:43:33
要らないはず。
むかーし、Z80のプログラムを逆アセンブルしてたら
同じように16進ASCII2桁を数値に直すサブルーチンがあって
正確には覚えてないが
push af
a >>= 4
call half
pop af
half:
以下1桁分の計算
ret
のような感じの、半再帰的な造りに感動した覚えがある。
57:デフォルトの名無しさん
09/01/04 23:46:02
ん、2桁がAに入るわけないな。
まあとにかく、サブルーチン内のわずか先を一度callするやり方、ってことで。
58:デフォルトの名無しさん
09/01/05 00:56:37
俺はそこで、半桁分変換するのに
DAAだかDADだかのBCD演算用の命令を使って、キャリーをうまく使って
分岐無しにしたような気がした。
どこか探せばあるかもね。
59:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/01/27 21:18:44
あげ
63:デフォルトの名無しさん
09/02/21 23:38:22
あげ
64:デフォルトの名無しさん
09/02/26 16:00:28
符号なし整数値について、1となっている
ビットのうちで、最下位のビット番号を
求める方法はありますか？
0x00000010 → 1
0x00100000 → 5
みたいな。
1のビット数は任意がいいですけど、
高速なら1ビット限定でもかまいません。
65:デフォルトの名無しさん
09/02/26 16:22:20
シフトしながらカウントか、テーブル参照かな。
x に入ってるとすると、x ^ (x - 1) とか x & (x ^ (x - 1)) とか、
最下位の立ってるビット関係の値を取り出せる演算はあるけど、
ビット位置がうまく出てくる方法はないんじゃないかな。
66:デフォルトの名無しさん
09/02/26 16:32:15
すべて、 テーブルにすればいいんじゃない？ で終わり。
67:デフォルトの名無しさん
09/02/26 16:46:49
最下位ビットを抜き出して、それから 1 を引いてビットを数える、とか
68:デフォルトの名無しさん
09/02/26 17:25:41
ハッカーのたのしみp90
69:デフォルトの名無しさん
09/02/26 20:58:20
これとかURLﾘﾝｸ(www.nminoru.jp)
あと、CPUによっては命令を持っていることもある。x86のbsfみたいに。
70:デフォルトの名無しさん
09/02/26 21:45:26
1bit限定なら、前スレにあったテーブル参照での逆算が使えるかもね
71:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/02/26 22:58:47
>>69は>>1にあるんだがなぁ…
73:デフォルトの名無しさん
09/02/27 00:03:32
＞＞71
なんでそんなのがわかるの？
天才ですか？
俺にはさっぱり・・・
returnで返しているのも何をしているのかわからん・・・
何かお勧めの本はありますか？
体育大学卒で組込みやってるあんぽんたんですが、
本を読む努力はします。
74:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/02/27 00:33:45
"0123456789"[i%10]
みたいな書き方、
自分で積極的に使う必要は無いが
読めるようになっておく必要はあると思うぞ。
76:デフォルトの名無しさん
09/02/27 07:28:19
(i%10)["0123456789"]
77:デフォルトの名無しさん
09/02/27 07:32:13
>>74
同じじゃないだろ
char配列の終端に冗長な0が必要だ
78:デフォルトの名無しさん
09/02/27 08:06:47
同じだよ。
79:デフォルトの名無しさん
09/02/27 10:14:24
>>73
組込み系か。
とりあえず「ハッカーのたのしみ」読んどけ。
あと、先輩や同業者が、計算機科学や情報系をバカにするかもしれないが、
話半分に聞いておくこと。
80:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/02/28 08:23:45
>>78
同じじゃない
実行時のメモリが1バイト冗長だ
82:デフォルトの名無しさん
09/02/28 08:37:37
大抵は4バイト違ってくるだろうな。
83:デフォルトの名無しさん
09/02/28 08:42:16
ところが大抵はページサイズで区切られるので、
84:デフォルトの名無しさん
09/02/28 09:03:18
同じだよ。
85:デフォルトの名無しさん
09/02/28 09:47:38
似たような感じでNLZはできないものか？
86:デフォルトの名無しさん
09/02/28 10:08:47
NLZって？
87:デフォルトの名無しさん
09/02/28 10:13:31
ニュージーランド
88:デフォルトの名無しさん
09/02/28 13:51:09
Number of Leading Zero だろう。頭からゼロが何個続いてるか数える。
シフトしてって数えるとか、浮動小数点フォーマット変換でとかあるけどあまりスマートな方法がないよね。
89:デフォルトの名無しさん
09/02/28 14:14:26
ないからわざわざそういう命令があったりするんだろうね。POWERとかだっけ？
DSPとかだとビット並びを反転させる命令があるから、それと組み合わせるか。
90:デフォルトの名無しさん
09/02/28 16:03:40
DSPだと、小数正規化用の命令が使える
91:デフォルトの名無しさん
09/02/28 16:42:35
体育会系で組込みはまだいるかもしれないが、
体育大学で組込みは希少だよな。日本全国探してもレア？
92:64
09/03/01 21:54:40
レスくれたひと、どーも。
簡単に言うと>>67なんですね。
ビットカウントのアレは知ってたんですが、
応用ができませんでした。
93:デフォルトの名無しさん
09/03/08 10:14:52
あげ
94:デフォルトの名無しさん
09/03/13 05:58:26
1つかまたは0個のビットが立っている時に何番目のビットが立っているか。(上からでも下からでも、より速い方)
お願いします。
95:デフォルトの名無しさん
09/03/13 06:05:16
すぐ上にありました。すみません。
96:デフォルトの名無しさん
09/03/20 21:41:48
2進数や16進数の為の代数学とか無いのかな？
例えば32bit符号付き整数の絶対値を求める式を、定理を使って単純に変形するだけで、
andとかshiftとかmulみたいな単純な操作のみで構成された式に変形できる公理系とかそういうの
x < 0 ? -x : x
={なんか、分岐の融合法則とかそういうの}
(n ^ (n >> 31)) - (n >> 31)
こういう等式変換の形でアルゴリズムを計算でできれば、
勘だけではできないときに色々と役立つんじゃないかなーと思うだけど
つーか絶対ある筈なんだけど、俺はそういう噂すら知らないんで
97:デフォルトの名無しさん
09/03/20 22:39:46
合同式のことかと思ったが、もっと低レベルな話みたいだ。
ビット演算で絶対値を求めたいなら、２の補数を調べるといい。
2進数とか16進数を難しいと思ってるかもしれないが、他の人は誰も
そう思ってないから。
98:96
09/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:デフォルトの名無しさん
09/03/25 04:25:32
右シフトが論理シフトだったら
(n^-(n>>31))+(n>>31)
かな？
nが1の補数だったらどうなるんだろう
100:デフォルトの名無しさん
09/03/25 04:27:42
nが1の補数だったら
n<0?~n:n
→n<0?n^-1:n^0
→n^(n>>31)
かな。
101:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/03/25 04:39:43
x<0?y:y+z
→y+(z&(x>>31))
103:デフォルトの名無しさん
09/03/25 05:50:18
条件式使うならビットシフトまで落とす意味ない。
104:デフォルトの名無しさん
09/03/26 18:53:33
3項演算子を使うとx86だと式の計算以外に少なくとも3～4クロック余計にかかるから、
他で4クロック以上重くなるというのでなければビットシフトまで落とす意味は十分にある。
105:デフォルトの名無しさん
09/03/26 19:34:12
ジャンプはvだということを考慮すると2～4クロックだぞ。
106:,,・´∀｀・,,）っ-○◎●
09/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:,,・´∀｀・,,）っ-○◎●
09/03/26 19:45:46
もしくはこうかｗ
y + srl(x, 31) * z
108:デフォルトの名無しさん
09/03/26 20:08:02
いや、それは逆に遅くならないか？
cmov系はフラグが確定するまで待機するから。
109:108
09/03/26 20:08:44
>>107
それはないｗ
110:,,・´∀｀・,,）っ-○◎●
09/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:デフォルトの名無しさん
09/04/18 06:06:04
a
112:デフォルトの名無しさん
09/04/28 19:50:17
ほしゅ
113:ほしゅ
09/05/15 16:34:50
>>58 daa を使ったのは、 add a,0x90; daa; adc a,0x40; daa といった感じ。 dasを使ったのは cmp a,10; sbc a,0x69; das といった感じ。 das方式の 参考ページは URLﾘﾝｸ(www.df.lth.se)
114:,,・´∀｀・,,）っ-○○○
09/05/15 20:53:01
BCD演算ってそもそも遅くね？
115:デフォルトの名無しさん
09/05/15 22:00:47
あんまり変わらなかった
116:デフォルトの名無しさん
09/05/17 23:45:35
これさ、○○与えると△△返すビット演算教えてください、みたいな感じで
それに人間が答えてるけどさ、
一般的に反復深化の自動計算でビット演算はじき出すフリーソフトとかないんだっけ？
117:デフォルトの名無しさん
09/05/17 23:49:36
反復深化？
118:,,・´∀｀・,,）っ-○○○
09/05/18 00:15:38
サブネットマスクでも計算するの？
てかその手のは社内ツールであったな。
119:,,・´∀｀・,,）っ-○○○
09/05/18 00:17:55
tmkk氏がBerkeleyのSISってツールがあるって言ってたな
120:デフォルトの名無しさん
09/05/19 02:55:16
記憶が正しければ、今はBCD系はMMX系統の余った回路使って演算してる筈。
121:,,・´∀｀・,,）っ-○○○
09/05/19 03:53:50
ないない。
BCDって64ビットで無効命令だぜ？
Core 2あたりで除算回路そのものが高速化されてるあたり、IDIVと同じようなことやってんだろ
122:デフォルトの名無しさん
09/05/24 21:17:29
あ
123:デフォルトの名無しさん
09/05/29 06:15:50
//INVERSEはビットの左右を反転する処理
c = INVERSE(a);
d = INVERSE(b);
e = c + d;
f = INVERSE(e);
このようにaとbからfを求める処理があるとき
INVERSEを無くしたり減らしたりはできるでしょうか
124:,,・´∀｀・,,）っ-○○○
09/05/29 07:25:25
キャリーの逆ができる回路があるならな。
大ヒント
a + b
= (a & b) + ((a ^ b) << 1)
125:デフォルトの名無しさん
09/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:,,・´∀｀・,,）っ-○○○
09/05/31 10:47:55
ARMとかならアンロールしてプレディケートすれば上手い具合に分岐除去できるな
127:デフォルトの名無しさん
09/06/06 18:55:12
>>124
a+b = (a^b) + ((a&b)<<1)
の間違い？
128:,,・´∀｀・,,）っ-○○○
09/06/12 01:37:04
>>127
そーでしたorz
129:デフォルトの名無しさん
09/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
09/06/20 17:41:04
>>129
a = *((unsigned char *)&c+3);
以下略。
131:デフォルトの名無しさん
09/06/21 00:01:18
エンディアン依存のコードはお行儀悪いんじゃなかった？
132: ◆0uxK91AxII
09/06/21 08:04:17
ぐはぁ。
133:デフォルトの名無しさん
09/06/30 01:49:31
>>123
本質的に難しいね
通常の加算の出力の MSB が入力の全ビットに依存するところを
加算命令が全部１命令でやってるわけで、
その左右反転の LSB が入力の全ビットに依存するような演算はバラすと結構かかる。
反転と再反転やりながら同時に加算もする方法を考えてみたけど
結局加算をバラすしかなくてだめだった。
(c & 0xAAAAAAAA)+(d & 0xAAAAAAAA) とかいろいろ考えたんだが。
逆演算の減算命令使うかなあと思ったけど、それも結局
「MSB が他のすべてのビットに影響を与える力」しかないし、
LSB に対する計算力が全くない。
結局やってることも補数の足し算だしね。
残るは特定係数の乗算？
それでもやっぱり基本的に LSB が上位ビットに無視されちゃう構造だし…。
なんか出力の LSB が入力の複数の上位ビットに依存するような便利な命令ないっすか？
右シフトくらいしか思いつかない…
134:133
09/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
09/06/30 03:42:52
>>134
訂正
b[i] = (c<<1 & a[i]) >= 3;
↓
b[i] = (c<<1 | a[i]) >= 3;
136:デフォルトの名無しさん
09/07/01 13:27:12
>>123
難しい
無理な気がする
137:デフォルトの名無しさん
09/07/01 20:33:21
おいおい、どうして>>125を無視する
inverseせずに出来てるじゃないか
138:デフォルトの名無しさん
09/07/01 20:50:37
ああ、ごめん
無視してないよ
コードも実行してみたよ
>>125よりいいのを考えてて思いつかなかった
139:デフォルトの名無しさん
09/07/02 02:33:25
>>125 は面白くていいんだけど
ちょっと最悪計算量が大きくない？
0x00000001 = reverse_add(0x80000000, 0xFFFFFFFE) とか。
64ビットとかだったら64回くらいループしそうだし。
140:デフォルトの名無しさん
09/07/05 21:53:38
>>116
そんなソフトあるんか・・・ 世界は広いな
141:デフォルトの名無しさん
09/07/06 18:55:03
60で割った余りが0かどうか調べるにはどうすればいい？
142:デフォルトの名無しさん
09/07/06 19:20:07
60で引いていって60以下になったらそれが答えです
143:デフォルトの名無しさん
09/07/06 19:54:13
以下じゃなくて未満ですた
144:デフォルトの名無しさん
09/07/06 20:01:13
if(0 == (n + 4) >> 6)
{
}
145:デフォルトの名無しさん
09/07/06 20:58:51
>>144
nを60にしても1なんですけどー
146:デフォルトの名無しさん
09/07/07 03:43:18
>>141 if( (n%60) ) { ０じゃないほう } else { ０のほう }
％は言語によって MOD とかもある。
147:デフォルトの名無しさん
09/07/07 04:08:05
え、マジで言ってる？
このスレの住人にも不可能なの？
148:,,・´∀｀・,,）っ-○○○
09/07/07 20:47:14
分岐のオーバーヘッドは高くないと仮定して、除算の平均回数を減らすほうがいいだろ
if ((n & 3) || (n % 60))
149:デフォルトの名無しさん
09/07/08 00:49:59
0 4 8 12 16 20 24 28 32 36 40 44 48 52 56
の時だけ割り算か。1/4になったね。
4の倍数に注目したらもうちょっとなんとかならない？
150:デフォルトの名無しさん
09/07/08 00:52:29
>>148
if(n & 3) return 0;
x=((n>>2)*0x01111111)>>12;
return !x || x==0xf;
まあ掛け算で桁あふれのない n<16444 どまりだけどね。
151:150
09/07/08 01:14:43
x=(((n>>2)*0x01111111)>>12 & 0xf);
& 0xf を忘れてた
152:デフォルトの名無しさん
09/07/08 02:54:49
すげー乗算になってさっぱり判らん
153:デフォルトの名無しさん
09/07/08 03:00:32
最近このスレを読み始めた新参だが、気になったので倍数判定法の作り方を探してみたらニコニコがひかっかった。
URLﾘﾝｸ(www.nicovideo.jp)
ニコ動も馬鹿に出来んな・・・これをベースに展開してみた。
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
09/07/08 03:19:13
エラーで>>150の投稿に気づかなかった・・・
まぁこっちもビット数の制限がゆるいって利点はあるか
>>150-151
定数での乗算を加算とビットシフトで置き換える操作はコンパイラ任せってことでしょうか
155:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/07/09 03:40:25
sprintf(buf,"%d",(int)n) を実装したいわけね。
小さくしたいなら、百の位からforループで回すべき。早くしたいなら、百の位を処理した後の
forループは1，2回しか回らないのだから、ifのがいい。bufの頭は呼び出し側で知っている
のだから、そこを返すのはムダだと思う。呼び出し側で役に立つ情報：文字列長を返すとか、
末尾nullをつけてｃ標準の文字列にしておいたほうがいい。
157:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/07/09 21:50:37
それだと他のbitにする場合もcolumnsや型を調整するだけで楽ですね。
159:デフォルトの名無しさん
09/07/11 17:59:06
今更だけど
x86でeaxにn>>2が入っているとして
(n>>2)*0x01111111
をちょっと手動で最適化してみてるんだけど、誰か8クロック未満になった人居る？
160:デフォルトの名無しさん
09/07/12 01:22:15
>>159
クロック計測はもうムリゲじゃ・・・？
161:154
09/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
09/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:デフォルトの名無しさん
09/07/12 15:41:36
ビット演算は面白いし頭の体操になるし高速化することも多いけど
可読性は馬鹿みたいに低下するよね。
ビット演算を使うことで可読性があがって保守性が高まるいい例ってあるかな。
164:デフォルトの名無しさん
09/07/12 15:59:57
適切なコメントをつける。