5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :デフォルトの名無しさん:2008/11/08(土) 20:32:00
前スレ
【高速化】ビット演算 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 :デフォルトの名無しさん: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 :デフォルトの名無しさん: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 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2008/11/10(月) 21:12:23
整数演算だけで高速に平方根を近似したいんだけど、どうすればいい?

6 :デフォルトの名無しさん:2008/11/10(月) 22:13:25
良く知られてるあのやり方しか思いつかん。

7 :デフォルトの名無しさん:2008/11/11(火) 01:29:17
ああ、あれね。

8 :デフォルトの名無しさん:2008/11/11(火) 10:25:57
将棋の盤面をビットボードにしたいんだけど、具体的にどうやったらいいの?

9 :デフォルトの名無しさん:2008/11/11(火) 13:33:27
128bit変数のうち、81bitを使う

10 :デフォルトの名無しさん:2008/11/11(火) 19:48:41
駒の識別に4bit程必要では?

11 :デフォルトの名無しさん:2008/11/11(火) 20:25:26
駒のあるbit、先手のbit、成っているbit、あと歩、香、桂、銀、金、角、飛、王、のそれぞれが81bit有ればいいのでは?>ビットボード
斜めビットボードもありか?
持ち駒は、どう表現すんのかわかんね。

12 :デフォルトの名無しさん:2008/11/12(水) 16:56:20
持ち駒は駒ごとに持ち駒数を表す配列 or 32ビットにパックした整数で十分だろ
ビットボードにする必要はない

13 :デフォルトの名無しさん:2008/11/13(木) 21:33:03
if((hr == DIERR_INPUTLOST) || (hr == DIERR_NOTACQUIRED))

この文はもっと縮まないですか?

14 :,,・´∀`・,,)っ-●◎○:2008/11/13(木) 21:46:15
>>2
Intelを前提にするならなぜ_bswap()を使わない

15 :デフォルトの名無しさん:2008/11/13(木) 21:52:47
if(hr == DIERR_INPUTLOST || hr == DIERR_NOTACQUIRED)

16 :,,・´∀`・,,)っ-●◎○:2008/11/13(木) 21:54:17
更に6バイト縮んだぜ

if(hr==DIERR_INPUTLOST||hr==DIERR_NOTACQUIRED)

17 :って書けるようにならんもんか:2008/11/13(木) 22:04:50
if(hr == (DIERR_INPUTLOST || DIERR_NOTACQUIRED))

18 :,,・´∀`・,,)っ-●◎○:2008/11/13(木) 22:07:35
>>4
32ビット即値を命令レベルでサポートするのってx86くらいしかないんだよね
定数ロードのオーバーヘッドがかる。
PPCなんかだと16ビットずつならロードできるんだけど。


19 :,,・´∀`・,,)っ-●◎○:2008/11/13(木) 22:10:40
>>17
MSに頼めよ
各エラーを表現するビットが独立してるならこれでいけるんだけどな

if(hr & (DIERR_INPUTLOST | DIERR_NOTACQUIRED))



20 :デフォルトの名無しさん:2008/11/13(木) 22:11:12
hrを1回だけにするなら、
switch(hr) {
case DIERR_INPUTLOST:
case DIERR_NOTACQUIRED:
}
だが、ifで書くのより格段に長くなるのと、DIERR_... が整数のときしか
使えない。


21 :,,・´∀`・,,)っ-●◎○: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 :捕手: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 :もひとつ捕手: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 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/01/03(土) 18:32:33
小文字の英字は考慮外でいいのか?

34 :デフォルトの名無しさん:2009/01/03(土) 18:33:21
文字コードはASCIIでええのん?
それとも別?

35 :デフォルトの名無しさん:2009/01/03(土) 18:39:15
>>28
なら、>>26 もしくは >>27 の上側でいいと思う。
(今時のコンパイラなら、ほぼ似たようなコードを吐くはず。)
それ以上を期待するなら、アセンブリコード出して手で最適化。
ただ、最適化する余地はそんなにないと思う。

36 :デフォルトの名無しさん:2009/01/03(土) 18:42:18
AVR 用のコンパイラでもそんなに賢いのかしらん?

37 :デフォルトの名無しさん:2009/01/03(土) 18:55:24
gccだよ>AVR

38 :デフォルトの名無しさん:2009/01/03(土) 18:58:55
なるほろ。そりゃ賢いわ。

39 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/01/03(土) 21:10:10
テーブルも分岐も使わないならこうかな。
h &= ~0x20;
h -= (h > '9') * ('A'-('9'+1));
return h - '0';
乗算があるけど7倍ならコンパイラがよろしくやってくれるだろ。

41 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/01/03(土) 22:58:53
除算が素直に可能ならこれでいいんだがな・・・。

return (h & ~48) % 55;

43 :41: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 :デフォルトの名無しさん:2009/01/03(土) 23:29:00
要求はサイズだけだったし。
まあ除算できないから無理なんだけどね・・・。

45 :デフォルトの名無しさん:2009/01/03(土) 23:48:54
みなさんありがとうございました。
AVRには乗除算命令は一部のモデルにしかなく、
ない場合はコンパイラが適当に変換するようになっています。

>>40>>28と全く同じコードサイズでした。
>>43が1ワード減って、最も小さくなりました。

>>39は上記に比べて50バイト程増えました。
strtol等ライブラリ関数は一応用意されてますが、
リンクするとサイズがとんでもないことになるので使えません。

>>42の割り算は、内部ルーチンが大きいため
テーブルを使うのとと同程度でした。



46 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/01/03(土) 23:59:04
unsigned char d = h + 0xC0;
unsigned char e = (d << 4 | d >> 4);
return (9 & ~e) + (h & 15);

これでどうだ?

48 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/01/04(日) 00:11:07
ああ、これはひどいな・・・。

50 :デフォルトの名無しさん:2009/01/04(日) 00:35:44
もう無理ぽ。
eori さえあれば・・・。

51 :デフォルトの名無しさん:2009/01/04(日) 01:00:01
>>40は被乗数が比較の0または1だから、
乗算自体なくなって0か7になるのか。
かしこいな。

52 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/01/04(日) 12:41:25
分岐は気になるけど確かに減るね・・・。

cpi, brvs, subi, andi, ret

の5命令でいけそうだ。
分岐なしの方は 1 ビットシフトしかないのでかなり長くなるはず。

54 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/01/04(日) 22:50:41
h &= ~0x20; って必要?

56 :デフォルトの名無しさん:2009/01/04(日) 23:43:33
要らないはず。

むかーし、Z80のプログラムを逆アセンブルしてたら
同じように16進ASCII2桁を数値に直すサブルーチンがあって
正確には覚えてないが
 push af
 a >>= 4
 call half
 pop af
half:
 以下1桁分の計算
 ret
のような感じの、半再帰的な造りに感動した覚えがある。

57 :デフォルトの名無しさん:2009/01/04(日) 23:46:02
ん、2桁がAに入るわけないな。
まあとにかく、サブルーチン内のわずか先を一度callするやり方、ってことで。

58 :デフォルトの名無しさん:2009/01/05(月) 00:56:37
俺はそこで、半桁分変換するのに
DAAだかDADだかのBCD演算用の命令を使って、キャリーをうまく使って
分岐無しにしたような気がした。
どこか探せばあるかもね。


59 :デフォルトの名無しさん: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 :デフォルトの名無しさん: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 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/02/26(木) 16:22:20
シフトしながらカウントか、テーブル参照かな。

x に入ってるとすると、x ^ (x - 1) とか x & (x ^ (x - 1)) とか、
最下位の立ってるビット関係の値を取り出せる演算はあるけど、
ビット位置がうまく出てくる方法はないんじゃないかな。

66 :デフォルトの名無しさん:2009/02/26(木) 16:32:15
すべて、 テーブルにすればいいんじゃない?  で終わり。

67 :デフォルトの名無しさん:2009/02/26(木) 16:46:49
最下位ビットを抜き出して、それから 1 を引いてビットを数える、とか

68 :デフォルトの名無しさん:2009/02/26(木) 17:25:41
ハッカーのたのしみp90

69 :デフォルトの名無しさん:2009/02/26(木) 20:58:20
これとかhttp://www.nminoru.jp/~nminoru/programming/bitcount.html
あと、CPUによっては命令を持っていることもある。x86のbsfみたいに。

70 :デフォルトの名無しさん:2009/02/26(木) 21:45:26
1bit限定なら、前スレにあったテーブル参照での逆算が使えるかもね

71 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/02/26(木) 22:58:47
>>69>>1にあるんだがなぁ…

73 :デフォルトの名無しさん:2009/02/27(金) 00:03:32
>>71
なんでそんなのがわかるの?
天才ですか?

俺にはさっぱり・・・
returnで返しているのも何をしているのかわからん・・・
何かお勧めの本はありますか?

体育大学卒で組込みやってるあんぽんたんですが、
本を読む努力はします。

74 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/02/27(金) 00:33:45
"0123456789"[i%10]
みたいな書き方、
自分で積極的に使う必要は無いが
読めるようになっておく必要はあると思うぞ。

76 :デフォルトの名無しさん:2009/02/27(金) 07:28:19
(i%10)["0123456789"]

77 :デフォルトの名無しさん:2009/02/27(金) 07:32:13
>>74
同じじゃないだろ
char配列の終端に冗長な0が必要だ

78 :デフォルトの名無しさん:2009/02/27(金) 08:06:47
同じだよ。

79 :デフォルトの名無しさん:2009/02/27(金) 10:14:24
>>73
組込み系か。
とりあえず「ハッカーのたのしみ」読んどけ。
あと、先輩や同業者が、計算機科学や情報系をバカにするかもしれないが、
話半分に聞いておくこと。

80 :デフォルトの名無しさん: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だけ追加すればおk。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
↓この文字列リテラルの部分な。
"xxxxxxx"[(ハッシュ計算式)]
すると、>>762-763になりますよ、と。ビット溢れによるマスクなども組み合わせているが。

81 :デフォルトの名無しさん:2009/02/28(土) 08:23:45
>>78
同じじゃない
実行時のメモリが1バイト冗長だ

82 :デフォルトの名無しさん:2009/02/28(土) 08:37:37
大抵は4バイト違ってくるだろうな。

83 :デフォルトの名無しさん:2009/02/28(土) 08:42:16
ところが大抵はページサイズで区切られるので、

84 :デフォルトの名無しさん:2009/02/28(土) 09:03:18
同じだよ。

85 :デフォルトの名無しさん:2009/02/28(土) 09:47:38
似たような感じでNLZはできないものか?

86 :デフォルトの名無しさん:2009/02/28(土) 10:08:47
NLZって?

87 :デフォルトの名無しさん:2009/02/28(土) 10:13:31
ニュージーランド

88 :デフォルトの名無しさん:2009/02/28(土) 13:51:09
Number of Leading Zero だろう。頭からゼロが何個続いてるか数える。
シフトしてって数えるとか、浮動小数点フォーマット変換でとかあるけどあまりスマートな方法がないよね。

89 :デフォルトの名無しさん:2009/02/28(土) 14:14:26
ないからわざわざそういう命令があったりするんだろうね。POWERとかだっけ?

DSPとかだとビット並びを反転させる命令があるから、それと組み合わせるか。

90 :デフォルトの名無しさん:2009/02/28(土) 16:03:40
DSPだと、小数正規化用の命令が使える

91 :デフォルトの名無しさん:2009/02/28(土) 16:42:35
体育会系で組込みはまだいるかもしれないが、
体育大学で組込みは希少だよな。日本全国探してもレア?

92 :64:2009/03/01(日) 21:54:40
レスくれたひと、どーも。

簡単に言うと>>67なんですね。
ビットカウントのアレは知ってたんですが、
応用ができませんでした。


93 :デフォルトの名無しさん:2009/03/08(日) 10:14:52
あげ

94 :デフォルトの名無しさん:2009/03/13(金) 05:58:26
1つかまたは0個のビットが立っている時に何番目のビットが立っているか。(上からでも下からでも、より速い方)

お願いします。

95 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/03/20(金) 22:39:46
合同式のことかと思ったが、もっと低レベルな話みたいだ。
ビット演算で絶対値を求めたいなら、2の補数を調べるといい。
2進数とか16進数を難しいと思ってるかもしれないが、他の人は誰も
そう思ってないから。

98 :96: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 :デフォルトの名無しさん:2009/03/25(水) 04:25:32
右シフトが論理シフトだったら
(n^-(n>>31))+(n>>31)
かな?

nが1の補数だったらどうなるんだろう

100 :デフォルトの名無しさん:2009/03/25(水) 04:27:42
nが1の補数だったら
n<0?~n:n
→n<0?n^-1:n^0
→n^(n>>31)
かな。

101 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/03/25(水) 04:39:43
x<0?y:y+z
→y+(z&(x>>31))

103 :デフォルトの名無しさん:2009/03/25(水) 05:50:18
条件式使うならビットシフトまで落とす意味ない。

104 :デフォルトの名無しさん:2009/03/26(木) 18:53:33
3項演算子を使うとx86だと式の計算以外に少なくとも3〜4クロック余計にかかるから、
他で4クロック以上重くなるというのでなければビットシフトまで落とす意味は十分にある。

105 :デフォルトの名無しさん:2009/03/26(木) 19:34:12
ジャンプはvだということを考慮すると2〜4クロックだぞ。

106 :,,・´∀`・,,)っ-○◎●: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 :,,・´∀`・,,)っ-○◎●:2009/03/26(木) 19:45:46
もしくはこうかw

y + srl(x, 31) * z

108 :デフォルトの名無しさん:2009/03/26(木) 20:08:02
いや、それは逆に遅くならないか?
cmov系はフラグが確定するまで待機するから。

109 :108:2009/03/26(木) 20:08:44
>>107
それはないw

110 :,,・´∀`・,,)っ-○◎●: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方式の 参考ページは http://www.df.lth.se/~john_e/gems/gem003a.html

114 :,,・´∀`・,,)っ-○○○:2009/05/15(金) 20:53:01
BCD演算ってそもそも遅くね?

115 :デフォルトの名無しさん:2009/05/15(金) 22:00:47
あんまり変わらなかった

116 :デフォルトの名無しさん:2009/05/17(日) 23:45:35
これさ、○○与えると△△返すビット演算教えてください、みたいな感じで
それに人間が答えてるけどさ、
一般的に反復深化の自動計算でビット演算はじき出すフリーソフトとかないんだっけ?


117 :デフォルトの名無しさん:2009/05/17(日) 23:49:36
反復深化?

118 :,,・´∀`・,,)っ-○○○:2009/05/18(月) 00:15:38
サブネットマスクでも計算するの?

てかその手のは社内ツールであったな。

119 :,,・´∀`・,,)っ-○○○:2009/05/18(月) 00:17:55
tmkk氏がBerkeleyのSISってツールがあるって言ってたな

120 :デフォルトの名無しさん:2009/05/19(火) 02:55:16
記憶が正しければ、今はBCD系はMMX系統の余った回路使って演算してる筈。

121 :,,・´∀`・,,)っ-○○○:2009/05/19(火) 03:53:50
ないない。
BCDって64ビットで無効命令だぜ?
Core 2あたりで除算回路そのものが高速化されてるあたり、IDIVと同じようなことやってんだろ

122 :デフォルトの名無しさん:2009/05/24(日) 21:17:29


123 :デフォルトの名無しさん:2009/05/29(金) 06:15:50
//INVERSEはビットの左右を反転する処理
c = INVERSE(a);
d = INVERSE(b);
e = c + d;
f = INVERSE(e);

このようにaとbからfを求める処理があるとき
INVERSEを無くしたり減らしたりはできるでしょうか

124 :,,・´∀`・,,)っ-○○○:2009/05/29(金) 07:25:25
キャリーの逆ができる回路があるならな。

大ヒント
a + b
= (a & b) + ((a ^ b) << 1)

125 :デフォルトの名無しさん: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 :,,・´∀`・,,)っ-○○○:2009/05/31(日) 10:47:55
ARMとかならアンロールしてプレディケートすれば上手い具合に分岐除去できるな

127 :デフォルトの名無しさん:2009/06/06(土) 18:55:12
>>124
a+b = (a^b) + ((a&b)<<1)
の間違い?


128 :,,・´∀`・,,)っ-○○○:2009/06/12(金) 01:37:04
>>127
そーでしたorz

129 :デフォルトの名無しさん: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 :2009/06/20(土) 17:41:04
>>129
a = *((unsigned char *)&c+3);
以下略。

131 :デフォルトの名無しさん:2009/06/21(日) 00:01:18
エンディアン依存のコードはお行儀悪いんじゃなかった?

132 : ◆0uxK91AxII :2009/06/21(日) 08:04:17
ぐはぁ。

133 :デフォルトの名無しさん:2009/06/30(火) 01:49:31
>>123
本質的に難しいね
通常の加算の出力の MSB が入力の全ビットに依存するところを
加算命令が全部1命令でやってるわけで、
その左右反転の LSB が入力の全ビットに依存するような演算はバラすと結構かかる。

反転と再反転やりながら同時に加算もする方法を考えてみたけど
結局加算をバラすしかなくてだめだった。
(c & 0xAAAAAAAA)+(d & 0xAAAAAAAA) とかいろいろ考えたんだが。

逆演算の減算命令使うかなあと思ったけど、それも結局
「MSB が他のすべてのビットに影響を与える力」しかないし、
LSB に対する計算力が全くない。
結局やってることも補数の足し算だしね。
残るは特定係数の乗算?
それでもやっぱり基本的に LSB が上位ビットに無視されちゃう構造だし…。
なんか出力の LSB が入力の複数の上位ビットに依存するような便利な命令ないっすか?
右シフトくらいしか思いつかない…

134 :133:2009/06/30(火) 03:39:26
>>123 左右反転加算
3による除算命令を使って何かできないか?

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 が1入力演算なので2入力演算な左右反転加算にはまだ遠いが…
なにか道が開けるかもしれない。

135 :133: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 :デフォルトの名無しさん:2009/07/01(水) 20:33:21
おいおい、どうして>>125を無視する
inverseせずに出来てるじゃないか

138 :デフォルトの名無しさん:2009/07/01(水) 20:50:37
ああ、ごめん
無視してないよ
コードも実行してみたよ
>>125よりいいのを考えてて思いつかなかった

139 :デフォルトの名無しさん:2009/07/02(木) 02:33:25
>>125 は面白くていいんだけど
ちょっと最悪計算量が大きくない?
0x00000001 = reverse_add(0x80000000, 0xFFFFFFFE) とか。
64ビットとかだったら64回くらいループしそうだし。

140 :デフォルトの名無しさん:2009/07/05(日) 21:53:38
>>116
そんなソフトあるんか・・・ 世界は広いな

141 :デフォルトの名無しさん:2009/07/06(月) 18:55:03
60で割った余りが0かどうか調べるにはどうすればいい?

142 :デフォルトの名無しさん:2009/07/06(月) 19:20:07
60で引いていって60以下になったらそれが答えです

143 :デフォルトの名無しさん:2009/07/06(月) 19:54:13
以下じゃなくて未満ですた









144 :デフォルトの名無しさん:2009/07/06(月) 20:01:13
if(0 == (n + 4) >> 6)
{
}

145 :デフォルトの名無しさん:2009/07/06(月) 20:58:51
>>144
nを60にしても1なんですけどー

146 :デフォルトの名無しさん:2009/07/07(火) 03:43:18
>>141 if( (n%60) ) { 0じゃないほう } else { 0のほう }
%は言語によって MOD とかもある。

147 :デフォルトの名無しさん:2009/07/07(火) 04:08:05
え、マジで言ってる?
このスレの住人にも不可能なの?

148 :,,・´∀`・,,)っ-○○○:2009/07/07(火) 20:47:14
分岐のオーバーヘッドは高くないと仮定して、除算の平均回数を減らすほうがいいだろ

if ((n & 3) || (n % 60))

149 :デフォルトの名無しさん: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 :デフォルトの名無しさん: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:2009/07/08(水) 01:14:43
x=(((n>>2)*0x01111111)>>12 & 0xf);
& 0xf を忘れてた

152 :デフォルトの名無しさん:2009/07/08(水) 02:54:49
すげー乗算になってさっぱり判らん


153 :デフォルトの名無しさん: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:2009/07/08(水) 03:19:13
エラーで>>150の投稿に気づかなかった・・・
まぁこっちもビット数の制限がゆるいって利点はあるか

>>150-151
定数での乗算を加算とビットシフトで置き換える操作はコンパイラ任せってことでしょうか

155 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/07/09(木) 03:40:25
sprintf(buf,"%d",(int)n) を実装したいわけね。
小さくしたいなら、百の位からforループで回すべき。早くしたいなら、百の位を処理した後の
forループは1,2回しか回らないのだから、ifのがいい。bufの頭は呼び出し側で知っている
のだから、そこを返すのはムダだと思う。呼び出し側で役に立つ情報:文字列長を返すとか、
末尾nullをつけてc標準の文字列にしておいたほうがいい。

157 :デフォルトの名無しさん: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 :デフォルトの名無しさん:2009/07/09(木) 21:50:37
それだと他のbitにする場合もcolumnsや型を調整するだけで楽ですね。


159 :デフォルトの名無しさん:2009/07/11(土) 17:59:06
今更だけど

x86でeaxにn>>2が入っているとして
(n>>2)*0x01111111
をちょっと手動で最適化してみてるんだけど、誰か8クロック未満になった人居る?

160 :デフォルトの名無しさん:2009/07/12(日) 01:22:15
>>159
クロック計測はもうムリゲじゃ・・・?

161 :154: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);
自分はこれが精一杯で、命令数調べるのが面倒だったからコンパイルしたら吹いたwww
最適化切るとregister指定に関係なくスタック使うわ、最適化すると乗算命令に戻るわww
乗算の展開は乗除命令を持たないCPUでないとあんまり意味が無いって示唆なのかね?

>>154で加算とビットシフトで置き換えって書きましたが、逆効果かもしれませんゴメンナサイ。

162 :154: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 :デフォルトの名無しさん:2009/07/12(日) 15:59:57
適切なコメントをつける。

165 :デフォルトの名無しさん:2009/07/13(月) 01:06:27
2^N単位の切り上げ処理とか

X=(X+3)&~3;

166 :デフォルトの名無しさん:2009/07/13(月) 01:12:55
式の中にNがないのにワロタ。

167 :デフォルトの名無しさん:2009/07/13(月) 04:13:17
>>163
いっぱいありすぎて書けない

168 :デフォルトの名無しさん:2009/07/13(月) 07:59:56
思いつくだけ片っ端から書いてみて

169 :デフォルトの名無しさん:2009/07/13(月) 08:37:16
30で割った余りを調べるどうする?

170 :デフォルトの名無しさん:2009/07/13(月) 08:47:36
日本語でOK

171 :デフォルトの名無しさん:2009/07/13(月) 09:21:09
海の水はどうしてですか?

172 :デフォルトの名無しさん:2009/07/13(月) 20:39:25
>>171
浸透圧がでてこないから

173 :デフォルトの名無しさん:2009/07/13(月) 21:12:18
>>167
書いてもいいですよ

174 :デフォルトの名無しさん:2009/07/13(月) 23:46:18
>>169
30で引いていって、30で引けなくなったらそれが余りです

175 :デフォルトの名無しさん:2009/07/14(火) 01:02:12
>>169
30進数表記に変換したときの一の位の数字をみる

176 :デフォルトの名無しさん:2009/07/14(火) 02:29:17
おまいらすごいな。やっぱりアセンブラ経験がかなりあるおっさんが多い?

177 :デフォルトの名無しさん:2009/07/14(火) 03:45:31
1969年からPGやってたからな。その頃は業務用のプログラムでもASM必須。
データベース使って部品展開とか組むのにメモリ48KBとか52KBだもん。

178 : ◆0uxK91AxII :2009/07/14(火) 12:09:18
スレ違いも、度が過ぎる。

>>174
無限ループだね。

179 :デフォルトの名無しさん:2009/07/14(火) 12:16:26
ここの人たちは何読んで勉強したの
the art of computer programming
ハッカーのたのしみ
Intel/AMDの最適化マニュアル
以外だと


180 :デフォルトの名無しさん:2009/07/14(火) 21:29:50
計算機プログラムの構造と解釈
とかじゃないか?

俺はmasm.exeとlink.exeとxda.exeで勉強したけど。

181 :デフォルトの名無しさん:2009/07/14(火) 21:39:11
その本全然ビット演算は関係ない
関係あるとしたら伝播遅延を含んだ論理回路設計の章があるけど
練習問題でもリップルキャリー加算器を作るまでで
ビット処理のテクニック的なことはほとんど出てこない
ただ、5章は未読なので知らん

182 :デフォルトの名無しさん:2009/07/14(火) 22:16:15
http://www.amazon.co.jp/CPU%E3%81%AE%E5%89%B5%E3%82%8A%E3%81%8B%E3%81%9F-%E6%B8%A1%E6%B3%A2-%E9%83%81/dp/4839909865

183 :デフォルトの名無しさん:2009/07/14(火) 22:22:11
     http://www.amazon.co.jp/dp/4839909865



184 :デフォルトの名無しさん:2009/07/14(火) 22:23:41
>179
256倍シリーズとか。エキスパートCプログラミングとか。

185 :デフォルトの名無しさん:2009/07/14(火) 22:54:40
256は知らんが、エキスパート(略はビット演算に関することは少ししか
無かったと思う。やはり昔のアセンブリメインの時代に習得したのか?

186 :デフォルトの名無しさん:2009/07/14(火) 23:33:26
俺はZ80マシン語秘伝の書を読んだ。

187 :デフォルトの名無しさん:2009/07/15(水) 00:32:09
>>166
例として2を代入したんだが、気づいてくれよ・・・
X=(X+(pow(2,N)-1))&~(pow(2,N)-1);

BMP形式の1ラインのバイト数求める時に良く使う

188 :デフォルトの名無しさん:2009/07/15(水) 00:34:38
>>179
解析魔法少女美咲ちゃんマジカルオープン!
http://www.amazon.co.jp/exec/obidos/ASIN/4798008532

Windowsプロフェッショナルゲームプログラミング2
http://www.amazon.co.jp/exec/obidos/ASIN/4798006033

…何か?
ええどーせ二次オタのゲーム好きですよ…

189 :デフォルトの名無しさん:2009/07/15(水) 11:38:16
(Z80|8086)マシン語秘伝の書は、機械語的のTipsの本で、ハッカーズディライトにあるような
高度(?)なビット演算の技は出てこない。

190 :デフォルトの名無しさん:2009/07/15(水) 14:39:51
The Art of Computer Programming.

191 :デフォルトの名無しさん:2009/07/15(水) 18:50:51
>>189
あの頃だと、下手にビット演算するよりも、
如何に効率の良いテーブル参照をできるかが勝負だった気がする。

192 :デフォルトの名無しさん:2009/07/16(木) 10:42:27
メモリは少ないけど、アクセスのペナルティは小さかったからな。

193 :デフォルトの名無しさん:2009/07/16(木) 19:00:25
>>192
つか、ペナルティだらけだったな。
今から考えると。


194 :,,・´∀`・,,)っ-○○○:2009/07/17(金) 23:26:58
>>179
やぱ、へるみ氏の掲示板じゃね?


195 :デフォルトの名無しさん:2009/07/30(木) 00:38:12
>>141 60 で割り切れるか

if((mul(x,0xEEEEEEEF) < 0x11111111) & (x&3==0)){
//割り切れる
}else{
//割り切れない
}

ここで mul(x,y) 命令は x*y の下位 32 bit
ハッカーのたのしみに載ってた

196 :デフォルトの名無しさん:2009/07/30(木) 02:26:43
mulがなかったらどうするの

197 :デフォルトの名無しさん:2009/07/30(木) 12:38:51
このスレ…とんでもないノネナール臭がする…

198 :デフォルトの名無しさん:2009/07/30(木) 13:26:35
シトロネラール臭もする

199 :,,・´∀`・,,)っ-○○○:2009/07/30(木) 20:51:57
test eax, 3
>>195
x86だとこんな感じかな。悪くない。

jnz c1else
mov edx, 3
mul edx, EEEEEEEFh
cmp edx, 111111111h
jl c1else
;; 割り切れる
jmp c1end
c1else:
;; 割り切れない
c1end:

200 :,,・´∀`・,,)っ-○○○:2009/07/30(木) 20:52:41
変なところにtest eax, 3がorz

201 :デフォルトの名無しさん:2009/07/30(木) 22:53:38
団子さんってどんな仕事してるの?

202 :,,・´∀`・,,)っ-○○○:2009/07/30(木) 23:00:01
訂正

test eax, 3
jnz c1else
mov edx, eax
mul edx, EEEEEEEFh
cmp edx, 111111111h
jl c1else
;; 割り切れる
jmp c1end
c1else:
;; 割り切れない
c1end:

>>201
刺身の上にタンポポを(ry

じゃなくて基本はPHPやRubyなんかの高級言語使い
たまにバイナリ操作用にC/C++なんかでライブラリを書いたりもする

203 :デフォルトの名無しさん:2009/07/30(木) 23:05:11
ていうか、話題自体の内容はなかなか面白いんだが
元質問者の>>141は既に居ない可能性が。

204 :,,・´∀`・,,)っ-○○○:2009/07/30(木) 23:11:34
このスレはアスペ・ADHDが多いからそんなことどうでもいいんだ。


205 :デフォルトの名無しさん:2009/07/30(木) 23:14:51
>>202
なるほど。それは才能の無駄使いのような。
昔はローレベルなことをやってたとか?

206 :デフォルトの名無しさん:2009/07/30(木) 23:20:15
フィクスターズにとらばーゆとか考えないの?

207 :,,・´∀`・,,)っ-○○○:2009/07/31(金) 18:19:15
俺をスカウトしてみてよ>ふぃく☆すたの中の人

転職考えてた時期に本名で問い合わせたらシカトされたんで見る目がない会社ってことだけはわかった。

208 :デフォルトの名無しさん:2009/07/31(金) 18:58:48
バイト列の各ビットを、それぞれ独立した8本のビットストリームとして
扱いたいのですが、簡単に分離する方法はあるでしょうか。

80 40 80 40 80 80 40 40というバイト列がきたら、

0〜5は 00000000b
6 は 01010011b
7 は 10101100b

という感じに抽出したいのです。

1つのバイトに対して8回ループするしかないでしょうか。

int i;
unsigned char buf[BUFSIZE];
for (i = 0; i < BUFSIZE; i++) {
 unsigned char pos, bit;
 unsigned char byte = buf[i]; // バイト列
 for (pos = 8, bit = 0x80; pos; bit>>=1) {
  pos--;
  stream[pos] <<= 1;
  if (byte & bit) {
   stream[pos] |= 1;
  }
 }
}


209 :,,・´∀`・,,)っ-○○○:2009/07/31(金) 19:05:54
PMOVMSKB

210 :デフォルトの名無しさん:2009/07/31(金) 19:06:10
>>208
if文の存在が分からない。
単純に元のビットをシフトしながら8本分合成していけばいいんでないの?


211 :,,・´∀`・,,)っ-○○◎:2009/07/31(金) 19:11:21
Hacker's Delightのtranspose.cがそのまんま答えだな

212 :デフォルトの名無しさん:2009/07/31(金) 19:12:57
>>209
x86系ではないので、汎用的な方法があれば

>>210
こういうことでしょうか?
int i;
unsigned char buf[BUFSIZE];
for (i = 0; i < BUFSIZE; i++) {
 unsigned char pos;
 unsigned char byte = buf[i]; // バイト列
 for (pos = 0; pos < 8; pos++) {
  stream[pos] <<= 1;
  stream[pos] |= (byte & 1);
  byte>>=1;
 }
}
これ以上は無理でしょうか。

213 :デフォルトの名無しさん:2009/07/31(金) 19:27:22
>>211
http://www.hackersdelight.org/HDcode/transpose8.c
を見るとループを展開したりバイト列をlongにまとめたりするだけで
同じものみたいですね。
その本は面白そうなので買ってみます。
ありがとうございました。

214 :デフォルトの名無しさん:2009/07/31(金) 19:27:22
なんでstream[]もbyteもシフトするの?
なんで1でアンド取るの?

215 :デフォルトの名無しさん:2009/07/31(金) 19:48:11
>>214
仰ってる事が判らないのですが、
streamに格納していくには両方シフトしないとだめですよね?
transpose8vnのようにしろということでしょうか。

int i;
unsigned char buf[BUFSIZE];
for (i = 0; i < BUFSIZE; i+=8) {
 unsigned char *a = buf+i;
 stream[0] = (a[0] & 128)  | (a[1] & 128)/2 | (a[2] & 128)/4 | (a[3] & 128)/8 |
       (a[4] & 128)/16 | (a[5] & 128)/32 | (a[6] & 128)/64 | (a[7]   )/128;
 stream[1] = (a[0] & 64)*2 | (a[1] & 64)  | (a[2] & 64)/2 | (a[3] & 64)/4 |
       (a[4] & 64)/8 | (a[5] & 64)/16 | (a[6] & 64)/32 | (a[7] & 64)/64;
 stream[2] = (a[0] & 32)*4 | (a[1] & 32)*2 | (a[2] & 32)  | (a[3] & 32)/2 |
       (a[4] & 32)/4 | (a[5] & 32)/8 | (a[6] & 32)/16 | (a[7] & 32)/32;
 stream[3] = (a[0] & 16)*8 | (a[1] & 16)*4 | (a[2] & 16)*2 | (a[3] & 16)  |
       (a[4] & 16)/2 | (a[5] & 16)/4 | (a[6] & 16)/8 | (a[7] & 16)/16;
 stream[4] = (a[0] &  8)*16 | (a[1] &  8)*8 | (a[2] &  8)*4 | (a[3] &  8)*2 |
       (a[4] &  8)  | (a[5] &  8)/2 | (a[6] &  8)/4 | (a[7] &  8)/8;
 stream[5] = (a[0] &  4)*32 | (a[1] &  4)*16 | (a[2] &  4)*8 | (a[3] &  4)*4 |
       (a[4] &  4)*2 | (a[5] &  4)  | (a[6] &  4)/2 | (a[7] &  4)/4;
 stream[6] = (a[0] &  2)*64 | (a[1] &  2)*32 | (a[2] &  2)*16 | (a[3] &  2)*8 |
       (a[4] &  2)*4 | (a[5] &  2)*2 | (a[6] &  2)  | (a[7] &  2)/2;
 stream[7] = (a[0]   )*128| (a[1] &  1)*64 | (a[2] &  1)*32 | (a[3] &  1)*16|
       (a[4] &  1)*8 | (a[5] &  1)*4 | (a[6] &  1)*2 | (a[7] &  1);
}

216 :デフォルトの名無しさん:2009/07/31(金) 19:53:05
なんだw 先に答え出てるじゃんw
最後はなんでるーぷするのって硫黄と思ってたのにw

217 :デフォルトの名無しさん:2009/07/31(金) 19:53:35
あ、streamの添字が逆でした7→0

218 :デフォルトの名無しさん:2009/07/31(金) 19:58:36
中間を全部レジスタでできるから展開はできるだけした方が速いのでしょうね。
コード量と相談ですね。
ありがとうございました。

219 :デフォルトの名無しさん:2009/07/31(金) 23:27:06
いいえ、ループの(単純な)展開は人間がやるべきじゃありません。

220 :デフォルトの名無しさん:2009/07/31(金) 23:56:47
1ビットずつしかシフトできない環境では使えないな

221 :デフォルトの名無しさん:2009/08/01(土) 00:31:32
これで8バイト単位での入力が仕様なら、固定の方が早いと思う。

222 :デフォルトの名無しさん:2009/08/01(土) 00:32:30
あ、でもマシンコードのキャッシュとかまで考えると、どっちが早いんだろ。
ループと、展開

223 :デフォルトの名無しさん:2009/08/01(土) 00:42:46
あまりに初歩的すぎて突っ込むべきかどうか悩んだが、
「 計 測 し ろ 」

224 :デフォルトの名無しさん:2009/08/01(土) 01:13:18
コンパイラ性能で異なるから計測しても意味無いだろうな。

225 :デフォルトの名無しさん:2009/08/01(土) 01:17:07
そんな理由で意味がないというなら、議論そのものに意味がないだろ。

226 :デフォルトの名無しさん:2009/08/01(土) 01:33:44
むしろCPUとかプラットフォームの違いの差が大きいだろう
実際に使う人が実際に使う環境で計測すりゃいいんだよ。

227 :デフォルトの名無しさん:2009/08/01(土) 01:41:11
つっても最近はループまで最適化するからな・・・コンパイラ。
CPU向けに分岐のヒントつける場合も有るんだっけ?

じゃなくてCPUと対象のアルゴリズムのほうが影響するかな。

ループの方が良くなる要因
・コードサイズが小さくなる
 :CPUのキャッシュに収まらないほどの大規模なアルゴリズムで有効
・アドレッシングが単純
 :演算単位が大きかったり、添字がアドレッシング能力ギリギリだった場合に有効
展開の方が良くなる要因
・ハザードコストが減る
 :パイプラインが存在する場合に有効
・分岐条件の計算が数分の1に減る
 :常に有効。分岐条件が複雑であるほど効果が高い

アドレッシングのコストは分岐条件やハザードコストで十分にペイ出来そうだし、最近のCPUのキャッシュで足りないほどの大規模な展開を要する事って少ないだろうことを考えれば、どのみち最近のPC事情なら展開の方がよさそうだけど。

228 :デフォルトの名無しさん:2009/08/01(土) 01:50:51
              , -‐;z..__     _丿
        / ゙̄ヽ′ ニ‐- 、\  \   ところがどっこい
       Z´// ,ヘ.∧ ヽ \ヽ ゝ   ヽ   ‥‥‥‥
       /, / ,リ   vヘ lヽ\ヽヽ.|    ノ  最新のPCじゃありません
       /イル_-、ij~  ハにヽ,,\`| <      ‥‥‥‥!
.        N⌒ヽヽ // ̄リ:| l l |   `)
            ト、_e.〉u ' e_ ノノ |.l l |  ∠.   現実です
          |、< 、 ij _,¨、イ||ト、|     ヽ      ‥‥‥!
.           |ドエエエ「-┴''´|.|L八   ノ -、   これが現実‥!
            l.ヒ_ー-r-ー'スソ | l トゝ、.__   | ,. - 、
    _,,. -‐ ''"トヽエエエエ!ゝ'´.イ i l;;;;:::::::::::`::ー/
   ハ:::::::::::::::::::::| l\ー一_v~'´ j ,1;;;;;;:::::::::::::::::::
.  /:::;l::::::::::::::::::::;W1;;;下、 /lル' !;;;;;;;;;::::::::::::::::
  /:::::;;;l:::::::::::::::::;;;;;;;;;;;;;;;|: :X: : : : : |;;;;;;;;;;;;;;::::::::::::
 /:::::;;;;;;|:::::::::::::::;;;;;;;;;;;;;;;;|/: : >、: : :|;;;;;;;;;;;;;;;:::::::::::

229 :デフォルトの名無しさん:2009/08/01(土) 03:59:10
だから、コンパイラに判断させればいいっての。
コンパイラが適切に展開できないことが判ってから初めて人手で展開すればいい。

230 :,,・´∀`・,,)っ-○○○:2009/08/01(土) 05:19:20
たとえばさ、8x8ビットをひっくり返すくらいだったらさ
テーブル使ったっていいんだぜ
出力先の配列が連続ならな


231 :デフォルトの名無しさん:2009/08/01(土) 16:13:32
オンドゥル語を符号に使えないでしょうか

232 :デフォルトの名無しさん:2009/08/01(土) 17:25:57
ウヅダドンドコドーン!!

233 :デフォルトの名無しさん:2009/08/01(土) 17:30:07
最上位ビットで 最上位からnビット分埋める
ってのを格好よく書きたいんだけどうまくいかない。
0b10000000 で n=3 なら 0b11100000 にするみたいな感じで。

234 :デフォルトの名無しさん:2009/08/01(土) 18:30:51
x | ~((1 << (8-n)) -1) みたいな感じか

235 :デフォルトの名無しさん:2009/08/02(日) 03:12:48
cでsignedなら算術シフトになるんじゃなかったかな。
ASMなら、論理シフトしかなくても、キャリーを立てておいてキャリーごとローテートで。

236 :デフォルトの名無しさん:2009/08/02(日) 04:09:21
とりあえず、
符号付整数型の負値の算術右シフトの結果がどうなるか(符号をどう扱うか)は処理系定義なので、
それを仮定して依存するコードを書いてはいけない。

それ以前の話として、
シフトじゃなくてマスクを望んでいるように思える。
言葉からも例からも断定は出来ないが。

237 :デフォルトの名無しさん:2009/08/02(日) 05:10:10
それなら、32bitでも32個のテーブルでいいんだから、mask[]={0,0x80000000,0xC0000000,・・・
0xFFFFFFFE,0xFFFFFFFF } を用意して、x |= mask[n]; でいいじゃん。

238 :デフォルトの名無しさん:2009/08/02(日) 05:14:14
>>234 == >>237 == baka

239 :デフォルトの名無しさん:2009/08/02(日) 11:27:54
>> 236
算術右シフトを使うときは
#if ((-1)>>1)!=0
#error
#endif
と書いてるよ

240 :デフォルトの名無しさん:2009/08/02(日) 11:29:01
>>239 訂正
#if ((-1)>>1)!=-1
#error
#endif

241 :デフォルトの名無しさん:2009/08/02(日) 13:28:13
0-(0x80000000>>(n-1))
か?

242 : ◆0uxK91AxII :2009/08/02(日) 13:36:46
0b01011000 で n=4 なら 0b00001000
とか、有り得そうな雰囲気。

243 :デフォルトの名無しさん:2009/08/02(日) 13:39:16
なんでこんなあほばっかりなんだここは?

244 :あほ:2009/08/02(日) 14:08:27
>>243
なら君が有無を言わせぬ明快なレスであほを黙らせてくれ。

245 :デフォルトの名無しさん:2009/08/02(日) 14:31:15
>>220
AVRで考えてみる。
1〜7シフト計算量
1,2,3 シフト 1〜3クロック
4 ニブル交換、AND 2クロック
5,6,7 ニブル交換、AND、シフト 3〜5クロック
最大5、平均3クロック。

>>215を実装すると、
レジスタ←a[0] 2クロック
AND 1クロック
レジスタ←a[1] 2クロック
AND 1クロック
右シフト1回 1クロック
OR 1クロック
(略)
stream[0]←レジスタ 2クロック
ここまで53クロック、(アドレス計算除く)
これを8回で424クロック。

同条件でループ>>212
レジスタ←buf[i] 2クロック
レジスタ←stream[pos] 2クロック
左シフト 1クロック
AND 1クロック
OR 1クロック
stream[pos]←レジスタ 2クロック
右シフト 1クロック
ここまで10クロック、これを8x8回繰り返すと640クロック。
実際は条件ジャンプ処理を加えるとさらに増える。
ループにすると1.5倍以上は掛かる。


246 :デフォルトの名無しさん:2009/08/02(日) 14:57:25
キャリーを使えば7ビットシフトは3クロック
C←レジスタ 1
レジスタクリア 1
レジスタ←C 1


247 :デフォルトの名無しさん:2009/08/02(日) 15:00:46
ヒント:夏休み

248 :233:2009/08/02(日) 21:34:48
言葉が足りないようですまなかたですが、マスクを望んでます。
>>242みたいな感じで。

249 :デフォルトの名無しさん:2009/08/02(日) 22:34:05
マスクか。
ビット列の長さにも寄るけれど、それほど長い単位でなければ、簡単かつ見通しがいいのはテーブル参照だろう。

250 :デフォルトの名無しさん:2009/08/02(日) 22:54:56
テーブル参照のが良いなんて一概には言えないでしょ。
メモリアクセスだけじゃなく、アドレス計算も入るわけで
例えばn=5から (1<<n)-1で下位4bitのマスクが整数演算だけで出せるわけだし
これを反転させたり、nを要求bit数に応じて細工するのも当然整数だし。
もちろん、アドレス計算も整数だけどね。
自由度は圧倒的にテーブルが有利だけど。

251 :233:2009/08/03(月) 03:48:50
-4096〜4095の整数に落とし込みたいとか、そういうのがやりたくて
符号をほしいところまでうにょ〜んと延ばしたら出来るかも! と
思ったんだス。
変な思考でごめん。

252 :デフォルトの名無しさん:2009/08/03(月) 04:24:27
>>250
つ簡単かつ見通しがいいのは

253 :デフォルトの名無しさん:2009/08/03(月) 04:44:59
>>251
算術シフト・・・

254 :デフォルトの名無しさん:2009/08/03(月) 04:53:04
>>252 そういうのは、別の(普通の)スレ向き。
このスレで(多数に)求められているのは、可読性を落としてでも1clock削ること。

255 :デフォルトの名無しさん:2009/08/03(月) 08:29:25

たとえば3ビットシフトと4ビットシフトで所要クロック数は変わりますか?

256 :デフォルトの名無しさん:2009/08/03(月) 09:10:11
変わるプロセッサもある。
例えば、8086や80286は変わる。

最近のプロセッサは
普通バレルシフタが載っているので、変わらない。

257 :,,・´∀`・,,)っ-○○○:2009/08/03(月) 21:31:57
Pentium 4って4ビットの左シフトやるならこれやった方が速かったよな

add eax, eax
add eax, eax
add eax, eax
add eax, eax


258 :デフォルトの名無しさん:2009/08/03(月) 22:32:13
なんかぐぐったら2006年頃のダンゴも同じ事言ってた


259 :,,・´∀`・,,)っ-○○○:2009/08/04(火) 07:32:09
Pen4の倍速ALUは上位と下位16ビットを0.5クロックずらして伝播する。
整数加減算は1クロックに2回実行出来てアホみたいに得意だがシフトが苦手。

260 :デフォルトの名無しさん:2009/08/06(木) 14:38:22
int memcmp(const void *vl, const void *vr, unsigned int len) {
unsigned char *l = (unsigned char *)vl, *r = (unsigned char *)vr;
for (;len--;) {
unsigned char x = *l++;
unsigned char y = *r++;
if (x > y)
return 1;
else
if (x < y)
return -1;
}
return 0;
}

unsigned char比較の不一致で1と-1を返したいのですが、
もっと簡単にならなかったでしょうか?
(1、-1じゃなくても正負が戻ればいいです)
昔どこかで見たような気がしたので。

261 :デフォルトの名無しさん:2009/08/06(木) 15:59:47
引き算しる
0ならループ

262 :デフォルトの名無しさん:2009/08/06(木) 18:52:16
4byteごとに比較して、同じ時はすぐ次
ってのは、alignあってないとだめ?

263 :デフォルトの名無しさん:2009/08/06(木) 19:08:09
>>262
CPU、またはその設定による。

整数単位で処理するのなら、8バイト
単位のほうがより速いのでは。

264 :デフォルトの名無しさん:2009/08/06(木) 19:35:03
>>262
CPUに依存しそうな質問するなら使ってるCPUくらい書けよ

265 :デフォルトの名無しさん:2009/08/07(金) 17:34:45
>>262
CPUによっては跨いだ時点で例外が飛ぶ

266 :デフォルトの名無しさん:2009/08/07(金) 19:02:29
昔のLISPはLSBが無視されるのを利用してタグに使ってた


267 :,,・´∀`・,,)っ-○○○:2009/08/07(金) 19:40:45
アラインメント制約の比較的緩いx86ですらページ境界跨ぎの問題があるからな


268 :デフォルトの名無しさん:2009/08/07(金) 19:41:01
>>266
いまでもそうだが, ネイティブコンパイルする処理系…
car とか cadr とか elis とかのバイトコードなマシンは MSB 側に
tag 持ってるような気が…


269 :デフォルトの名無しさん:2009/08/07(金) 20:21:31
例えば24bitで16Mセルしか使わないと見積もれば、残り8bitがタグとして使える。
ここで言ってる話はマスクが必要ないということだろう。

270 :デフォルトの名無しさん:2009/08/07(金) 22:23:10
逆にarmみたいなAlignきつい奴って
byte pointerのインクリメントってどうやってんの?

271 :デフォルトの名無しさん:2009/08/07(金) 22:34:12
>>269
(初代)68000マシンとかであったな。

272 :デフォルトの名無しさん:2009/08/08(土) 14:14:00
>>270
ARMでもアドレスはバイト単位なんだから、ポインタ計算時には気にしなくて良いよ。
メモリアクセスするときには下位ビットをマスクすればOK。
下位ビット値からマスクやシフトの計算して任意のバイトにアクセスする。


273 :デフォルトの名無しさん:2009/08/08(土) 22:08:18
250みたいなのは、両方のアラインメントで場合分けすると
えーと、何通りにすればいいんだ
4バイトだと9通り?

274 :デフォルトの名無しさん:2009/09/15(火) 20:04:58
ビット演算の本格的素養を身につけるには
どんなドキュンメントを参照するべきですか?

275 :デフォルトの名無しさん:2009/09/15(火) 20:55:30
>>274
カーニハン&リッチー

276 :デフォルトの名無しさん:2009/09/16(水) 07:44:51
そうなのか
本格的とか書いてあるから74シリーズのデータシートでも見せるべきなのかと思った

277 :デフォルトの名無しさん:2009/09/16(水) 08:13:01
74シリーズのデータシート見てもカルノー図は書けるようにならないぞ

278 :,,・´∀`・,,)っ-○○○:2009/09/19(土) 00:33:39
クヌースと墓寺

279 :デフォルトの名無しさん:2009/09/21(月) 21:40:06
枕好き法

280 :デフォルトの名無しさん:2009/10/18(日) 22:27:25
今日一日悩んだが決定打が見つからず。
だれかアドバイスくだしあ。

[問題]
81ビットのデータがある。
アプリケーション上の制約から81ビットのうち値が1になるビットは高々15個である。
このデータを情報の欠損なく64ビットに圧縮したい。
その際、圧縮伸長はなるべく高速なものが望ましい。
どのようなアルゴリズムがよいか。



281 :280:2009/10/18(日) 22:41:00
>アプリケーション上の制約から81ビットのうち値が1になるビットは高々15個である。

ちょっと微妙な表現ですが、どのビットも1になれるけど、
81ビット全体として見たとき同時に1になるのは高々15個と言う意味です。



282 :デフォルトの名無しさん:2009/10/18(日) 23:56:13
1.81ビットの先頭から0をカウントする
2.16個カウントするか、1が出てきたら、個数を4bitで吐き出す
3.最後まで繰り返して81ビット端まで言ったら、残りは0でパディング

(1が高々15個なら0が連続する領域は、最悪でも16箇所なので)

戻すときは、
1.64ビットの先頭から、4ビット取り出す。
2.取り出した数分0を吐き出す。吐き出した個数が64超えたら終わり
2.1を吐き出す。4bit取り出して2.に戻る。

早い実装は誰かに任せた

283 :デフォルトの名無しさん:2009/10/19(月) 00:03:03
11...1100...001 はどうなるの

284 :デフォルトの名無しさん:2009/10/19(月) 00:13:03
カウントを15個ずつにすれば何とかなると思ったが
最悪80ビットになるな

285 :デフォルトの名無しさん:2009/10/19(月) 00:14:27
81ビットの先頭から見ていって、
1が出てきたら11を吐き出す、
01が出てきたら10を吐き出す、
00が出てきたら0を吐き出す。

これじゃだめかね。

286 :デフォルトの名無しさん:2009/10/19(月) 00:31:08
将棋の何の条件だろう

287 :280:2009/10/19(月) 00:35:48
>>285
おお、仕様も満たすし速度的にも完璧です。
ありがとうございます。

余談になりますが、高々15個のところを高々16個に変えると
>>285でぎりぎりアウトのケースがあるみたいです。
組み合わせの数的には64ビットで16個収まるみたいですが
16個でも速いアルゴリズムはあるのか、ちょっと気になりますね。



288 :デフォルトの名無しさん:2009/10/19(月) 00:47:32
>>282
あいぢあはそれでいい
16個連続してたときの扱いにバグが有りそう
平均で連続するのは4個か5個だから16分割4bitだともったいない
huffmanとか出現頻度で長さが変わるコードにすれば
もっと圧縮できると思うけど
そのテーブルを81bitに含めるかどうかでも変わってくる



289 :デフォルトの名無しさん:2009/10/19(月) 01:05:30
81ビット中、1は15個、0は66個

よって、0を圧縮するのがよい?

290 :デフォルトの名無しさん:2009/10/19(月) 04:55:00
81ビットの先頭から見ていって、
1が出てきたら111を吐き出す、
01が出てきたら110を吐き出す、
001が出てきたら10を吐き出す、
000が出てきたら0を吐き出す。


291 :デフォルトの名無しさん:2009/10/19(月) 08:53:42
それ先頭に1が15連続したとき 3*15 + (81-15)/3 = 67
15個の場合すら未クリアで>>285に劣るようだけども

292 :デフォルトの名無しさん:2009/10/19(月) 09:07:19
と思ったら1→10 001→111 で解決するな

293 :デフォルトの名無しさん:2009/10/19(月) 11:37:58
81ビットの先頭から見ていって、
1が出てきたら10を吐き出す、
01が出てきたら110を吐き出す、
001が出てきたら1110を吐き出す、
0001が出てきたら1111を吐き出す、
0000が出てきたら0を吐き出す。

294 :デフォルトの名無しさん:2009/10/19(月) 11:38:40
>>285,290
要するに、ハフマン符号化?


295 :デフォルトの名無しさん:2009/10/19(月) 11:49:00
0が連続する確立が他界から00->0はいいとして
それ以外は逆にbit数殖えちゃうんだよもん


296 :デフォルトの名無しさん:2009/10/19(月) 11:54:11
>>293
(0001)^15 0^21

297 :デフォルトの名無しさん:2009/10/19(月) 12:05:27
>>290
(01)^15 0^66

298 :デフォルトの名無しさん:2009/10/19(月) 12:07:30
(01)^15 0^51 orz

299 :デフォルトの名無しさん:2009/10/19(月) 17:58:00
>>280
1になるビットの最低個数は0?

圧縮の話はスレ違いな気もするけど、いま圧縮アルゴリズムを語るスレは無いのね。

300 :デフォルトの名無しさん:2009/10/19(月) 19:53:31
>>280
これって、数え上げ符号でいいんじゃないかな?

301 :デフォルトの名無しさん:2009/10/19(月) 20:14:28
遅いんじゃないの?

302 :280:2009/10/19(月) 21:17:37
>>299
当初の仕様では1になるビットの最低個数は0でしたが、
今は立ってるビットが極端に少ないときは32ビットまで絞ろうかなーとか思ってます。
よかったら32ビットで何個のビットまで対応できるかもアドバイスください。


303 :デフォルトの名無しさん:2009/10/19(月) 21:26:07
>>285をみて理解できた完璧だとか言えるなら全体のbit数に応じて出現最大bit数を計算する応用は出来るはずだろ

304 :デフォルトの名無しさん:2009/10/19(月) 21:44:10
>>303

>>285については
1.仕様を満たしている。
2.ワンパスで速度もほぼ最速に近い
ということは理解できるし、32bitへの応用もある程度できると思いますが
どの圧縮方法が最善か?ということになるとどう考えればいいか難しいです。


305 :デフォルトの名無しさん:2009/10/19(月) 22:06:59
出現頻度が常に0>1ならハフマン符号化でいいんじゃないの

306 :デフォルトの名無しさん:2009/10/19(月) 22:29:54
データ長 81ビット その内 1になるビットは最大15個 欠損なく 64ビットに圧縮

000 -> 0            3ビット毎 区切り 右の様に 変換(圧縮) 64ビットに満たない時は 0 で埋める
001 -> 100           81ビットなので 27組
010 -> 101           64ビットに収める為には
100 -> 110            1組に1が1個ある場合は無圧縮なので 64/3=21.33 最大21個まで1を許容
011 -> 11100           1組に1が2個ある場合は拡大なので   64/5=12.8 最大24個まで1を許容
101 -> 11101               :
110 -> 11110          81-64=17 /2=8.5 000 が最低 9組無いと駄目 27-9=18
111 -> 11111          もろもろ計算すると この方法では 最大18個まで1を許容する  と思う

解凍方法
 1.1ビット拾う ---> ア
 2.ア が 0 なら 000 を吐き 5へ
   ア が 1 なら 2ビット拾う ---> イ
 3.イ が 00 なら 001 を吐き 5へ
   イ が 01 なら 010 を吐き 5へ
   イ が 10 なら 100 を吐き 5へ
   イ が 11 なら 2ビット拾う ---> ウ
 4.ウ が 00 なら 011 を吐き 5へ
   ウ が 01 なら 101 を吐き 5へ
    ウ が 10 なら 110 を吐き 5へ
    ウ が 11 なら 111 を吐き 5へ
 5.1へ 27組分やったら終り もしくは 1の出現をカウントし 最大数に達していたら終り

ハフマン符号化の亜種

307 :280:2009/10/19(月) 23:23:20
組み合わせの数から言っても19個だと絶対に64ビットに収まりきらないようなので>>306が最適解てことになりますね。
ありがとうございます。
圧縮時のワード長に3を選んだのもハフマン符号の考え方から導き出せるんでしょうか。


308 :デフォルトの名無しさん:2009/10/19(月) 23:35:17
ちゃくちゃくと将棋の終盤戦の圧縮アルゴリズムに向かってるにおいがしてきました…

309 :デフォルトの名無しさん:2009/10/19(月) 23:36:05
81bitの約数を選んだだけじゃないの?
というかハフマン符号化について調べてないよねきっと。

310 :デフォルトの名無しさん:2009/10/19(月) 23:38:22
将棋の終盤戦で、各々の持駒数計が22個もあるような状態ってよくあることなの?

311 :デフォルトの名無しさん:2009/10/19(月) 23:42:05
詰め将棋だとしてもこの持ち方は非効率的だろ

312 :280:2009/10/19(月) 23:43:41
ハフマン符号はちょっとググって見ましたが、
アルファベットとその出現確率が与えられた時の符号化の説明がありました。
ワード長の選び方に巻してはそのページには特に記述がなかったので
それもハフマン符号の範疇なのかなと疑問を持ちました。


313 :デフォルトの名無しさん:2009/10/19(月) 23:46:30
000 -> 0            
001 -> 100          
010 -> 101          
100 -> 110           
011 -> 11100           1組に1が2個ある場合は拡大なので   64/5=12.8 最大24個まで1を許容
101 -> 11101               :
110 -> 11110          81-64=17 /2=8.5 000 が最低 9組無いと駄目 27-9=18
111 -> 11111          もろもろ計算すると この方法では 最大18個まで1を許容する  と思う

314 :デフォルトの名無しさん:2009/10/19(月) 23:49:54
orz
3bitごとにひとまとまりのデータと見立てた場合でかつ、上であるほど出現頻度が高い場合の符号化パターン
を書こうとしたら誤爆した。

圧縮率を高めたい→高々15個の制限を取り払い、可能な限り増やしたい
ということでなければ>>306ので十分だと思う。
出現頻度調べるコストが許容できるのかどうかわからんし。

315 :280:2009/10/20(火) 00:07:13
そうですね。
期待していた以上の回答がもらえました。
ありがとうございます。
32ビットへの圧縮だと8ビットを1ワードとするくらいのほうがいいですかね。

0が8個     -> 0
0が7個,1が1個 -> 10xxx
0が6個,1が2個  -> 110xxxxx
0が5個,1が3個  -> 1110xxxxxx
...




316 :デフォルトの名無しさん:2009/10/20(火) 01:04:32
それで効率悪くならなければそれでもいいんじゃない?

317 :デフォルトの名無しさん:2009/10/20(火) 01:29:50
実データがある程度作れるなら、辞書持った方がいいと思うけどなあ


318 :デフォルトの名無しさん:2009/10/20(火) 08:00:11
ハフマン符号化とか情報理論の勉強初めて一番最初に習うようなもんだと思っていたが

319 :280:2009/10/20(火) 08:05:12
すいません。>>307で組み合わせの数からいって19個は無理といいましたが、プログラムにバグがありました。
組み合わせの数だけでいえば64ビットで20個まで詰められるみたいです。
私の用途としては>>306で十分なのですが、嘘を言ってしまったので訂正しておきます。


320 :デフォルトの名無しさん:2009/10/20(火) 08:56:02

32bitだと何個まで逝けるんだ?

321 :デフォルトの名無しさん:2009/10/20(火) 18:26:45
一日三回くらいまで

322 :デフォルトの名無しさん:2009/10/20(火) 18:37:25
多い日も安心

323 :デフォルトの名無しさん:2009/10/20(火) 20:41:31
>>320
81Cx <= 2^32 を満たす x までじゃないかなぁ

324 :デフォルトの名無しさん:2009/10/20(火) 21:26:36
てか、ビット数も出現率も分かってるんだから、
理論限界値はシャノンの定理で算出できるだろJK。


325 :デフォルトの名無しさん:2009/10/21(水) 20:18:30
81ビット長
 1が0個 81!/(0!81!)=1 1種    1が1個 81!/(1!80!)=81       1が2個 81!/(2!79!)=3240
 1が3個 81!/(3!78!)=85320    1が4個 81!/(4!77!)=1663740   1が5個 81!/(5!76!)=25621596
 1が6個 81!/(6!75!)=324540216 1が7個 81!/(7!74!)=3477216600 1が8個 81!/(8!73!)=32164253550
32ビット長 4294967296種の表現力 
 81ビット長データを31ビットに圧縮する場合 81ビットの内 1が最大 7 個までならば可能と推測できる
 テーブル引き(辞書検索) なら 出来る が データ量と検索時間から実現は難しい   と思われる

で 連続する 0を特定のビット列に置き変える方法を紹介しときます  ハフマン符号化の亜種
 元データを 0, 10, 11 の三つの状態に変えます 元データの 1は 11になります 
 あとは 連続する0の個数を 0, 10 を使って表現します
  1:0  2:00  3:10  4:000  5:010  6:100
  7:0000  8:0010  9:0100  10:1000  11:1010
  12:00000  13:00010  14:00100  15:01000  16:10000  17:01010  18:10010  19:10100
  20:000000  21:000010  22:000100  23:001000  24:010000  25:100000  26:001010
    27:010010  28:100010  29:010100  30:100100  31:101000  32:101010
  33:0000000  34:0000010  35:0000100 … … 77:00101010  78:01001010  79:10001010
  80:01010010  81:10010010  82:10100010  83:01010100 … …

これで圧縮できるのは
 データ長 81ビット その内 1になるビットは最大 4 個 までなら32ビット長にできます   たぶん

解凍は
 11 が来るか データの最後まで読んだかでビット列を取得
 そのビット列の種類により0の個数を判断しその数分 0を吐く
 11 は 1を吐く

326 :デフォルトの名無しさん:2009/10/21(水) 20:26:03
敬体と常体が入り交じる文章って流行ってるの?


327 :デフォルトの名無しさん:2009/10/21(水) 20:38:18
コピペの継ぎ接ぎを読み過ぎてそのように学習してしまったのでしょう
意味が通じればいい、まさに理系の鏡です

328 : ◆0uxK91AxII :2009/10/21(水) 21:06:14
鑑。

329 :デフォルトの名無しさん:2009/10/21(水) 21:09:51


330 :,,・´∀`・,,)っ-○◎○:2009/10/21(水) 21:27:23
加々見

331 :デフォルトの名無しさん:2009/10/21(水) 21:32:32
今回は高速化数え上げ符号を使いました

332 :デフォルトの名無しさん:2009/10/21(水) 23:58:41
4個でいいなら8bitづつにわけて絶対アドレスでおk。


333 :デフォルトの名無しさん:2009/10/22(木) 01:15:36
>>838
除数をy、商を10000a+1000b+100c+10d+eとする(問題より、b=7)。
(1) 一番下の段で2桁シフトしてるので、10の位d=0
(2) 7をかけて3桁、8か9をかけて4桁なので、除数yは112以上142以下
(3) 3桁の数から7yを引いて3桁、その下の段4桁の数からc*yを引いて2桁。
つまりc>7であるが、少なくとも9yは4桁にならないといけないがc*yは3桁なのでc=8
(4) (3)より、8yは3桁なのでyは112以上124以下
(5) e*yは4桁なのでe=9
(6) a*yは4桁なのでa=9。つまり商は97809
(7) あとは適当に、たとえば124*97809=12128316としてみる。
□にうめる数は、上の行から順に
97809/124,12128316/1116/968/868/1003/992/1116/1116
となり、条件を満たす。

334 :デフォルトの名無しさん:2009/10/22(木) 02:51:54
どこの誤爆なんだろう?

335 :デフォルトの名無しさん:2009/10/22(木) 03:00:18
>>330
だんごってどれが目なの

336 : ◆0uxK91AxII :2009/10/22(木) 03:02:54
´ `

337 :デフォルトの名無しさん:2009/10/22(木) 03:06:04
まじで!
それ眉間のしわで・・が目だと思ってたわ。。。

338 :デフォルトの名無しさん:2009/10/22(木) 03:23:58
・・は、ほっぺのりんごですね

339 :デフォルトの名無しさん:2009/10/22(木) 11:13:42
>337の所為でもうそのようにしか見えない……_/⌒|○

340 :デフォルトの名無しさん:2009/10/22(木) 15:09:03
,, が目とか

341 :デフォルトの名無しさん:2009/10/22(木) 15:11:11
◎が目だろ?

342 :デフォルトの名無しさん:2009/10/23(金) 01:11:37
・∀・)っ-○◎●
,,・´∀`・,,)っ-○◎○
明らかに・が目だろ。,,が頬だから・が頬というのはありえん。´は眉だよね?

343 :デフォルトの名無しさん:2009/10/23(金) 01:59:17
,,・´∀`・,,)っ-○◎○
あぁん?俺のダンゴが食えねえってのか?

344 :デフォルトの名無しさん:2009/10/23(金) 03:12:35
△と□と○なら、おでんですね

345 : ◆0uxK91AxII :2009/10/23(金) 04:41:19
-○◎○

ネギま?

346 :デフォルトの名無しさん:2009/10/23(金) 08:38:50
●は最近品切れ?

347 :デフォルトの名無しさん:2009/10/23(金) 08:50:24
無職になってクレカ審査通らなくなったらしい

348 :デフォルトの名無しさん:2009/10/24(土) 02:22:25
オセロってもう完全回答出たのかな?

349 :デフォルトの名無しさん:2009/10/24(土) 02:30:31
出てないよ

350 :デフォルトの名無しさん:2009/10/24(土) 09:03:46
オセロはいいよな。8x8マスがちょうど64ビットにおさまって。


351 :デフォルトの名無しさん:2009/10/24(土) 09:12:24
一マス保持するのに1.6ビットほど必要だけどな

352 :デフォルトの名無しさん:2009/10/24(土) 09:14:35
オセロのビットボードで1マス2ビット以外の実装はしない

353 :,,・´∀`・,,)っ-○○○:2009/10/24(土) 12:39:01
ビットボード(笑)ってシフトとかややこしくなるのに速いわけないと思ってるんだが


354 :デフォルトの名無しさん:2009/10/24(土) 14:01:31
>>353
このあたりを見てもそう思えるかな?
ttp://www.amy.hi-ho.ne.jp/okuhara/howtoj.htm


355 :デフォルトの名無しさん:2009/10/24(土) 15:04:37
普通シフトはしないよ。
ANDとifの羅列だよ。


356 :デフォルトの名無しさん:2009/10/24(土) 15:15:01
普通は1マス3ビットだろ

357 :デフォルトの名無しさん:2009/10/24(土) 15:22:47
ああ、失礼。

>>354
これに書いてる用途の場合はシフトもするね。
このメリットがあるのはオセロ特有だけど。
一般的にビットボードが使われるのは
盤面を変化させたり戻すのよりも盤面コピー&破棄が速いから。

>>356
オセロでは普通2ビットだよ。


358 :デフォルトの名無しさん:2009/10/24(土) 15:45:54
色以外の情報は何なの?

359 :デフォルトの名無しさん:2009/10/24(土) 15:52:05
空き

360 :デフォルトの名無しさん:2009/10/24(土) 18:31:22
色毎に置ける置けない

361 :デフォルトの名無しさん:2009/10/24(土) 19:07:39
それを持たせるのはどうなの

362 :デフォルトの名無しさん:2009/10/24(土) 19:17:14
常に持たせるのは無駄


363 :,,・´∀`・,,)っ-○○○:2009/10/24(土) 19:19:49
さすがに将棋でビットボードはないよな?


364 :デフォルトの名無しさん:2009/10/24(土) 19:22:20
思いっきりあるよ


365 :,,・´∀`・,,)っ-○○○:2009/10/24(土) 19:27:39
1ワード27ビット×3レジスタくらいかな


366 :デフォルトの名無しさん:2009/10/24(土) 19:37:54
人口無能を用意しない場合でも自動パス位は必要だからね
2ビットに成るか3ビットに成るかの分かれ目はAIの有無

367 :デフォルトの名無しさん:2009/10/24(土) 19:42:27
それはない


368 :デフォルトの名無しさん:2009/10/24(土) 19:49:41
>>365
掛ける7

369 :デフォルトの名無しさん:2009/10/24(土) 19:56:38
だんごさんってこんな人だったっけ。
以前見たレスでは結構賢そうな印象だったけど。
別人なのかな。

370 :デフォルトの名無しさん:2009/10/24(土) 21:01:14
本物のだんごはしばらく見てないと思う

371 :,,・´∀`・,,)っ-○○○:2009/10/24(土) 21:04:04
馬!鹿!団子!だよ

372 :デフォルトの名無しさん:2009/10/25(日) 08:03:00
>>369
前からこんなんだよ。
知ったかぶりしたり大口を叩いたりして自分を不利な状況に追い込んでからの
ディベートを楽しむ人。

373 :デフォルトの名無しさん:2009/10/25(日) 13:02:15
組込み開発だ度で、あまり特殊的ではなく、汎用的に使える
ビット演算をまとめてライブラリ化したいと思うけど、
何をピックアップしたらいいのだろうか?

374 :デフォルトの名無しさん:2009/10/25(日) 14:05:11
あはは、馬鹿だこいつ

375 :デフォルトの名無しさん:2009/10/25(日) 18:58:20
局所的な最適化のためにやるんであって、
変な汎用化をするくらいなら普通に書いてコンパイラに任せなよ

376 :,,・´∀`・,,)っ-○○○:2009/10/25(日) 19:51:18
ここ最近のGCCは賢すぎて小手先のテクはあんま意味無さ過ぎる
やるとしたらアルゴリズムレベルでの再考が必要

>>373
http://bmagic.sourceforge.net/

377 :デフォルトの名無しさん:2009/10/25(日) 20:19:00
>>376
昔のGCCがアホすぎただけだろ?


378 :,,・´∀`・,,)っ-○○○:2009/10/25(日) 20:23:34
そうとも言う

379 :デフォルトの名無しさん:2009/10/25(日) 22:26:51
アホの子のほうがかわいい

380 :デフォルトの名無しさん:2009/10/25(日) 22:33:32
GCCがなかったらプログラマは今頃もっと幸せだったはずだ

381 :デフォルトの名無しさん:2009/10/25(日) 22:37:50
CodeWarrior を使わざるをえなくてもそう思うか!


382 :デフォルトの名無しさん:2009/10/26(月) 09:21:18
現在のGCCでも変数の局所性はあまり生かせてないらしい。

383 :デフォルトの名無しさん:2009/10/26(月) 17:46:10
>>354
外人はビットボードに掛け算を持ち込んでくるからすごいよな

384 :デフォルトの名無しさん:2009/10/26(月) 19:49:15
ビットボードの掛け算って、行列の掛け算みたいな感覚?

385 :デフォルトの名無しさん:2009/10/26(月) 19:51:15
>>383
それ何のための計算?

386 :デフォルトの名無しさん:2009/10/26(月) 21:16:50
>>354
だとttp://www.amy.hi-ho.ne.jp/okuhara/bitmob.c
のimullのことかな?チェスだと
ttp://chessprogramming.wikispaces.com/Sliding+Piece+Attacks
あたりかね?横方向だけじゃなく縦方向や斜め方向の連続したビットを切り出す感じかなぁ

387 :,,・´∀`・,,)っ-○○○:2009/10/26(月) 22:56:56
パイプライニングが職人技すぐる。
現行CPUではAtomでくらいしか役に立たないけど。


388 :デフォルトの名無しさん:2009/10/26(月) 23:18:46
奥原さんって一時期は国内有数のオセロプログラムの作者だったけど
今はもう冷めたのかな
これだけの腕があるのに勿体無い


389 :デフォルトの名無しさん:2009/11/29(日) 19:13:26
>>386
その imull は単純なビット数え上げの一部かな。

cf.http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
>The best method for counting bits in a 32-bit integer v is the following:
>v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
>v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
>c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

これそのまま?


390 :386:2009/11/29(日) 21:45:24
>>389
ごめ、数字の頭が$だったので、16進に見えたw

391 :デフォルトの名無しさん:2009/11/30(月) 09:52:33
頭が $ で16進って、何の表記法だったっけ?

392 :デフォルトの名無しさん:2009/11/30(月) 10:31:40
モステクノロジー6502 だとか、モトローラ系のアセンブラ、
あとは vz のマクロで使う表記だと思ってたよ

393 :デフォルトの名無しさん:2009/12/01(火) 01:08:14
俺はPascalの書き方だと思った

394 :デフォルトの名無しさん:2009/12/24(木) 03:03:00
>>124
キャリーの逆ができる回路ってx86CPUに無いのかな?
x86以外ではこれができるCPUってある?

395 :デフォルトの名無しさん:2009/12/24(木) 03:10:24
>>123のような命令があるとかなり最適化の
幅が広がると気がするんだけどどうなんだろ
あんまり使い道ない?


396 :,,・´∀`・,,)っ-○○○:2009/12/24(木) 04:27:11
そもそもそんなことが要求されるアプリケーションを知らない。
利用頻度の低い回路を実装することほど無駄なものは無いからな。
まあビット逆転なら高速化方法がいくつかあるが


397 :デフォルトの名無しさん:2009/12/24(木) 21:22:36
>>395
強いてよく使われる場を挙げるとなると
高速フーリエ変換 (FFT) のアドレスアクセスで
ビット逆転の1インクリメントが必要になるとこくらいかな。
0000→1000→0100→1100… のように。
これを多用する DSP チップなんかでは多分そういう演算器として実装されてると思うし、
RISC じゃあまり見当たらないかな。
(しかもこの場合アドレスアクセスに使うだけだから
A[0]→A[8]→A[4]→A[12]…というポインタの「先の値」が得られればいいだけだが)

>>123 は当時のタイミングから勝手に想像するに、
オセロの着手判定に使いたかったのではないかと思う。
http://science6.2ch.net/test/read.cgi/sim/1090548999/791-
ちょうどこっちのこの辺の流れで必要になってて、同時期は僕も探してたしね。

この応用範囲を「一般のビット演算での使い道」にまで広げて解釈するとなると、
「並列左端指定付き連続値右端探索」かな。
「Y で指定された複数の set bit に対して、
X の中の set bit が右方向に初めて途切れる場所が
set bit になるようなビット列 Z を求めよ。
(ただし Y は Y & ~X = 0 を満たすものになっているとする)」
ex.
X=000011110000111100001111000011110000
Y=000010000000010000000000000001100000
Z=000000001000000010000000000000001000
これが「左方向に初めて」なら、
Z = (X+Y) & (~Y) と非常に簡単になる。
また、これが「Y での左端指定なし」で全部抜きだすだけならそれはそれで
Z = ~X & (X>>1) と簡単になる。

まあこれがオセロ以外に必要になることは少ないかもしれないね。

398 :,,・´∀`・,,)っ-○○○:2009/12/24(木) 23:18:08
pshufbで各バイト4ビットずつビット逆転するとか

399 :デフォルトの名無しさん:2009/12/26(土) 02:54:55
この命令の回路って実装の手間とか実行のコストは普通の加算命令と同じだよね?


400 :,,・´∀`・,,)っ-○○○:2009/12/26(土) 10:20:35
こういうのは汎用化し辛い。


401 :デフォルトの名無しさん:2009/12/30(水) 02:25:57
だんごさんはFPGAやASICには興味ないの?
既存のCPUで満足なの?

402 :デフォルトの名無しさん:2009/12/30(水) 04:42:59
満足じゃなくたって、まさかCPUは作れないじゃん。

403 :デフォルトの名無しさん:2009/12/30(水) 08:45:18
作れるけど、性能が一昔前なんだな。
たとえばNios II、一般品だとクロックが500M出るのは御の字。

404 :デフォルトの名無しさん:2009/12/30(水) 09:55:37
っつーかFPGAでCPU作ってもメリットあまりないだろ
FPGAはCPU使わずに演算した方が高速

405 :,,・´∀`・,,)っ-○○○:2009/12/30(水) 11:49:39
こんなのよりよっぽど欲しい命令ならいっぱいあるから
D = (A & B) | (B & C) | (C & A)

とかな


406 :デフォルトの名無しさん:2010/01/02(土) 04:06:04
32bit符号なし整数同士の加算でアセンブラを使わずに桁あふれをチェックするいい方法はないでしょうか?
if ( ( x + y ) < x ) {
  ...
}
今のところこれが一番速いのですが

407 :デフォルトの名無しさん:2010/01/02(土) 04:33:19
>>394
キャリー先読みの関係で順序入れ替え回路を挟まざるを得ないと思うけれど、そんなニッチな状況に特化した命令を用意するかどうか…

>>395
だってRISCが持て囃される時代ですもの。

408 :,,・´∀`・,,)っ-○○○:2010/01/03(日) 15:46:51
利用頻度次第じゃね?
FPGAですらFull Adderとかのよく使う回路は固定機能化されてることが多いぞ

まあ利用頻度の低い命令に専用回路を持たないのはある意味正解ではあるのだけど。
Nehalemでpopcntが実装されたのだって意外なことだと思ってるくらいだ。
ちなみにウン千ビットになるとSSSE3を使ったソフトウェア実装の方が速い。

409 :デフォルトの名無しさん:2010/01/03(日) 17:55:23
ウンチビット って何だろうと思ってしまった。

410 :デフォルトの名無しさん:2010/01/03(日) 23:50:21
>>406
普通これって投機的にコンパイルしてくれないんだっけ。
例えば、64 bit 加算を 32 bit 変数 {zH,zL}={xH,xL}+{yH,yL} を計算する時に
zL=xL+yL;
if(zL<yL){
zH=xH+yH;
zH++;
}else{
zH=xH+yH;
}
とすれば zH=xH+yH までは分岐の前にやってくれるとか。

411 :デフォルトの名無しさん:2010/01/08(金) 10:51:26
>410の言いたいことが今一つよく判らんけど、gcc (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)は
void add3(int xh, int xl, int yh, int yl, int * pzh, int * pzl){ int zh, zl;
zl = xl + yl;
if (zl < yl) {
zh = xh + yh;
++zh;
} else {
zh = xh + yh;
}
* pzh = zh; * pzl = zl;
}

_add3:
pushl %ebp
xorl %edx, %edx
movl %esp, %ebp
movl 20(%ebp), %eax
movl 12(%ebp), %ecx
addl %eax, %ecx
cmpl %eax, %ecx
movl 16(%ebp), %eax
setl %dl
addl 8(%ebp), %eax
addl %eax, %edx
movl 24(%ebp), %eax
movl %edx, (%eax)
movl 28(%ebp), %eax
movl %ecx, (%eax)
popl %ebp
ret
とコンパイルした。ちょっと微妙?


412 :デフォルトの名無しさん:2010/01/10(日) 02:30:27
zl = xl+yl;
zh = xh+yh+(zl<yl);
ってことか。割と頭いいな gcc。

413 :デフォルトの名無しさん:2010/01/10(日) 05:53:08
if (zl < xl)
という比較はいらないの?

414 :デフォルトの名無しさん:2010/01/10(日) 13:52:50
Z = mod(X+Y, 2^k)
X+Y<2^k ならば Z>=Y。
対偶をとって
Z<Y ならば X+Y>=2^k。
Z<Y さえ満たせば それで判定OK。

確かに Z<X だけでもよいけど、両方必要というわけでもない。

415 :デフォルトの名無しさん:2010/01/10(日) 14:01:28
>>413
「cmpl %eax, %ecx」で評価して「setl %dl」で評価結果に合わせてゼロまたは1をセットして「addl %eax, %edx」で加算してる。
つまりしっかりと比較してる。
SETccやCMOVccなんかは目立たないけどちゃんと条件みて動作してるからねー
ただ、ホントの所はADCでキャリーごと加算してもらうのが理想だと思うが…
(zl < xl)がxl+ylのキャリーと一致することを予測してもらうのは荷が重いんだろうな。

投機的云々は最適化されすぎて、投機的にやったつもりなのかそうするまでもなかったのか、これではよく分からない。
メモリアクセスを含む命令は意図的に分散されてしまうものだし…

しっかし、AT文法は個人的には読み辛くって嫌だな…

416 :デフォルトの名無しさん:2010/01/10(日) 14:32:13
-masm=intel にして出力しなおしてから読むべし

417 :デフォルトの名無しさん:2010/01/10(日) 22:32:54
ある変数が0かどうかを分岐無しで調べる方法ってありますか?
ビットが全部0なら0、一つでも立っていたら1みたいな感じで。
無理ですかね?

418 :デフォルトの名無しさん:2010/01/10(日) 22:56:18
分岐するより遅いものしか思いつかん


419 :デフォルトの名無しさん:2010/01/10(日) 23:00:12
Cなら!!xでいいんじゃね。gccにコンパイルさせてみたら
xorl  %eax, %eax
setne %al
になったんで十分かと

420 :デフォルトの名無しさん:2010/01/10(日) 23:11:48
>>419
少し速くなりました。
なんか既視感を感じるなと思ったら大昔に自分でそのコードを
書いたのを思い出してしまいました。
どうも退化しているようです。
ありがとうございました。

421 :デフォルトの名無しさん:2010/01/10(日) 23:20:52
xorlとcmplだとcmplの方がレジスタへの書き出しを伴わない分速かったりするのかね?

422 :,,・´∀`・,,)っ-○○○:2010/01/10(日) 23:49:17
うん、ここ最近のx86の実装では条件フラグ更新と汎用レジスタ更新は同時にはできない。
後続の条件フラグ更新命令の検出で演算をキャンセルすることで

でもSandy Bridgeでは両方同時にできるようになる。
具体的に言うとdec + jccもfusionできたりする。

423 :デフォルトの名無しさん:2010/02/01(月) 12:20:57
PN9で生成多項式がX9+X5+1を考えたとき
レジスタの初期値が0x001だった場合、
下のexorした結果の100001000110・・・
が送信するデータになるんでしょうか?
つまり送信するデータ量だけシフトしてexorをとる必要
があるのでしょうか?
シフトレジスタ exor結果
00000|0001 → 1
10000|0000 → 0
01000|0000 → 0
00100|0000 → 0
00010|0000 → 0
00001|0000 → 1
10000|1000 → 0
01000|0100 → 0
00100|0010 → 0
00010|0001 → 1
10001|0000 → 1
11000|1000 → 0

424 :デフォルトの名無しさん:2010/03/07(日) 01:59:17
あげ

425 :デフォルトの名無しさん:2010/03/19(金) 11:30:09
乱数x から [a, b)かつ偶数or奇数の乱数 に写像するビット演算ってどうなりますか?

426 :デフォルトの名無しさん:2010/03/19(金) 13:40:34
偶数or奇数の乱数の意味がわからね
(x%(b-a))+aじゃダメか?

427 : [―{}@{}@{}-] デフォルトの名無しさん:2010/03/19(金) 15:59:35
偶数か奇数か固定したかったら1回左シフトして適宜1をorすればいいと思うよ。

428 :デフォルトの名無しさん:2010/03/19(金) 21:00:19
>>427
なんとなくだけど、左シフトはあんまり
よくない気が。
ANDでLSBを0にするほうがいいと思う。
疑似乱数的に考えて。


429 :デフォルトの名無しさん:2010/03/20(土) 04:38:34
そこは発生器の質に依るだろう

430 :|ω・`):2010/03/20(土) 21:46:15
全ビット詰まってないならシフトした方がいいし
全ビット詰まってて上位ビットほどランダムならシフトしない方がいいし
全ビット詰まってて全ビットがランダムならどっちでもいい

あと>>425はビット演算だけじゃやってらんない
算術必要じゃん、入力になんか仮定を置かないと

431 :デフォルトの名無しさん:2010/03/21(日) 13:41:44
>>429
といっても、そういう期待以上のものは
なかなかないだろうな。


432 :デフォルトの名無しさん:2010/03/24(水) 00:57:27
発生器にも統計的な国際基準の規定があるから一定の質を期待してもいい

433 :,,・´∀`・,,)っ-○○○:2010/04/06(火) 21:21:32
文字通り固定するなら分岐使った方が速いんじゃね?

偶数固定: (n & 0xFFFFFFFE)
奇数固定: (n | 1)


434 :デフォルトの名無しさん:2010/04/07(水) 14:13:21
>>433
偶数固定時にaが奇数かつn=aの場合とか、
奇数固定時にbが奇数かつn=b-1の場合…

435 :デフォルトの名無しさん:2010/05/20(木) 19:09:55
あげ

105 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)