985コメント274KB

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

レス数が950を超えています。1000を超えると書き込みができなくなります。

0001デフォルトの名無しさん

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

0002デフォルトの名無しさん

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);}
より速いのがありそうな気がしてならない

0003デフォルトの名無しさん

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 ] ;

0004デフォルトの名無しさん

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;
}

0005デフォルトの名無しさん

2008/11/10(月) 21:12:23

整数演算だけで高速に平方根を近似したいんだけど、どうすればいい？

0006デフォルトの名無しさん

2008/11/10(月) 22:13:25

良く知られてるあのやり方しか思いつかん。

0007デフォルトの名無しさん

2008/11/11(火) 01:29:17

ああ、あれね。

0008デフォルトの名無しさん

2008/11/11(火) 10:25:57

将棋の盤面をビットボードにしたいんだけど、具体的にどうやったらいいの？

0009デフォルトの名無しさん

2008/11/11(火) 13:33:27

128bit変数のうち、81bitを使う

0010デフォルトの名無しさん

2008/11/11(火) 19:48:41

駒の識別に4bit程必要では？

0011デフォルトの名無しさん

2008/11/11(火) 20:25:26

駒のあるbit、先手のbit、成っているbit、あと歩、香、桂、銀、金、角、飛、王、のそれぞれが81bit有ればいいのでは？＞ビットボード
斜めビットボードもありか？
持ち駒は、どう表現すんのかわかんね。

0012デフォルトの名無しさん

2008/11/12(水) 16:56:20

持ち駒は駒ごとに持ち駒数を表す配列 or 32ビットにパックした整数で十分だろ
ビットボードにする必要はない

0013デフォルトの名無しさん

2008/11/13(木) 21:33:03

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

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

0014,,・´∀｀・,,）っ-●◎○

2008/11/13(木) 21:46:15

>>2
Intelを前提にするならなぜ_bswap()を使わない

0015デフォルトの名無しさん

2008/11/13(木) 21:52:47

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

0016,,・´∀｀・,,）っ-●◎○

2008/11/13(木) 21:54:17

更に6バイト縮んだぜ

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

0017って書けるようにならんもんか

2008/11/13(木) 22:04:50

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

0018,,・´∀｀・,,）っ-●◎○

2008/11/13(木) 22:07:35

>>4
32ビット即値を命令レベルでサポートするのってx86くらいしかないんだよね
定数ロードのオーバーヘッドがかる。
PPCなんかだと16ビットずつならロードできるんだけど。

0019,,・´∀｀・,,）っ-●◎○

2008/11/13(木) 22:10:40

>>17
MSに頼めよ
各エラーを表現するビットが独立してるならこれでいけるんだけどな

if(hr & (DIERR_INPUTLOST | DIERR_NOTACQUIRED))

0020デフォルトの名無しさん

2008/11/13(木) 22:11:12

hrを1回だけにするなら、
switch(hr) {
case DIERR_INPUTLOST:
case DIERR_NOTACQUIRED:
}
だが、ifで書くのより格段に長くなるのと、DIERR_... が整数のときしか
使えない。

0021,,・´∀｀・,,）っ-●◎○

2008/11/13(木) 22:22:48

いっそマクロでもインライン関数でも作れよ

#define EQUAL_OR2(X, N1, N2) (((X) == (N1)) || ((X) == (N2)))

0022デフォルトの名無しさん

2008/11/14(金) 23:05:27

>>18
組込みなら幾らでもあるぞ
有名どころでH8とかTLCS900とか

0023デフォルトの名無しさん

2008/12/08(月) 00:02:32

保守あげ

0024捕手

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]);
}

0025もひとつ捕手

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);
　}
};

0026デフォルトの名無しさん

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;
}

0027デフォルトの名無しさん

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];
}

0028デフォルトの名無しさん

2009/01/03(土) 18:10:41

AVR用なので、コード、メモリサイズともに小さければ可です。
大きなテーブル使うとかは無理です。
すいません。

0029デフォルトの名無しさん

2009/01/03(土) 18:17:42

ソースの文字数とバイナリに変換したサイズは違うと思うが? どうなの?

0030デフォルトの名無しさん

2009/01/03(土) 18:19:12

バイナリ命令文とメモリの合計の最小値ですか

0031デフォルトの名無しさん

2009/01/03(土) 18:21:03

0-9の場合 A-Fの場合　それ以外　で分岐して値を返すのが最小とは思う。

0032デフォルトの名無しさん

2009/01/03(土) 18:30:37

0-9 A-Fしか入力無いとすると、A-Fは6bit目が1であることは利用できそう・
分岐と配列なしで値を返せるとは思うが計算時間の方が掛かる。

0033デフォルトの名無しさん

2009/01/03(土) 18:32:33

小文字の英字は考慮外でいいのか？

0034デフォルトの名無しさん

2009/01/03(土) 18:33:21

文字コードはASCIIでええのん？
それとも別？

0035デフォルトの名無しさん

2009/01/03(土) 18:39:15

>>28
なら、>>26 もしくは >>27 の上側でいいと思う。
(今時のコンパイラなら、ほぼ似たようなコードを吐くはず。)
それ以上を期待するなら、アセンブリコード出して手で最適化。
ただ、最適化する余地はそんなにないと思う。

0036デフォルトの名無しさん

2009/01/03(土) 18:42:18

AVR 用のコンパイラでもそんなに賢いのかしらん？

0037デフォルトの名無しさん

2009/01/03(土) 18:55:24

gccだよ>AVR

0038デフォルトの名無しさん

2009/01/03(土) 18:58:55

なるほろ。そりゃ賢いわ。

0039デフォルトの名無しさん

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);

0040デフォルトの名無しさん

2009/01/03(土) 21:10:10

テーブルも分岐も使わないならこうかな。
h &= ~0x20;
h -= (h > '9') * ('A'-('9'+1));
return h - '0';
乗算があるけど7倍ならコンパイラがよろしくやってくれるだろ。

0041デフォルトの名無しさん

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;

0042デフォルトの名無しさん

2009/01/03(土) 22:58:53

除算が素直に可能ならこれでいいんだがな・・・。

return (h & ~48) % 55;

004341

2009/01/03(土) 23:26:34

あー事前にマスクしなければ1命令減らせた。

unsigned char d = (h >> 4 | h << 4);
d = (d&1)-1 & 9;
h = h+d & 0xF;

>>42
除算がサポートされてても速度が微妙じゃね？
でも格好良いなそれ。

0044デフォルトの名無しさん

2009/01/03(土) 23:29:00

要求はサイズだけだったし。
まあ除算できないから無理なんだけどね・・・。

0045デフォルトの名無しさん

2009/01/03(土) 23:48:54

みなさんありがとうございました。
AVRには乗除算命令は一部のモデルにしかなく、
ない場合はコンパイラが適当に変換するようになっています。

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

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

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

0046デフォルトの名無しさん

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
きちんとスワップされました

0047デフォルトの名無しさん

2009/01/03(土) 23:59:04

unsigned char d = h + 0xC0;
unsigned char e = (d << 4 | d >> 4);
return (9 & ~e) + (h & 15);

これでどうだ？

0048デフォルトの名無しさん

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

0049デフォルトの名無しさん

2009/01/04(日) 00:11:07

ああ、これはひどいな・・・。

0050デフォルトの名無しさん

2009/01/04(日) 00:35:44

もう無理ぽ。
eori さえあれば・・・。

0051デフォルトの名無しさん

2009/01/04(日) 01:00:01

>>40は被乗数が比較の0または1だから、
乗算自体なくなって0か7になるのか。
かしこいな。

0052デフォルトの名無しさん

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;

0053デフォルトの名無しさん

2009/01/04(日) 12:41:25

分岐は気になるけど確かに減るね・・・。

cpi, brvs, subi, andi, ret

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

0054デフォルトの名無しさん

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
すばらしいです。

0055デフォルトの名無しさん

2009/01/04(日) 22:50:41

h &= ~0x20; って必要？

0056デフォルトの名無しさん

2009/01/04(日) 23:43:33

要らないはず。

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

0057デフォルトの名無しさん

2009/01/04(日) 23:46:02

ん、2桁がAに入るわけないな。
まあとにかく、サブルーチン内のわずか先を一度callするやり方、ってことで。

0058デフォルトの名無しさん

2009/01/05(月) 00:56:37

俺はそこで、半桁分変換するのに
DAAだかDADだかのBCD演算用の命令を使って、キャリーをうまく使って
分岐無しにしたような気がした。
どこか探せばあるかもね。

0059デフォルトの名無しさん

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

0060デフォルトの名無しさん

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が無駄のような、必要なような。

0061デフォルトの名無しさん

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;

0062デフォルトの名無しさん

2009/01/27(火) 21:18:44

あげ

0063デフォルトの名無しさん

2009/02/21(土) 23:38:22

あげ

0064デフォルトの名無しさん

2009/02/26(木) 16:00:28

符号なし整数値について、1となっている
ビットのうちで、最下位のビット番号を
求める方法はありますか？

0x00000010 → 1
0x00100000 → 5
みたいな。

1のビット数は任意がいいですけど、
高速なら1ビット限定でもかまいません。

0065デフォルトの名無しさん

2009/02/26(木) 16:22:20

シフトしながらカウントか、テーブル参照かな。

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

0066デフォルトの名無しさん

2009/02/26(木) 16:32:15

すべて、　テーブルにすればいいんじゃない？　　で終わり。

0067デフォルトの名無しさん

2009/02/26(木) 16:46:49

最下位ビットを抜き出して、それから 1 を引いてビットを数える、とか

0068デフォルトの名無しさん

2009/02/26(木) 17:25:41

ハッカーのたのしみp90

0069デフォルトの名無しさん

2009/02/26(木) 20:58:20

これとかhttp://www.nminoru.jp/~nminoru/programming/bitcount.html
あと、CPUによっては命令を持っていることもある。x86のbsfみたいに。

0070デフォルトの名無しさん

2009/02/26(木) 21:45:26

1bit限定なら、前スレにあったテーブル参照での逆算が使えるかもね

0071デフォルトの名無しさん

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];
}

0072デフォルトの名無しさん

2009/02/26(木) 22:58:47

>>69は>>1にあるんだがなぁ…

0073デフォルトの名無しさん

2009/02/27(金) 00:03:32

＞＞71
なんでそんなのがわかるの？
天才ですか？

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

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

0074デフォルトの名無しさん

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];
と同じだよ。

0075デフォルトの名無しさん

2009/02/27(金) 00:33:45

"0123456789"[i%10]
みたいな書き方、
自分で積極的に使う必要は無いが
読めるようになっておく必要はあると思うぞ。

0076デフォルトの名無しさん

2009/02/27(金) 07:28:19

(i%10)["0123456789"]

0077デフォルトの名無しさん

2009/02/27(金) 07:32:13

>>74
同じじゃないだろ
char配列の終端に冗長な0が必要だ

0078デフォルトの名無しさん

2009/02/27(金) 08:06:47

同じだよ。

0079デフォルトの名無しさん

2009/02/27(金) 10:14:24

>>73
組込み系か。
とりあえず「ハッカーのたのしみ」読んどけ。
あと、先輩や同業者が、計算機科学や情報系をバカにするかもしれないが、
話半分に聞いておくこと。

0080デフォルトの名無しさん

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になりますよ、と。ビット溢れによるマスクなども組み合わせているが。

0081デフォルトの名無しさん

2009/02/28(土) 08:23:45

>>78
同じじゃない
実行時のメモリが1バイト冗長だ

0082デフォルトの名無しさん

2009/02/28(土) 08:37:37

大抵は4バイト違ってくるだろうな。

0083デフォルトの名無しさん

2009/02/28(土) 08:42:16

ところが大抵はページサイズで区切られるので、

0084デフォルトの名無しさん

2009/02/28(土) 09:03:18

同じだよ。

0085デフォルトの名無しさん

2009/02/28(土) 09:47:38

似たような感じでNLZはできないものか？

0086デフォルトの名無しさん

2009/02/28(土) 10:08:47

NLZって？

0087デフォルトの名無しさん

2009/02/28(土) 10:13:31

ニュージーランド

0088デフォルトの名無しさん

2009/02/28(土) 13:51:09

Number of Leading Zero だろう。頭からゼロが何個続いてるか数える。
シフトしてって数えるとか、浮動小数点フォーマット変換でとかあるけどあまりスマートな方法がないよね。

0089デフォルトの名無しさん

2009/02/28(土) 14:14:26

ないからわざわざそういう命令があったりするんだろうね。POWERとかだっけ？

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

0090デフォルトの名無しさん

2009/02/28(土) 16:03:40

DSPだと、小数正規化用の命令が使える

0091デフォルトの名無しさん

2009/02/28(土) 16:42:35

体育会系で組込みはまだいるかもしれないが、
体育大学で組込みは希少だよな。日本全国探してもレア？

009264

2009/03/01(日) 21:54:40

レスくれたひと、どーも。

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

0093デフォルトの名無しさん

2009/03/08(日) 10:14:52

あげ

0094デフォルトの名無しさん

2009/03/13(金) 05:58:26

1つかまたは0個のビットが立っている時に何番目のビットが立っているか。(上からでも下からでも、より速い方)

お願いします。

0095デフォルトの名無しさん

2009/03/13(金) 06:05:16

すぐ上にありました。すみません。

0096デフォルトの名無しさん

2009/03/20(金) 21:41:48

2進数や16進数の為の代数学とか無いのかな？
例えば32bit符号付き整数の絶対値を求める式を、定理を使って単純に変形するだけで、
andとかshiftとかmulみたいな単純な操作のみで構成された式に変形できる公理系とかそういうの

x < 0 ? -x : x
={なんか、分岐の融合法則とかそういうの}
(n ^ (n >> 31)) - (n >> 31)

こういう等式変換の形でアルゴリズムを計算でできれば、
勘だけではできないときに色々と役立つんじゃないかなーと思うだけど
つーか絶対ある筈なんだけど、俺はそういう噂すら知らないんで

0097デフォルトの名無しさん

2009/03/20(金) 22:39:46

合同式のことかと思ったが、もっと低レベルな話みたいだ。
ビット演算で絶対値を求めたいなら、２の補数を調べるといい。
2進数とか16進数を難しいと思ってるかもしれないが、他の人は誰も
そう思ってないから。

009896

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はその常識をまとめてあったり、こういう演算の性質について
群とかそういった代数学の概念での議論とかが載ってる文献などありませんかという意味でした

0099デフォルトの名無しさん

2009/03/25(水) 04:25:32

右シフトが論理シフトだったら
(n^-(n>>31))+(n>>31)
かな？

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

0100デフォルトの名無しさん

2009/03/25(水) 04:27:42

nが1の補数だったら
n<0?~n:n
→n<0?n^-1:n^0
→n^(n>>31)
かな。

0101デフォルトの名無しさん

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)))

0102デフォルトの名無しさん

2009/03/25(水) 04:39:43

x<0?y:y+z
→y+(z&(x>>31))

0103デフォルトの名無しさん

2009/03/25(水) 05:50:18

条件式使うならビットシフトまで落とす意味ない。

0104デフォルトの名無しさん

2009/03/26(木) 18:53:33

3項演算子を使うとx86だと式の計算以外に少なくとも3～4クロック余計にかかるから、
他で4クロック以上重くなるというのでなければビットシフトまで落とす意味は十分にある。

0105デフォルトの名無しさん

2009/03/26(木) 19:34:12

ジャンプはvだということを考慮すると2～4クロックだぞ。

0106,,・´∀｀・,,）っ-○◎●

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

0107,,・´∀｀・,,）っ-○◎●

2009/03/26(木) 19:45:46

もしくはこうかｗ

y + srl(x, 31) * z

0108デフォルトの名無しさん

2009/03/26(木) 20:08:02

いや、それは逆に遅くならないか？
cmov系はフラグが確定するまで待機するから。

0109108

2009/03/26(木) 20:08:44

>>107
それはないｗ

0110,,・´∀｀・,,）っ-○◎●

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

どうみてもネタです。本当にありがとうございました。

0111デフォルトの名無しさん

2009/04/18(土) 06:06:04

0112デフォルトの名無しさん

2009/04/28(火) 19:50:17

ほしゅ

0113ほしゅ

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

0114,,・´∀｀・,,）っ-○○○

2009/05/15(金) 20:53:01

BCD演算ってそもそも遅くね？

0115デフォルトの名無しさん

2009/05/15(金) 22:00:47

あんまり変わらなかった

0116デフォルトの名無しさん

2009/05/17(日) 23:45:35

これさ、○○与えると△△返すビット演算教えてください、みたいな感じで
それに人間が答えてるけどさ、
一般的に反復深化の自動計算でビット演算はじき出すフリーソフトとかないんだっけ？

0117デフォルトの名無しさん

2009/05/17(日) 23:49:36

反復深化？

0118,,・´∀｀・,,）っ-○○○

2009/05/18(月) 00:15:38

サブネットマスクでも計算するの？

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

0119,,・´∀｀・,,）っ-○○○

2009/05/18(月) 00:17:55

tmkk氏がBerkeleyのSISってツールがあるって言ってたな

0120デフォルトの名無しさん

2009/05/19(火) 02:55:16

記憶が正しければ、今はBCD系はMMX系統の余った回路使って演算してる筈。

0121,,・´∀｀・,,）っ-○○○

2009/05/19(火) 03:53:50

ないない。
BCDって64ビットで無効命令だぜ？
Core 2あたりで除算回路そのものが高速化されてるあたり、IDIVと同じようなことやってんだろ

0122デフォルトの名無しさん

2009/05/24(日) 21:17:29

あ

0123デフォルトの名無しさん

2009/05/29(金) 06:15:50

//INVERSEはビットの左右を反転する処理
c = INVERSE(a);
d = INVERSE(b);
e = c + d;
f = INVERSE(e);

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

0124,,・´∀｀・,,）っ-○○○

2009/05/29(金) 07:25:25

キャリーの逆ができる回路があるならな。

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

0125デフォルトの名無しさん

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;
}

0126,,・´∀｀・,,）っ-○○○

2009/05/31(日) 10:47:55

ARMとかならアンロールしてプレディケートすれば上手い具合に分岐除去できるな

0127デフォルトの名無しさん

2009/06/06(土) 18:55:12

>>124
a+b = (a^b) + ((a&b)<<1)
の間違い？

0128,,・´∀｀・,,）っ-○○○

2009/06/12(金) 01:37:04

>>127
そーでしたorz

0129デフォルトの名無しさん

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;

0130 ◆0uxK91AxII

2009/06/20(土) 17:41:04

>>129
a = *((unsigned char *)&c+3);
以下略。

0131デフォルトの名無しさん

2009/06/21(日) 00:01:18

エンディアン依存のコードはお行儀悪いんじゃなかった？

0132 ◆0uxK91AxII

2009/06/21(日) 08:04:17

ぐはぁ。

0133デフォルトの名無しさん

2009/06/30(火) 01:49:31

>>123
本質的に難しいね
通常の加算の出力の MSB が入力の全ビットに依存するところを
加算命令が全部１命令でやってるわけで、
その左右反転の LSB が入力の全ビットに依存するような演算はバラすと結構かかる。

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

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

0134133

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

0135133

2009/06/30(火) 03:42:52

>>134
訂正
b[i] = (c<<1 & a[i]) >= 3;
↓
b[i] = (c<<1 | a[i]) >= 3;

0136デフォルトの名無しさん

2009/07/01(水) 13:27:12

>>123
難しい
無理な気がする

0137デフォルトの名無しさん

2009/07/01(水) 20:33:21

おいおい、どうして>>125を無視する
inverseせずに出来てるじゃないか

0138デフォルトの名無しさん

2009/07/01(水) 20:50:37

ああ、ごめん
無視してないよ
コードも実行してみたよ
>>125よりいいのを考えてて思いつかなかった

0139デフォルトの名無しさん

2009/07/02(木) 02:33:25

>>125 は面白くていいんだけど
ちょっと最悪計算量が大きくない？
0x00000001 = reverse_add(0x80000000, 0xFFFFFFFE) とか。
64ビットとかだったら64回くらいループしそうだし。

0140デフォルトの名無しさん

2009/07/05(日) 21:53:38

>>116
そんなソフトあるんか・・・世界は広いな

0141デフォルトの名無しさん

2009/07/06(月) 18:55:03

60で割った余りが0かどうか調べるにはどうすればいい？

0142デフォルトの名無しさん

2009/07/06(月) 19:20:07

60で引いていって60以下になったらそれが答えです

0143デフォルトの名無しさん

2009/07/06(月) 19:54:13

以下じゃなくて未満ですた

0144デフォルトの名無しさん

2009/07/06(月) 20:01:13

if(0 == (n + 4) >> 6)
{
}

0145デフォルトの名無しさん

2009/07/06(月) 20:58:51

>>144
nを60にしても1なんですけどー

0146デフォルトの名無しさん

2009/07/07(火) 03:43:18

>>141 if( (n%60) ) { ０じゃないほう } else { ０のほう }
％は言語によって MOD とかもある。

0147デフォルトの名無しさん

2009/07/07(火) 04:08:05

え、マジで言ってる？
このスレの住人にも不可能なの？

0148,,・´∀｀・,,）っ-○○○

2009/07/07(火) 20:47:14

分岐のオーバーヘッドは高くないと仮定して、除算の平均回数を減らすほうがいいだろ

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

0149デフォルトの名無しさん

2009/07/08(水) 00:49:59

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56
の時だけ割り算か。1/4になったね。
4の倍数に注目したらもうちょっとなんとかならない？

0150デフォルトの名無しさん

2009/07/08(水) 00:52:29

>>148
if(n & 3) return 0;
x=((n>>2)*0x01111111)>>12;
return !x || x==0xf;

まあ掛け算で桁あふれのない n<16444 どまりだけどね。

0151150

2009/07/08(水) 01:14:43

x=(((n>>2)*0x01111111)>>12 & 0xf);
& 0xf を忘れてた

0152デフォルトの名無しさん

2009/07/08(水) 02:54:49

すげー乗算になってさっぱり判らん

0153デフォルトの名無しさん

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では微妙かもな。
まだ最適化できる気がするが飽きた。

0154153

2009/07/08(水) 03:19:13

エラーで>>150の投稿に気づかなかった・・・
まぁこっちもビット数の制限がゆるいって利点はあるか

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

0155デフォルトの名無しさん

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;
}

0156デフォルトの名無しさん

2009/07/09(木) 03:40:25

sprintf(buf,"%d",(int)n) を実装したいわけね。
小さくしたいなら、百の位からforループで回すべき。早くしたいなら、百の位を処理した後の
forループは1，2回しか回らないのだから、ifのがいい。bufの頭は呼び出し側で知っている
のだから、そこを返すのはムダだと思う。呼び出し側で役に立つ情報：文字列長を返すとか、
末尾nullをつけてｃ標準の文字列にしておいたほうがいい。

0157デフォルトの名無しさん

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;
}

0158デフォルトの名無しさん

2009/07/09(木) 21:50:37

それだと他のbitにする場合もcolumnsや型を調整するだけで楽ですね。

0159デフォルトの名無しさん

2009/07/11(土) 17:59:06

今更だけど

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

0160デフォルトの名無しさん

2009/07/12(日) 01:22:15

>>159
クロック計測はもうムリゲじゃ・・・？

0161154

2009/07/12(日) 01:47:25

>>159
>>150-151の部分を最適化してるんだよな？
n>>=2;
x=(n+(n<<4));
n=(n<<24)+(x<<16)+(x<<8)+x;
x=(n>>12 & 0xf);
自分はこれが精一杯で、命令数調べるのが面倒だったからコンパイルしたら吹いたｗｗｗ
最適化切るとregister指定に関係なくスタック使うわ、最適化すると乗算命令に戻るわｗｗ
乗算の展開は乗除命令を持たないCPUでないとあんまり意味が無いって示唆なのかね？

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

0162154

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;

0163デフォルトの名無しさん

2009/07/12(日) 15:41:36

ビット演算は面白いし頭の体操になるし高速化することも多いけど
可読性は馬鹿みたいに低下するよね。

ビット演算を使うことで可読性があがって保守性が高まるいい例ってあるかな。

0164デフォルトの名無しさん

2009/07/12(日) 15:59:57

適切なコメントをつける。

0165デフォルトの名無しさん

2009/07/13(月) 01:06:27

2^N単位の切り上げ処理とか

X=(X+3)&~3;

0166デフォルトの名無しさん

2009/07/13(月) 01:12:55

式の中にＮがないのにワロタ。

0167デフォルトの名無しさん

2009/07/13(月) 04:13:17

>>163
いっぱいありすぎて書けない

0168デフォルトの名無しさん

2009/07/13(月) 07:59:56

思いつくだけ片っ端から書いてみて

0169デフォルトの名無しさん

2009/07/13(月) 08:37:16

30で割った余りを調べるどうする？

0170デフォルトの名無しさん

2009/07/13(月) 08:47:36

日本語でOK

0171デフォルトの名無しさん

2009/07/13(月) 09:21:09

海の水はどうしてですか？

0172デフォルトの名無しさん

2009/07/13(月) 20:39:25

>>171
浸透圧がでてこないから

0173デフォルトの名無しさん

2009/07/13(月) 21:12:18

>>167
書いてもいいですよ

0174デフォルトの名無しさん

2009/07/13(月) 23:46:18

>>169
30で引いていって、30で引けなくなったらそれが余りです

0175デフォルトの名無しさん

2009/07/14(火) 01:02:12

>>169
30進数表記に変換したときの一の位の数字をみる

0176デフォルトの名無しさん

2009/07/14(火) 02:29:17

おまいらすごいな。やっぱりアセンブラ経験がかなりあるおっさんが多い？

0177デフォルトの名無しさん

2009/07/14(火) 03:45:31

1969年からPGやってたからな。その頃は業務用のﾌﾟﾛｸﾞﾗﾑでもASM必須。
ﾃﾞｰﾀﾍﾞｰｽ使って部品展開とか組むのにﾒﾓﾘ48KBとか52KBだもん。

0178 ◆0uxK91AxII

2009/07/14(火) 12:09:18

スレ違いも、度が過ぎる。

>>174
無限ループだね。

0179デフォルトの名無しさん

2009/07/14(火) 12:16:26

ここの人たちは何読んで勉強したの
the art of computer programming
ハッカーのたのしみ
Intel/AMDの最適化マニュアル
以外だと

0180デフォルトの名無しさん

2009/07/14(火) 21:29:50

計算機プログラムの構造と解釈
とかじゃないか？

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

0181デフォルトの名無しさん

2009/07/14(火) 21:39:11

その本全然ビット演算は関係ない
関係あるとしたら伝播遅延を含んだ論理回路設計の章があるけど
練習問題でもリップルキャリー加算器を作るまでで
ビット処理のテクニック的なことはほとんど出てこない
ただ、5章は未読なので知らん

0182デフォルトの名無しさん

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

0183デフォルトの名無しさん

2009/07/14(火) 22:22:11

http://www.amazon.co.jp/dp/4839909865

0184デフォルトの名無しさん

2009/07/14(火) 22:23:41

>179
256倍シリーズとか。エキスパートCプログラミングとか。

0185デフォルトの名無しさん

2009/07/14(火) 22:54:40

256は知らんが、エキスパート(略はビット演算に関することは少ししか
無かったと思う。やはり昔のアセンブリメインの時代に習得したのか？

0186デフォルトの名無しさん

2009/07/14(火) 23:33:26

俺はZ80マシン語秘伝の書を読んだ。

0187デフォルトの名無しさん

2009/07/15(水) 00:32:09

>>166
例として2を代入したんだが、気づいてくれよ・・・
X=(X+(pow(2,N)-1))&~(pow(2,N)-1);

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

0188デフォルトの名無しさん

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

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

0189デフォルトの名無しさん

2009/07/15(水) 11:38:16

(Z80|8086)マシン語秘伝の書は、機械語的のTipsの本で、ハッカーズディライトにあるような
高度(?)なビット演算の技は出てこない。

0190デフォルトの名無しさん

2009/07/15(水) 14:39:51

The Art of Computer Programming.

0191デフォルトの名無しさん

2009/07/15(水) 18:50:51

>>189
あの頃だと、下手にビット演算するよりも、
如何に効率の良いテーブル参照をできるかが勝負だった気がする。

0192デフォルトの名無しさん

2009/07/16(木) 10:42:27

メモリは少ないけど、アクセスのペナルティは小さかったからな。

0193デフォルトの名無しさん

2009/07/16(木) 19:00:25

>>192
つか、ペナルティだらけだったな。
今から考えると。

0194,,・´∀｀・,,）っ-○○○

2009/07/17(金) 23:26:58

>>179
やぱ、へるみ氏の掲示板じゃね？

0195デフォルトの名無しさん

2009/07/30(木) 00:38:12

>>141 60 で割り切れるか

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

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

0196デフォルトの名無しさん

2009/07/30(木) 02:26:43

mulがなかったらどうするの

0197デフォルトの名無しさん

2009/07/30(木) 12:38:51

このスレ…とんでもないノネナール臭がする…

0198デフォルトの名無しさん

2009/07/30(木) 13:26:35

シトロネラール臭もする

0199,,・´∀｀・,,）っ-○○○

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:

0200,,・´∀｀・,,）っ-○○○

2009/07/30(木) 20:52:41

変なところにtest eax, 3がorz

0201デフォルトの名無しさん

2009/07/30(木) 22:53:38

団子さんってどんな仕事してるの？

0202,,・´∀｀・,,）っ-○○○

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
刺身の上にタンポポを（ｒｙ

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

0203デフォルトの名無しさん

2009/07/30(木) 23:05:11

ていうか、話題自体の内容はなかなか面白いんだが
元質問者の>>141は既に居ない可能性が。

0204,,・´∀｀・,,）っ-○○○

2009/07/30(木) 23:11:34

このスレはアスペ・ADHDが多いからそんなことどうでもいいんだ。

0205デフォルトの名無しさん

2009/07/30(木) 23:14:51

>>202
なるほど。それは才能の無駄使いのような。
昔はローレベルなことをやってたとか？

0206デフォルトの名無しさん

2009/07/30(木) 23:20:15

フィクスターズにとらばーゆとか考えないの？

0207,,・´∀｀・,,）っ-○○○

2009/07/31(金) 18:19:15

俺をスカウトしてみてよ＞ふぃく☆すたの中の人

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

0208デフォルトの名無しさん

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;
　　}
　}
}

0209,,・´∀｀・,,）っ-○○○

2009/07/31(金) 19:05:54

PMOVMSKB

0210デフォルトの名無しさん

2009/07/31(金) 19:06:10

>>208
if文の存在が分からない。
単純に元のビットをシフトしながら８本分合成していけばいいんでないの？

0211,,・´∀｀・,,）っ-○○◎

2009/07/31(金) 19:11:21

Hacker's Delightのtranspose.cがそのまんま答えだな

0212デフォルトの名無しさん

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;
　}
}
これ以上は無理でしょうか。

0213デフォルトの名無しさん

2009/07/31(金) 19:27:22

>>211
http://www.hackersdelight.org/HDcode/transpose8.c
を見るとループを展開したりバイト列をlongにまとめたりするだけで
同じものみたいですね。
その本は面白そうなので買ってみます。
ありがとうございました。

0214デフォルトの名無しさん

2009/07/31(金) 19:27:22

なんでstream[]もbyteもシフトするの？
なんで1でアンド取るの？

0215デフォルトの名無しさん

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);
}

0216デフォルトの名無しさん

2009/07/31(金) 19:53:05

なんだw　先に答え出てるじゃんw
最後はなんでるーぷするのって硫黄と思ってたのにw

0217デフォルトの名無しさん

2009/07/31(金) 19:53:35

あ、streamの添字が逆でした7→0

0218デフォルトの名無しさん

2009/07/31(金) 19:58:36

中間を全部レジスタでできるから展開はできるだけした方が速いのでしょうね。
コード量と相談ですね。
ありがとうございました。

0219デフォルトの名無しさん

2009/07/31(金) 23:27:06

いいえ、ループの(単純な)展開は人間がやるべきじゃありません。

0220デフォルトの名無しさん

2009/07/31(金) 23:56:47

1ビットずつしかシフトできない環境では使えないな

0221デフォルトの名無しさん

2009/08/01(土) 00:31:32

これで８バイト単位での入力が仕様なら、固定の方が早いと思う。

0222デフォルトの名無しさん

2009/08/01(土) 00:32:30

あ、でもマシンコードのキャッシュとかまで考えると、どっちが早いんだろ。
ループと、展開

0223デフォルトの名無しさん

2009/08/01(土) 00:42:46

あまりに初歩的すぎて突っ込むべきかどうか悩んだが、
「　計　測　し　ろ　」

0224デフォルトの名無しさん

2009/08/01(土) 01:13:18

コンパイラ性能で異なるから計測しても意味無いだろうな。

0225デフォルトの名無しさん

2009/08/01(土) 01:17:07

そんな理由で意味がないというなら、議論そのものに意味がないだろ。

0226デフォルトの名無しさん

2009/08/01(土) 01:33:44

むしろCPUとかプラットフォームの違いの差が大きいだろう
実際に使う人が実際に使う環境で計測すりゃいいんだよ。

0227デフォルトの名無しさん

2009/08/01(土) 01:41:11

つっても最近はループまで最適化するからな・・・コンパイラ。
CPU向けに分岐のヒントつける場合も有るんだっけ？

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

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

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

0228デフォルトの名無しさん

2009/08/01(土) 01:50:51

　　　　　　　　　　　 ,　-‐;ｚ..__　　　　　＿丿
　　　　　　　／￣ﾞヽ′　ﾆ‐- 、＼　　＼　　　ところがどっこい
　　　　　　　Ｚ´// ,ﾍ.∧ ヽ　＼ヽ　ゝ　　ヽ　　　‥‥‥‥
　　　　　　　/, / ,ﾘ　 vﾍｌヽ＼ヽヽ.|　　ノ　　最新のPCじゃありません
　　　　　　　/ｲﾙ_-､ij~　ﾊにヽ,,＼`|　＜　　　　　　‥‥‥‥！
.　　　　　　　 N⌒ヽヽ　/／￣ﾘ:| l l |　　｀)
　　　　　　ﾄ､_e.〉u ' ｅ_ ノﾉ |.l l |　 ∠.　　　現実です
　　　　　　　　 |､＜､ ij　_,¨､イ||ト､| 　　ヽ　　　　　　‥‥‥！
.　　　　　　　 |ドｴｴエ「-┴''´|.|L八　　　ﾉ -､　　　これが現実‥！
　　　　　　　 l.ﾋ_ー-r-ー'スｿ | l トゝ､.__　　 | ,. - ､
　　　　_,,.　-‐ ''"ﾄヽｴｴｴエ!ゝ'´.ｲ i l;;;;:::::::::::`::ｰ/
　　　ﾊ:::::::::::::::::::::| l＼ｰ一_v~'´ j　,1;;;;;;:::::::::::::::::::
.　　/:::;l::::::::::::::::::::;W1;;;下、　／lﾙ' !;;;;;;;;;::::::::::::::::
　 /:::::;;;ｌ:::::::::::::::::;;;;;;;;;;;;;;;|: :Ｘ: : : : : |;;;;;;;;;;;;;;::::::::::::
　/:::::;;;;;;|:::::::::::::::;;;;;;;;;;;;;;;;|/: : >､: : :|;;;;;;;;;;;;;;;:::::::::::

0229デフォルトの名無しさん

2009/08/01(土) 03:59:10

だから、コンパイラに判断させればいいっての。
コンパイラが適切に展開できないことが判ってから初めて人手で展開すればいい。

0230,,・´∀｀・,,）っ-○○○

2009/08/01(土) 05:19:20

たとえばさ、8x8ビットをひっくり返すくらいだったらさ
テーブル使ったっていいんだぜ
出力先の配列が連続ならな

0231デフォルトの名無しさん

2009/08/01(土) 16:13:32

オンドゥル語を符号に使えないでしょうか

0232デフォルトの名無しさん

2009/08/01(土) 17:25:57

ｳﾂﾞﾀﾞﾄﾞﾝﾄﾞｺﾄﾞｰﾝ!!

0233デフォルトの名無しさん

2009/08/01(土) 17:30:07

最上位ビットで最上位からnビット分埋める
ってのを格好よく書きたいんだけどうまくいかない。
0b10000000 で n=3 なら 0b11100000 にするみたいな感じで。

0234デフォルトの名無しさん

2009/08/01(土) 18:30:51

x | ~((1 << (8-n)) -1) みたいな感じか

0235デフォルトの名無しさん

2009/08/02(日) 03:12:48

ｃでsignedなら算術シフトになるんじゃなかったかな。
ASMなら、論理シフトしかなくても、キャリーを立てておいてキャリーごとローテートで。

0236デフォルトの名無しさん

2009/08/02(日) 04:09:21

とりあえず、
符号付整数型の負値の算術右シフトの結果がどうなるか(符号をどう扱うか)は処理系定義なので、
それを仮定して依存するコードを書いてはいけない。

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

0237デフォルトの名無しさん

2009/08/02(日) 05:10:10

それなら、32bitでも３２個のﾃｰﾌﾞﾙでいいんだから、mask[]={0,0x80000000,0xC0000000,・・・
0xFFFFFFFE,0xFFFFFFFF } を用意して、x |= mask[n]; でいいじゃん。

0238デフォルトの名無しさん

2009/08/02(日) 05:14:14

>>234 == >>237 == baka

0239デフォルトの名無しさん

2009/08/02(日) 11:27:54

>> 236
算術右シフトを使うときは
#if ((-1)>>1)!=0
#error
#endif
と書いてるよ

0240デフォルトの名無しさん

2009/08/02(日) 11:29:01

>>239 訂正
#if ((-1)>>1)!=-1
#error
#endif

0241デフォルトの名無しさん

2009/08/02(日) 13:28:13

0-(0x80000000>>(n-1))
か？

0242 ◆0uxK91AxII

2009/08/02(日) 13:36:46

0b01011000 で n=4 なら 0b00001000
とか、有り得そうな雰囲気。

0243デフォルトの名無しさん

2009/08/02(日) 13:39:16

なんでこんなあほばっかりなんだここは？

0244あほ

2009/08/02(日) 14:08:27

>>243
なら君が有無を言わせぬ明快なレスであほを黙らせてくれ。

0245デフォルトの名無しさん

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倍以上は掛かる。

0246デフォルトの名無しさん

2009/08/02(日) 14:57:25

キャリーを使えば7ビットシフトは3クロック
C←レジスタ 1
レジスタクリア 1
レジスタ←C 1

0247デフォルトの名無しさん

2009/08/02(日) 15:00:46

ヒント:夏休み

0248233

2009/08/02(日) 21:34:48

言葉が足りないようですまなかたですが、マスクを望んでます。
>>242みたいな感じで。

0249デフォルトの名無しさん

2009/08/02(日) 22:34:05

マスクか。
ビット列の長さにも寄るけれど、それほど長い単位でなければ、簡単かつ見通しがいいのはテーブル参照だろう。

0250デフォルトの名無しさん

2009/08/02(日) 22:54:56

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

0251233

2009/08/03(月) 03:48:50

-4096～4095の整数に落とし込みたいとか、そういうのがやりたくて
符号をほしいところまでうにょ～んと延ばしたら出来るかも！と
思ったんだス。
変な思考でごめん。

0252デフォルトの名無しさん

2009/08/03(月) 04:24:27

>>250
つ簡単かつ見通しがいいのは

0253デフォルトの名無しさん

2009/08/03(月) 04:44:59

>>251
算術シフト・・・

0254デフォルトの名無しさん

2009/08/03(月) 04:53:04

>>252 そういうのは、別の(普通の)スレ向き。
このスレで(多数に)求められているのは、可読性を落としてでも1clock削ること。

0255デフォルトの名無しさん

2009/08/03(月) 08:29:25

たとえば３ビットシフトと４ビットシフトで所要クロック数は変わりますか？

0256デフォルトの名無しさん

2009/08/03(月) 09:10:11

変わるプロセッサもある。
例えば、8086や80286は変わる。

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

0257,,・´∀｀・,,）っ-○○○

2009/08/03(月) 21:31:57

Pentium 4って4ビットの左シフトやるならこれやった方が速かったよな

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

0258デフォルトの名無しさん

2009/08/03(月) 22:32:13

なんかぐぐったら2006年頃のダンゴも同じ事言ってた

0259,,・´∀｀・,,）っ-○○○

2009/08/04(火) 07:32:09

Pen4の倍速ALUは上位と下位16ビットを0.5クロックずらして伝播する。
整数加減算は1クロックに2回実行出来てアホみたいに得意だがシフトが苦手。

0260デフォルトの名無しさん

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じゃなくても正負が戻ればいいです)
昔どこかで見たような気がしたので。

0261デフォルトの名無しさん

2009/08/06(木) 15:59:47

引き算しる
0ならループ

0262デフォルトの名無しさん

2009/08/06(木) 18:52:16

4byteごとに比較して、同じ時はすぐ次
ってのは、alignあってないとだめ？

0263デフォルトの名無しさん

2009/08/06(木) 19:08:09

>>262
CPU、またはその設定による。

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

0264デフォルトの名無しさん

2009/08/06(木) 19:35:03

>>262
CPUに依存しそうな質問するなら使ってるCPUくらい書けよ

0265デフォルトの名無しさん

2009/08/07(金) 17:34:45

>>262
CPUによっては跨いだ時点で例外が飛ぶ

0266デフォルトの名無しさん

2009/08/07(金) 19:02:29

昔のLISPはLSBが無視されるのを利用してタグに使ってた

0267,,・´∀｀・,,）っ-○○○

2009/08/07(金) 19:40:45

アラインメント制約の比較的緩いx86ですらページ境界跨ぎの問題があるからな

0268デフォルトの名無しさん

2009/08/07(金) 19:41:01

>>266
いまでもそうだが, ネイティブコンパイルする処理系…
car とか cadr とか elis とかのバイトコードなマシンは MSB 側に
tag 持ってるような気が…

0269デフォルトの名無しさん

2009/08/07(金) 20:21:31

例えば24bitで16Mセルしか使わないと見積もれば、残り8bitがタグとして使える。
ここで言ってる話はマスクが必要ないということだろう。

0270デフォルトの名無しさん

2009/08/07(金) 22:23:10

逆にarmみたいなAlignきつい奴って
byte pointerのインクリメントってどうやってんの？

0271デフォルトの名無しさん

2009/08/07(金) 22:34:12

>>269
(初代)68000マシンとかであったな。

0272デフォルトの名無しさん

2009/08/08(土) 14:14:00

>>270
ARMでもアドレスはバイト単位なんだから、ポインタ計算時には気にしなくて良いよ。
メモリアクセスするときには下位ビットをマスクすればOK。
下位ビット値からマスクやシフトの計算して任意のバイトにアクセスする。

0273デフォルトの名無しさん

2009/08/08(土) 22:08:18

250みたいなのは、両方のアラインメントで場合分けすると
えーと、何通りにすればいいんだ
４バイトだと9通り？

0274デフォルトの名無しさん

2009/09/15(火) 20:04:58

ビット演算の本格的素養を身につけるには
どんなドキュンメントを参照するべきですか？

0275デフォルトの名無しさん

2009/09/15(火) 20:55:30

>>274
カーニハン＆リッチー

0276デフォルトの名無しさん

2009/09/16(水) 07:44:51

そうなのか
本格的とか書いてあるから74シリーズのデータシートでも見せるべきなのかと思った

0277デフォルトの名無しさん

2009/09/16(水) 08:13:01

74シリーズのデータシート見てもカルノー図は書けるようにならないぞ

0278,,・´∀｀・,,）っ-○○○

2009/09/19(土) 00:33:39

クヌースと墓寺

0279デフォルトの名無しさん

2009/09/21(月) 21:40:06

枕好き法

0280デフォルトの名無しさん

2009/10/18(日) 22:27:25

今日一日悩んだが決定打が見つからず。
だれかアドバイスくだしあ。

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

0281280

2009/10/18(日) 22:41:00

>アプリケーション上の制約から81ビットのうち値が１になるビットは高々15個である。

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

0282デフォルトの名無しさん

2009/10/18(日) 23:56:13

１．81ビットの先頭から0をカウントする
２．16個カウントするか、1が出てきたら、個数を4bitで吐き出す
３．最後まで繰り返して81ビット端まで言ったら、残りは0でパディング

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

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

早い実装は誰かに任せた

0283デフォルトの名無しさん

2009/10/19(月) 00:03:03

11...1100...001 はどうなるの

0284デフォルトの名無しさん

2009/10/19(月) 00:13:03

カウントを15個ずつにすれば何とかなると思ったが
最悪80ビットになるな

0285デフォルトの名無しさん

2009/10/19(月) 00:14:27

81ビットの先頭から見ていって、
1が出てきたら11を吐き出す、
01が出てきたら10を吐き出す、
00が出てきたら0を吐き出す。

これじゃだめかね。

0286デフォルトの名無しさん

2009/10/19(月) 00:31:08

将棋の何の条件だろう

0287280

2009/10/19(月) 00:35:48

>>285
おお、仕様も満たすし速度的にも完璧です。
ありがとうございます。

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

0288デフォルトの名無しさん

2009/10/19(月) 00:47:32

>>282
あいぢあはそれでいい
16個連続してたときの扱いにバグが有りそう
平均で連続するのは4個か5個だから16分割4bitだともったいない
huffmanとか出現頻度で長さが変わるコードにすれば
もっと圧縮できると思うけど
そのテーブルを81bitに含めるかどうかでも変わってくる

0289デフォルトの名無しさん

2009/10/19(月) 01:05:30

81ビット中、1は15個、0は66個

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

0290デフォルトの名無しさん

2009/10/19(月) 04:55:00

81ビットの先頭から見ていって、
1が出てきたら111を吐き出す、
01が出てきたら110を吐き出す、
001が出てきたら10を吐き出す、
000が出てきたら0を吐き出す。

0291デフォルトの名無しさん

2009/10/19(月) 08:53:42

それ先頭に1が15連続したとき 3*15 + (81-15)/3 = 67
15個の場合すら未クリアで>>285に劣るようだけども

0292デフォルトの名無しさん

2009/10/19(月) 09:07:19

と思ったら1→10 001→111 で解決するな

0293デフォルトの名無しさん

2009/10/19(月) 11:37:58

81ビットの先頭から見ていって、
1が出てきたら10を吐き出す、
01が出てきたら110を吐き出す、
001が出てきたら1110を吐き出す、
0001が出てきたら1111を吐き出す、
0000が出てきたら0を吐き出す。

0294デフォルトの名無しさん

2009/10/19(月) 11:38:40

>>285,290
要するに、ハフマン符号化？

0295デフォルトの名無しさん

2009/10/19(月) 11:49:00

0が連続する確立が他界から00->0はいいとして
それ以外は逆にbit数殖えちゃうんだよもん

0296デフォルトの名無しさん

2009/10/19(月) 11:54:11

>>293
(0001)^15 0^21

0297デフォルトの名無しさん

2009/10/19(月) 12:05:27

>>290
(01)^15 0^66

0298デフォルトの名無しさん

2009/10/19(月) 12:07:30

(01)^15 0^51 orz

0299デフォルトの名無しさん

2009/10/19(月) 17:58:00

>>280
1になるビットの最低個数は0？

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

0300デフォルトの名無しさん

2009/10/19(月) 19:53:31

>>280
これって、数え上げ符号でいいんじゃないかな？

0301デフォルトの名無しさん

2009/10/19(月) 20:14:28

遅いんじゃないの？

0302280

2009/10/19(月) 21:17:37

>>299
当初の仕様では1になるビットの最低個数は０でしたが、
今は立ってるビットが極端に少ないときは32ビットまで絞ろうかなーとか思ってます。
よかったら32ビットで何個のビットまで対応できるかもアドバイスください。

0303デフォルトの名無しさん

2009/10/19(月) 21:26:07

>>285をみて理解できた完璧だとか言えるなら全体のbit数に応じて出現最大bit数を計算する応用は出来るはずだろ

0304デフォルトの名無しさん

2009/10/19(月) 21:44:10

>>303

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

0305デフォルトの名無しさん

2009/10/19(月) 22:06:59

出現頻度が常に0>1ならハフマン符号化でいいんじゃないの

0306デフォルトの名無しさん

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個ある場合は無圧縮なので 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ビット拾う ---> ア
　２．アが 0 なら 000 を吐き５へ
　　　アが 1 なら 2ビット拾う ---> イ
　３．イが 00 なら 001 を吐き５へ
　　　イが 01 なら 010 を吐き５へ
　　　イが 10 なら 100 を吐き５へ
　　　イが 11 なら 2ビット拾う ---> ウ
　４．ウが 00 なら 011 を吐き５へ
　　　ウが 01 なら 101 を吐き５へ
　　ウが 10 なら 110 を吐き５へ
　　ウが 11 なら 111 を吐き５へ
　５．１へ　27組分やったら終りもしくは 1の出現をカウントし最大数に達していたら終り

ハフマン符号化の亜種

0307280

2009/10/19(月) 23:23:20

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

0308デフォルトの名無しさん

2009/10/19(月) 23:35:17

ちゃくちゃくと将棋の終盤戦の圧縮アルゴリズムに向かってるにおいがしてきました…

0309デフォルトの名無しさん

2009/10/19(月) 23:36:05

81bitの約数を選んだだけじゃないの？
というかハフマン符号化について調べてないよねきっと。

0310デフォルトの名無しさん

2009/10/19(月) 23:38:22

将棋の終盤戦で、各々の持駒数計が22個もあるような状態ってよくあることなの？

0311デフォルトの名無しさん

2009/10/19(月) 23:42:05

詰め将棋だとしてもこの持ち方は非効率的だろ

0312280

2009/10/19(月) 23:43:41

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

0313デフォルトの名無しさん

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を許容する　　と思う

0314デフォルトの名無しさん

2009/10/19(月) 23:49:54

orz
3bitごとにひとまとまりのデータと見立てた場合でかつ、上であるほど出現頻度が高い場合の符号化パターン
を書こうとしたら誤爆した。

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

0315280

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
...

0316デフォルトの名無しさん

2009/10/20(火) 01:04:32

それで効率悪くならなければそれでもいいんじゃない？

0317デフォルトの名無しさん

2009/10/20(火) 01:29:50

実データがある程度作れるなら、辞書持った方がいいと思うけどなあ

0318デフォルトの名無しさん

2009/10/20(火) 08:00:11

ハフマン符号化とか情報理論の勉強初めて一番最初に習うようなもんだと思っていたが

0319280

2009/10/20(火) 08:05:12

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

0320デフォルトの名無しさん

2009/10/20(火) 08:56:02

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

0321デフォルトの名無しさん

2009/10/20(火) 18:26:45

一日三回くらいまで

0322デフォルトの名無しさん

2009/10/20(火) 18:37:25

多い日も安心

0323デフォルトの名無しさん

2009/10/20(火) 20:41:31

>>320
81Cx <= 2^32 を満たす x までじゃないかなぁ

0324デフォルトの名無しさん

2009/10/20(火) 21:26:36

てか、ビット数も出現率も分かってるんだから、
理論限界値はシャノンの定理で算出できるだろＪＫ。

0325デフォルトの名無しさん

2009/10/21(水) 20:18:30

81ビット長
　1が0個 81!/(0!81!)=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が最大７個までならば可能と推測できる
　テーブル引き（辞書検索）なら出来るがデータ量と検索時間から実現は難しい　　　と思われる

で連続する 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になるビットは最大４個　までなら32ビット長にできます　　　たぶん

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

0326デフォルトの名無しさん

2009/10/21(水) 20:26:03

敬体と常体が入り交じる文章って流行ってるの？

0327デフォルトの名無しさん

2009/10/21(水) 20:38:18

コピペの継ぎ接ぎを読み過ぎてそのように学習してしまったのでしょう
意味が通じればいい、まさに理系の鏡です

0328 ◆0uxK91AxII

2009/10/21(水) 21:06:14

鑑。

0329デフォルトの名無しさん

2009/10/21(水) 21:09:51

檻

0330,,・´∀｀・,,）っ-○◎○

2009/10/21(水) 21:27:23

加々見

0331デフォルトの名無しさん

2009/10/21(水) 21:32:32

今回は高速化数え上げ符号を使いました

0332デフォルトの名無しさん

2009/10/21(水) 23:58:41

4個でいいなら8bitづつにわけて絶対アドレスでおk。

0333デフォルトの名無しさん

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
となり、条件を満たす。

0334デフォルトの名無しさん

2009/10/22(木) 02:51:54

どこの誤爆なんだろう？

0335デフォルトの名無しさん

2009/10/22(木) 03:00:18

>>330
だんごってどれが目なの

0336 ◆0uxK91AxII

2009/10/22(木) 03:02:54

´　｀

0337デフォルトの名無しさん

2009/10/22(木) 03:06:04

まじで！
それ眉間のしわで・・が目だと思ってたわ。。。

0338デフォルトの名無しさん

2009/10/22(木) 03:23:58

・・は、ほっぺのりんごですね

0339デフォルトの名無しさん

2009/10/22(木) 11:13:42

>337の所為でもうそのようにしか見えない……_/⌒|○

0340デフォルトの名無しさん

2009/10/22(木) 15:09:03

,, が目とか

0341デフォルトの名無しさん

2009/10/22(木) 15:11:11

◎が目だろ？

0342デフォルトの名無しさん

2009/10/23(金) 01:11:37

・∀・）っ-○◎●
,,・´∀｀・,,）っ-○◎○
明らかに・が目だろ。,,が頬だから・が頬というのはありえん。´は眉だよね？

0343デフォルトの名無しさん

2009/10/23(金) 01:59:17

,,・´∀｀・,,）っ-○◎○
あぁん？俺のダンゴが食えねえってのか？

0344デフォルトの名無しさん

2009/10/23(金) 03:12:35

△と□と○なら、おでんですね

0345 ◆0uxK91AxII

2009/10/23(金) 04:41:19

-○◎○

ネギま？

0346デフォルトの名無しさん

2009/10/23(金) 08:38:50

●は最近品切れ？

0347デフォルトの名無しさん

2009/10/23(金) 08:50:24

無職になってクレカ審査通らなくなったらしい

0348デフォルトの名無しさん

2009/10/24(土) 02:22:25

オセロってもう完全回答出たのかな？

0349デフォルトの名無しさん

2009/10/24(土) 02:30:31

出てないよ

0350デフォルトの名無しさん

2009/10/24(土) 09:03:46

オセロはいいよな。8x8マスがちょうど64ビットにおさまって。

0351デフォルトの名無しさん

2009/10/24(土) 09:12:24

一マス保持するのに1.6ビットほど必要だけどな

0352デフォルトの名無しさん

2009/10/24(土) 09:14:35

オセロのビットボードで１マス２ビット以外の実装はしない

0353,,・´∀｀・,,）っ-○○○

2009/10/24(土) 12:39:01

ビットボード（笑）ってシフトとかややこしくなるのに速いわけないと思ってるんだが

0354デフォルトの名無しさん

2009/10/24(土) 14:01:31

>>353
このあたりを見てもそう思えるかな?
ttp://www.amy.hi-ho.ne.jp/okuhara/howtoj.htm

0355デフォルトの名無しさん

2009/10/24(土) 15:04:37

普通シフトはしないよ。
ANDとifの羅列だよ。

0356デフォルトの名無しさん

2009/10/24(土) 15:15:01

普通は1マス3ビットだろ

0357デフォルトの名無しさん

2009/10/24(土) 15:22:47

ああ、失礼。

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

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

0358デフォルトの名無しさん

2009/10/24(土) 15:45:54

色以外の情報は何なの？

0359デフォルトの名無しさん

2009/10/24(土) 15:52:05

空き

0360デフォルトの名無しさん

2009/10/24(土) 18:31:22

色毎に置ける置けない

0361デフォルトの名無しさん

2009/10/24(土) 19:07:39

それを持たせるのはどうなの

0362デフォルトの名無しさん

2009/10/24(土) 19:17:14

常に持たせるのは無駄

0363,,・´∀｀・,,）っ-○○○

2009/10/24(土) 19:19:49

さすがに将棋でビットボードはないよな？

0364デフォルトの名無しさん

2009/10/24(土) 19:22:20

思いっきりあるよ

0365,,・´∀｀・,,）っ-○○○

2009/10/24(土) 19:27:39

1ワード27ビット×3レジスタくらいかな

0366デフォルトの名無しさん

2009/10/24(土) 19:37:54

人口無能を用意しない場合でも自動パス位は必要だからね
2ビットに成るか3ビットに成るかの分かれ目はＡＩの有無

0367デフォルトの名無しさん

2009/10/24(土) 19:42:27

それはない

0368デフォルトの名無しさん

2009/10/24(土) 19:49:41

>>365
掛ける7

0369デフォルトの名無しさん

2009/10/24(土) 19:56:38

だんごさんってこんな人だったっけ。
以前見たレスでは結構賢そうな印象だったけど。
別人なのかな。

0370デフォルトの名無しさん

2009/10/24(土) 21:01:14

本物のだんごはしばらく見てないと思う

0371,,・´∀｀・,,）っ-○○○

2009/10/24(土) 21:04:04

馬！鹿！団子！だよ

0372デフォルトの名無しさん

2009/10/25(日) 08:03:00

>>369
前からこんなんだよ。
知ったかぶりしたり大口を叩いたりして自分を不利な状況に追い込んでからの
ディベートを楽しむ人。

0373デフォルトの名無しさん

2009/10/25(日) 13:02:15

組込み開発だ度で、あまり特殊的ではなく、汎用的に使える
ビット演算をまとめてライブラリ化したいと思うけど、
何をピックアップしたらいいのだろうか？

0374デフォルトの名無しさん

2009/10/25(日) 14:05:11

あはは、馬鹿だこいつ

0375デフォルトの名無しさん

2009/10/25(日) 18:58:20

局所的な最適化のためにやるんであって、
変な汎用化をするくらいなら普通に書いてコンパイラに任せなよ

0376,,・´∀｀・,,）っ-○○○

2009/10/25(日) 19:51:18

ここ最近のGCCは賢すぎて小手先のテクはあんま意味無さ過ぎる
やるとしたらアルゴリズムレベルでの再考が必要

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

0377デフォルトの名無しさん

2009/10/25(日) 20:19:00

>>376
昔のGCCがアホすぎただけだろ？

0378,,・´∀｀・,,）っ-○○○

2009/10/25(日) 20:23:34

そうとも言う

0379デフォルトの名無しさん

2009/10/25(日) 22:26:51

アホの子のほうがかわいい

0380デフォルトの名無しさん

2009/10/25(日) 22:33:32

GCCがなかったらプログラマは今頃もっと幸せだったはずだ

0381デフォルトの名無しさん

2009/10/25(日) 22:37:50

CodeWarrior を使わざるをえなくてもそう思うか!

0382デフォルトの名無しさん

2009/10/26(月) 09:21:18

現在のGCCでも変数の局所性はあまり生かせてないらしい。

0383デフォルトの名無しさん

2009/10/26(月) 17:46:10

>>354
外人はビットボードに掛け算を持ち込んでくるからすごいよな

0384デフォルトの名無しさん

2009/10/26(月) 19:49:15

ビットボードの掛け算って、行列の掛け算みたいな感覚？

0385デフォルトの名無しさん

2009/10/26(月) 19:51:15

>>383
それ何のための計算？

0386デフォルトの名無しさん

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
あたりかね？横方向だけじゃなく縦方向や斜め方向の連続したビットを切り出す感じかなぁ

0387,,・´∀｀・,,）っ-○○○

2009/10/26(月) 22:56:56

パイプライニングが職人技すぐる。
現行CPUではAtomでくらいしか役に立たないけど。

0388デフォルトの名無しさん

2009/10/26(月) 23:18:46

奥原さんって一時期は国内有数のオセロプログラムの作者だったけど
今はもう冷めたのかな
これだけの腕があるのに勿体無い

0389デフォルトの名無しさん

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

これそのまま？

0390386

2009/11/29(日) 21:45:24

>>389
ごめ、数字の頭が$だったので、１６進に見えたｗ

0391デフォルトの名無しさん

2009/11/30(月) 09:52:33

頭が $ で16進って、何の表記法だったっけ？

0392デフォルトの名無しさん

2009/11/30(月) 10:31:40

モステクノロジー6502 だとか、モトローラ系のアセンブラ、
あとは vz のマクロで使う表記だと思ってたよ

0393デフォルトの名無しさん

2009/12/01(火) 01:08:14

俺はPascalの書き方だと思った

0394デフォルトの名無しさん

2009/12/24(木) 03:03:00

>>124
キャリーの逆ができる回路ってx86CPUに無いのかな？
x86以外ではこれができるCPUってある？

0395デフォルトの名無しさん

2009/12/24(木) 03:10:24

>>123のような命令があるとかなり最適化の
幅が広がると気がするんだけどどうなんだろ
あんまり使い道ない？

0396,,・´∀｀・,,）っ-○○○

2009/12/24(木) 04:27:11

そもそもそんなことが要求されるアプリケーションを知らない。
利用頻度の低い回路を実装することほど無駄なものは無いからな。
まあビット逆転なら高速化方法がいくつかあるが

0397デフォルトの名無しさん

2009/12/24(木) 21:22:36

>>395
強いてよく使われる場を挙げるとなると
高速フーリエ変換 (FFT) のアドレスアクセスで
ビット逆転の１インクリメントが必要になるとこくらいかな。
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) と簡単になる。

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

0398,,・´∀｀・,,）っ-○○○

2009/12/24(木) 23:18:08

pshufbで各バイト4ビットずつビット逆転するとか

0399デフォルトの名無しさん

2009/12/26(土) 02:54:55

この命令の回路って実装の手間とか実行のコストは普通の加算命令と同じだよね？

0400,,・´∀｀・,,）っ-○○○

2009/12/26(土) 10:20:35

こういうのは汎用化し辛い。

0401デフォルトの名無しさん

2009/12/30(水) 02:25:57

だんごさんはFPGAやASICには興味ないの？
既存のCPUで満足なの？

0402デフォルトの名無しさん

2009/12/30(水) 04:42:59

満足じゃなくたって、まさかCPUは作れないじゃん。

0403デフォルトの名無しさん

2009/12/30(水) 08:45:18

作れるけど、性能が一昔前なんだな。
たとえばNios II、一般品だとクロックが500M出るのは御の字。

0404デフォルトの名無しさん

2009/12/30(水) 09:55:37

っつーかFPGAでCPU作ってもメリットあまりないだろ
FPGAはCPU使わずに演算した方が高速

0405,,・´∀｀・,,）っ-○○○

2009/12/30(水) 11:49:39

こんなのよりよっぽど欲しい命令ならいっぱいあるから
D = (A & B) | (B & C) | (C & A)

とかな

0406デフォルトの名無しさん

2010/01/02(土) 04:06:04

32bit符号なし整数同士の加算でアセンブラを使わずに桁あふれをチェックするいい方法はないでしょうか？
if ( ( x + y ) < x ) {
　　...
}
今のところこれが一番速いのですが

0407デフォルトの名無しさん

2010/01/02(土) 04:33:19

>>394
キャリー先読みの関係で順序入れ替え回路を挟まざるを得ないと思うけれど、そんなニッチな状況に特化した命令を用意するかどうか…

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

0408,,・´∀｀・,,）っ-○○○

2010/01/03(日) 15:46:51

利用頻度次第じゃね？
FPGAですらFull Adderとかのよく使う回路は固定機能化されてることが多いぞ

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

0409デフォルトの名無しさん

2010/01/03(日) 17:55:23

ウンチビット　って何だろうと思ってしまった。

0410デフォルトの名無しさん

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 までは分岐の前にやってくれるとか。

0411デフォルトの名無しさん

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
とコンパイルした。ちょっと微妙?

0412デフォルトの名無しさん

2010/01/10(日) 02:30:27

zl = xl+yl;
zh = xh+yh+(zl<yl);
ってことか。割と頭いいな gcc。

0413デフォルトの名無しさん

2010/01/10(日) 05:53:08

if (zl < xl)
という比較はいらないの？

0414デフォルトの名無しさん

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 さえ満たせばそれで判定ＯＫ。

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

0415デフォルトの名無しさん

2010/01/10(日) 14:01:28

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

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

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

0416デフォルトの名無しさん

2010/01/10(日) 14:32:13

-masm=intel にして出力しなおしてから読むべし

0417デフォルトの名無しさん

2010/01/10(日) 22:32:54

ある変数が0かどうかを分岐無しで調べる方法ってありますか？
ビットが全部0なら0、一つでも立っていたら1みたいな感じで。
無理ですかね？

0418デフォルトの名無しさん

2010/01/10(日) 22:56:18

分岐するより遅いものしか思いつかん

0419デフォルトの名無しさん

2010/01/10(日) 23:00:12

Cなら!!xでいいんじゃね。gccにコンパイルさせてみたら
xorl　　%eax, %eax
setne　%al
になったんで十分かと

0420デフォルトの名無しさん

2010/01/10(日) 23:11:48

>>419
少し速くなりました。
なんか既視感を感じるなと思ったら大昔に自分でそのコードを
書いたのを思い出してしまいました。
どうも退化しているようです。
ありがとうございました。

0421デフォルトの名無しさん

2010/01/10(日) 23:20:52

xorlとcmplだとcmplの方がレジスタへの書き出しを伴わない分速かったりするのかね？

0422,,・´∀｀・,,）っ-○○○

2010/01/10(日) 23:49:17

うん、ここ最近のx86の実装では条件フラグ更新と汎用レジスタ更新は同時にはできない。
後続の条件フラグ更新命令の検出で演算をキャンセルすることで

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

0423デフォルトの名無しさん

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

0424デフォルトの名無しさん

2010/03/07(日) 01:59:17

あげ

0425デフォルトの名無しさん

2010/03/19(金) 11:30:09

乱数x から [a, b)かつ偶数or奇数の乱数に写像するビット演算ってどうなりますか？

0426デフォルトの名無しさん

2010/03/19(金) 13:40:34

偶数or奇数の乱数の意味がわからね
(x%(b-a))+aじゃダメか？

0427 [―{}@{}@{}-] デフォルトの名無しさん

2010/03/19(金) 15:59:35

偶数か奇数か固定したかったら1回左シフトして適宜1をorすればいいと思うよ。

0428デフォルトの名無しさん

2010/03/19(金) 21:00:19

>>427
なんとなくだけど、左シフトはあんまり
よくない気が。
ANDでLSBを0にするほうがいいと思う。
疑似乱数的に考えて。

0429デフォルトの名無しさん

2010/03/20(土) 04:38:34

そこは発生器の質に依るだろう

0430|ω・`)

2010/03/20(土) 21:46:15

全ビット詰まってないならシフトした方がいいし
全ビット詰まってて上位ビットほどランダムならシフトしない方がいいし
全ビット詰まってて全ビットがランダムならどっちでもいい

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

0431デフォルトの名無しさん

2010/03/21(日) 13:41:44

>>429
といっても、そういう期待以上のものは
なかなかないだろうな。

0432デフォルトの名無しさん

2010/03/24(水) 00:57:27

発生器にも統計的な国際基準の規定があるから一定の質を期待してもいい

0433,,・´∀｀・,,）っ-○○○

2010/04/06(火) 21:21:32

文字通り固定するなら分岐使った方が速いんじゃね？

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

0434デフォルトの名無しさん

2010/04/07(水) 14:13:21

>>433
偶数固定時にaが奇数かつn=aの場合とか、
奇数固定時にbが奇数かつn=b-1の場合…

0435デフォルトの名無しさん

2010/05/20(木) 19:09:55

あげ

0436デフォルトの名無しさん

2010/08/11(水) 16:30:00

保守

0437デフォルトの名無しさん

2010/09/16(木) 00:47:08

age

0438デフォルトの名無しさん

2010/09/16(木) 00:56:48

スレチかも知れませんが
ビットフィールドの定義順って
実際のビット順に反映されますか？
あと先に定義書かれてる方と後の方とでは
どっちが上位ビットになりますか？
例えば64ビットのときのメモリ上のバイト順は？

0439デフォルトの名無しさん

2010/09/16(木) 01:02:21

仕様書読め

0440デフォルトの名無しさん

2010/09/16(木) 01:26:12

処理系依存でFA

0441デフォルトの名無しさん

2010/09/16(木) 01:35:30

お前ら全然役に立たないね

0442デフォルトの名無しさん

2010/09/16(木) 01:36:02

お前には負けるよ

0443デフォルトの名無しさん

2010/09/16(木) 01:43:24

スレチかも、ではなく
スレチである！出てけ！

0444デフォルトの名無しさん

2010/09/16(木) 01:43:56

>>441
処理系依存なら仕方ないだろ

0445デフォルトの名無しさん

2010/09/16(木) 05:14:50

例えばライフボートのIAR ｃのマニュアルでは、デフォがMSBファースト
（ワードのMSB側から割り付けられる）で、#pragma bitfields=reversed を書くと
LSBファーストになる、と書かれてる。441が使うｃでその辺の記述を確認しなきゃ
どっちだか判らないだろ。今は多くがルネ系で、これならMSBファーストがデフォ。

0446デフォルトの名無しさん

2010/09/17(金) 13:56:03

うんちく

Big Endian と Little Endian は英語の言い回しが変が感じがするが、これはガリバー旅行記のリリパット (小人) 国の

話から来ているためである。この国では、卵を小さい方の端から割るように勅令を発した国王の支持派 (Little Endian)

と、しきたり通り大きい方の端から割る反対派 (Big Endian) が争いを起こす。この言い回しは、小さな違いが大きな事

態を引き起こしてしまうことを意味していて良くできていると思う。

0447デフォルトの名無しさん

2010/09/17(金) 14:43:16

それで、どこからコピーしてきたんだい？

0448デフォルトの名無しさん

2010/09/18(土) 08:18:39

1行置きに空行入れんな

0449デフォルトの名無しさん

2010/09/27(月) 09:16:42

>>446
うんち君乙

0450デフォルトの名無しさん

2010/10/03(日) 20:51:54

http://video.google.co.jp/videoplay?docid=6267783675810924557#

0451デフォルトの名無しさん

2010/10/03(日) 21:15:41

ワロタw

0452デフォルトの名無しさん

2010/10/05(火) 07:55:08

ウンチビット

0453デフォルトの名無しさん

2010/10/09(土) 20:13:49

価格のわりに処理速度がすげー速いマイコンって何になる？

0454デフォルトの名無しさん

2010/10/09(土) 20:29:56

>>453
今時の組み込みだとSH、ARM、ATOM辺りかなぁ？

0455デフォルトの名無しさん

2010/10/10(日) 03:28:02

atomってマイコンなのかへー

0456デフォルトの名無しさん

2010/10/10(日) 06:48:24

それを使ってアトムを作ってほしい

0457デフォルトの名無しさん

2010/10/10(日) 22:48:14

マイコンって何かね？

0458デフォルトの名無しさん

2010/10/11(月) 00:00:49

マイコンピュータ
デスクトップにあるやつ

0459デフォルトの名無しさん

2010/10/12(火) 22:10:37

誘電体に雲母を使った（

0460デフォルトの名無しさん

2010/10/15(金) 16:00:40

うちのアラジンのクラシックなストーブも雲母使ってあるな

0461デフォルトの名無しさん

2010/10/15(金) 18:57:58

ま、いーか

0462デフォルトの名無しさん

2010/10/15(金) 19:00:31

ttp://www.yogkan.co.jp/image/top_logo_image/product_top/maikon.png

0463デフォルトの名無しさん

2010/10/19(火) 22:06:10

ビッテンザン

0464デフォルトの名無しさん

2010/10/23(土) 05:08:54

ushortのポート読みとり値がLSB2bitより大きく変化したら、という判定をするのに
　if( ( (current>read) &&
　　　　(current-read)>=3 ) ||
　　　( (read>current) &&
　　　　(read-current)>=3 )　 ) {
とやってるんですが、なんかもう少しスマートな演算がありそうな気がします。
どうすればいいでしょうか？

0465デフォルトの名無しさん

2010/10/23(土) 06:54:36

if( ((current^read) & ~3) != 0) {...

0466デフォルトの名無しさん

2010/10/23(土) 07:03:27

464のコードはLSB2bitより大きく変化ではなくて差が3以上ならばだよね
そういうこと？

0467デフォルトの名無しさん

2010/10/23(土) 07:19:48

>>465
current=5, read=3とかの場合>>464の結果と違う事にならん？

0468デフォルトの名無しさん

2010/10/23(土) 07:47:06

LSB2bitより大きくの意味が曖昧でわからない
仮に>>464から差が3(11b)より大きいの意味だとすると
(current-read)>=3 ではなく (current-read)>3 とすべきなのでは

0469デフォルトの名無しさん

2010/10/23(土) 08:39:24

currentとreadの差の絶対値が3以上の時って事ジャマイカ
>LSB2bitより大きく
これだと4以上というようになると思うけど…

まあそれはいいとして
この手のは一時変数を使うと見やすくて分かりやすいと思う、個人的に
ushort t_read = read, t_current = current;
if ( t_current < t_read ) t_current = read, t_read = current;
if ( (t_current - t_read) >= 3 ) {...

マジレスするならやはり三項演算子だろう
if ( (current>read ? current-read : read-current) >= 3 ) {...

0470デフォルトの名無しさん

2010/10/23(土) 09:34:56

abs(current-read)

0471デフォルトの名無しさん

2010/10/23(土) 09:38:34

int>shortの環境ならこうすることもできそうだね
if( (unsigned)(c-r+2) > 4U ) {...
int=shortの環境は知らないがw

0472464

2010/10/23(土) 14:03:45

皆さんありがとう。読んだ値はA/D値なので、LSBは揺らいでいるから変化を見ない
ようにしたいんです。>=3ではなくて>3のほうが判定が軽いならそれでもいいです。
>>465で判定が軽ければ、５→３の変化を拾ってしまってもいいかも・・・　あ！
捨てるマスクを3bitにすれば７→３で４変化だから、引き算>3と同じ判定になるかも。
どうでしょうか？

0473デフォルトの名無しさん

2010/10/23(土) 15:06:28

A/Dの読みが何bit有効かでやり方変わるでしょ

0474464

2010/10/23(土) 16:09:16

10bitです。つまみの回し具合を取るもので、10bitの0～1023を、数値の60.0～0.0
になるように補正して使います。出力値も10bitなのですが、LSBまで変化を拾って
しまっては、bitシリアルな出力コマンドの数が出過ぎるので、間引きしたい訳です。

0475デフォルトの名無しさん

2010/10/23(土) 16:13:51

10bitの中の上から8bitを有効にするとかじゃダメなの？

0476デフォルトの名無しさん

2010/10/23(土) 17:05:32

470 がいいと思う。
結局のところ、前回の値との差が　n 以上なら、ということなのだから、
const int diff = current - read;
if ( diff >= n || diff <= -n ) ...
というのが素直な表現だと思う。

で、470 でも十分意図は伝わると思う。464 よりはずっとわかりやすい。
なんなら /*前回の値との差が　n 以上なら*/ とコメントしておくとよりよいかもしれない。

そして、abs は CPU によっては命令があるし、コンパイラによっては abs 命令や　cmov を使ってくれるかもしれない。

>>475
00 0000 0100 と 00 0000 0011　の間で振動するかもしれないからダメだということでしょ。

0477デフォルトの名無しさん

2010/10/23(土) 17:32:05

CPUがどうのってほどの話じゃなさそうなんだが

0478デフォルトの名無しさん

2010/10/23(土) 19:40:47

めんどくさい、1024個のテーブル作っちゃえ！

0479デフォルトの名無しさん

2010/10/23(土) 19:46:31

表引き嫌いな人っているんだよね

0480デフォルトの名無しさん

2010/10/23(土) 21:37:11

cur = ADC >> 2;
if (read != cur) {
read = cur;
}

0481デフォルトの名無しさん

2010/10/23(土) 22:57:50

だよなあ。正規化したいなら
cur = ADC & ~3; とかでいいわけだし。

0482デフォルトの名無しさん

2010/10/23(土) 23:26:44

生データとって、パソコン上でやり方考えたほうがいいんじゃないの？

0483464

2010/10/24(日) 03:04:55

表現の簡潔さで>>476ですか。でも判定の重さは変わらないようですね。
（このＣのabsは関数コールになるので）　やはり変えないでおきます。
相談に乗ってくれてありがとうございました。

0484デフォルトの名無しさん

2010/10/24(日) 03:14:38

>>483
だから abs() ならコンパイラがイイ具合にしてくれるかもしれないと言ってるんだ。
コンパイラと CPU の組み合わせによっては関数呼び出しではなく、もっといいものにしてくれる。
出荷時に予定している最適化オプションでコンパイルして出力を見てみるといい。

0485464

2010/10/24(日) 05:57:26

それは確認しました。インテル系ではなくH8S系で、インライン展開される機械語は
割り込みmask操作系、eepmov系、左右ローテート系　ぐらいしかありません。
　if( abs(curr-read)>=3 ) {　は、R6=curr-read で JSR　@abs：24 が出ます。
重さは同じなので、今度書くときには表現の簡潔さでこちらを使うとおもいます。

0486デフォルトの名無しさん

2010/10/24(日) 07:42:15

D/Aは8bitしかないのに何難しく考えてるんだろうね？

0487デフォルトの名無しさん

2010/10/24(日) 13:39:30

(x ^ (x>>31)) - (x>>31)

0488デフォルトの名無しさん

2010/10/24(日) 14:45:31

>>487
算術シフトであることを言わないと。

0489デフォルトの名無しさん

2010/10/24(日) 15:58:12

シフトやら論理積やらしなくてもいいんじゃないか？

INVALID_RANGE = 7; // 差分がこの範囲(-3 ～ +3）は無視する
LOWER_BOUND = -(INVALID_RANGE / 2);

((unsigned)(current - read - LOWER_BOUND) > INVALID_RANGE) ? "ok" : "ignore";

C言語の規格には詳しくないので、これがどの程度ポータブルなのかわからん。
キャストする代わりに、0ではなくINT_MINに片寄せするほうがよいのかも。

0490デフォルトの名無しさん

2010/10/24(日) 19:58:32

>>486
ものにも因るけど、音とかだったら、
折れ線近似程はやらないとダイナミックレンジかせげんちゃう？

0491デフォルトの名無しさん

2010/10/24(日) 20:16:12

それなら、机上じゃなくて
生データとって、パソコンでデータ解析とかやったらいいんじゃん
アルゴリズムとかも生データ見ながらのほうがいいと思うけど

考えすぎなだけのような気がするけど

0492デフォルトの名無しさん

2010/10/24(日) 20:29:49

>>491
音は無条件に下の方がつぶれるよ
人間の耳の感度が対数特性持ってるから…

0493デフォルトの名無しさん

2010/10/24(日) 22:19:36

なに言われてるのか、さっぱり...

0494デフォルトの名無しさん

2010/10/24(日) 22:47:16

2ch は心の荒んだ人の溜り場だな

0495デフォルトの名無しさん

2010/10/25(月) 18:50:42

いまのフレームのカウントから
n秒おきに処理するには
どう計算するのが速い？

0496デフォルトの名無しさん

2010/10/25(月) 18:55:39

n秒おきつっても
前の処理が終了してからn秒後に次の処理を始める
前の処理を開始してからn秒後に次の処理を始める
の2通り考えられるしなぁ

0497 [―{}@{}@{}-] デフォルトの名無しさん

2010/10/25(月) 19:14:29

フレームあたりの時間が安定していると仮定するなら(1/60sとか)、
PITみたいにフレーム毎に
A--;
if(A==0){
A=B;
event();
}
するのが良いかと

0498デフォルトの名無しさん

2010/10/25(月) 19:24:30

ははぁ、さてはヒヨコを餓死させたな＞495

0499デフォルトの名無しさん

2010/10/25(月) 19:56:17

fpsに合わせて関数テーブルつくって、間接呼び出しするとか
余計な判定いらないし

0500デフォルトの名無しさん

2010/10/26(火) 06:04:45

>>495-499
スレタイをご覧ください。

0501デフォルトの名無しさん

2010/10/26(火) 06:31:13

ジッタは許容するもの

0502デフォルトの名無しさん

2010/10/26(火) 22:43:35

ひよこ？
自動餌やり器か何かをコーディングするためにビット演算スレで質問ってこと？かわいい！
↓
バグ混入によりひよこが３２７６８日分の餌に埋れて死亡

0503 [―{}@{}@{}-] デフォルトの名無しさん

2010/10/27(水) 08:35:19

それは餓死と言うより圧死だな

0504デフォルトの名無しさん

2010/10/31(日) 16:10:40

たまにブログを読んでると Binary Hacks という本がちょくちょく眼に入って気になるんだが
俺らには関係ある話？

0505デフォルトの名無しさん

2010/10/31(日) 17:15:14

目次見ればわかるだろうに
http://www.oreilly.co.jp/books/4873112885/#toc

0506デフォルトの名無しさん

2010/11/02(火) 17:09:31

x & -x
で最下位ビットを取り出せますが、最上位ビットはできませんか？

0507,,・´∀｀・,,）っ-○○○

2010/11/02(火) 17:19:00

x >> (sizeof (unsigned int) * 8 - 1)

0508デフォルトの名無しさん

2010/11/02(火) 17:40:27

506ですが自己解決しました

0509デフォルトの名無しさん

2010/11/02(火) 23:19:27

マスクしろよ
(x >> (sizeof (unsigned int) * 8 - 1)) & 1

0510,,・´∀｀・,,）っ-○○○

2010/11/02(火) 23:41:58

>>506のいう最下位と最上位の意味が違ったようだ。
先頭／末尾から数えて最初の1だけを取り出すって意味ね

AMDは次の世代のCPUでTZCNT命令を追加する予定のようだね。
新命令を作るよりは今あるBSR/BSFを速くしろと思うんだが。

0511デフォルトの名無しさん

2010/11/03(水) 21:45:57

これがCore iの技術だ
HTT：マルチスレッド、HTT最適化ベンチマークの数値を上げる。
ただしシングルスレッド性能低下と爆熱化、消費電力向上のおまけ付き。有効活用出来る場面はニッチな用途のエンコードのみ。
ターボブースト：疑似OC。シングルスレッドベンチマークの数値を上積みでき、ベンチマーク結果表に定格のクロックで表記出来る。
コア性能が上がったとぬか喜びできる機能。実際はCore2から進歩していません。
PowerGate：未使用コアに電力を一切流さない事で省電力化を計れる・・・割にあまり下がっていません。
アイドル時に低クロック・低電圧駆動をし未使用コアへの電力供給を切ってようやく数Wの違いですか。
http://pc.nikkeibp.co.jp/article/news/20081103/1009419/?SS=imgview&FD=1213287981
http://pc.nikkeibp.co.jp/article/news/20090909/1018460/?SS=imgview&FD=1952977057

悪い悪くないの問題じゃなく、事実としてCore2Duo,Core2Quad,Core i7はもっさりCPU
キャッシュに収まらない処理をするとAMD製CPUには無いプチフリを頻発する欠陥品

CoreMAはもっさりテクノロジー

0512,,・´∀｀・,,）っ-○○○

2010/11/03(水) 22:36:25

ゲハでやれ

0513デフォルトの名無しさん

2010/11/06(土) 00:57:19

インテルのCPUは自分の息のかかったベンチさえ速ければ
それで売れるからな

メディアは広告ばんばんだしてやれば、
勝手にインテル有利のベンチだけの提灯記事書いてくれる

0514デフォルトの名無しさん

2010/11/09(火) 13:20:00

さらにSSD二つでRAID 0
ここはもっとIntel悲惨過ぎ
SSD一枚時より速度落ちるってなんだよ
　
専用のRAIDカードの次に早いAMD
http://akiba-pc.watch.impress.co.jp/hotline/20100904/sp_ssd2.html
　
　LSI MegaRAID SAS 9260-8iが最速、次いでAMD SB850となった。
AMD SB850はチップセット標準の機能である点を考えると、かなりコストパフォーマンスが高い。
　
　
　
RAID 0すると、逆に速度が落ちるIntel
http://akiba-pc.watch.impress.co.jp/hotline/20100904/sp_ssd2.html
　
　Marvell 88SE9128に関しては単体時よりも速度が落ちる結果となってしまった。
いろいろ手は尽くしてみたものの、速度を引き出すことはできなかった。
Marvell 88SE9128のRAID機能はおまけ程度に見ておいた方がいい。

0515デフォルトの名無しさん

2010/11/09(火) 13:22:27

今度はSSD四つでRAID 0
SATA 6Gbpsが二つしか付いてないIntelはテストすら出来ないときた
http://akiba-pc.watch.impress.co.jp/hotline/20100904/sp_ssd3.html

　4台RAID 0でもLSI MegaRAID SAS 9260-8iが最速。
頭一つ抜けて速度が出ているので、高速性をウリとするハードウェアRAIDカードの真価を発揮したといったところだろう。
　
　2番目に高速となったAMD SB850だが、チップセットの890GX - SB850間の帯域幅の問題でシーケンシャル速度が頭打ちになっている可能性はあるものの、チップセットのRAID機能で実測1GB/sを超えられるのは正直脅威だ。
RAID 0に関しては、並みのRAIDカードではAMD SB850の性能を上回ることは困難だろう。
コストパフォーマンス面でもずば抜けており、素晴らしい製品といえる。
　
　LSI 3ware SAS 9750-8iは2台RAID 0の時と同じく、相性なのか書き込み性能が出ない。
同じコントローラを搭載するMegaRAID SAS 9260-8iが高速な点を考慮すると、ドライバやファームウェアの改良で大きく変わる可能性があるので、今後に期待したい。
　
　3Gbps対応品に関しては2台RAID 0から速度が伸び悩むかたちとなった。
おそらく、コントローラの性能云々ではなく、カード側の帯域幅やチップセット間の帯域幅の上限に達してしまっていると思われる。
今回テストしたIntel ICH10RとLaCie SATA II 3Gbits/s PCI-Express Card 4Eに関しては、使用するならSSDは2台までにした方がいいだろう。
　
　全編を通してみると、AMD SB850のコストパフォーマンスの良さが光る結果となった。
チップセットの標準機能でここまで高性能なのは脅威を感じるほど。
速度に関しては高いポテンシャルを持ったなチップセットなので、AMD SB850ユーザーには積極的に高速なディスクを組み合わせて使ってもらいたい。

0516デフォルトの名無しさん

2010/11/09(火) 17:06:12

自作PC板に帰れ！

0517デフォルトの名無しさん

2010/11/09(火) 17:33:09

むしろ宗教板だな

0518デフォルトの名無しさん

2011/01/23(日) 02:22:29

あげ

0519デフォルトの名無しさん

2011/01/24(月) 17:57:14

>>506
ちなみにどうやったんですか？
一発でとれるんですか？

0520デフォルトの名無しさん

2011/01/24(月) 21:16:26

hacker's delightには506も含めて色々載ってる、Webで一部読めるし
ビット演算は左に伝播するため
xの型がわからなければ無理、が教科書的な回答じゃなかろか
それらの技術を駆使すれば
Boostに「熟練したプログラマでも云々」ってソースにコメントが書いてあるNextCombinationを
ビット演算とfor文だけで実装出来たりして面白い

0521デフォルトの名無しさん

2011/01/24(月) 21:53:19

>>519
検索したら見つかったけど、長いから採用しませんでした。

0522デフォルトの名無しさん

2011/01/28(金) 02:24:36

大文字と小文字を逆転させるコード考えたのですが
もっといいのないですか?

c ^= c >> 1 & (c - 1 & 31) + 38 & 32;

0523デフォルトの名無しさん

2011/01/28(金) 03:13:12

見せびらかしたかったんだね

0524,,・´∀｀・,,）っ-○○○

2011/01/28(金) 04:08:02

まず実用性がないな。
その程度ならテーブル引いたほうが速いんじゃね？

というか大文字と小文字を逆転する意味が不明。
たとえば大文字を小文字に変換（あるいはその逆）ならそれなりにあるけど
（大文字小文字区別なしの文字列検索・置換処理とかね）

んでもってこの手の処理はSSE*とかで纏めてやったほうが速い。
実際glibcのSSE対応パッチなんかも出てる

0525デフォルトの名無しさん

2011/01/28(金) 04:31:45

ちょっとした遊びだろ
意味が不明とか言ってやるなよ

0526,,・´∀｀・,,）っ-○○○

2011/01/28(金) 05:45:56

もしその処理が必要な箇所が1箇所だけならこう書く。
c = isupper(c)? tolower(c) : toupper(c);

そもそも動作確認してないだろ。
ちょっとRubyでチェックしてみたぜ。

def exchange_char_pedantic(c)
c ^= c >> 1 & (c - 1 & 31) + 38 & 32;
end
def exchange_char(c)
clower = c.chr.downcase[0]
c = (c == clower)? c.chr.upcase[0] : clower
end

256.times {|i|
printf("0x%02x ", i) if exchange_char_pedantic(i) != exchange_char(i)
}

このスクリプトでエラーになるパターンがこんだけ出ますた。使い物になりませんな。
0xc1 0xc2 0xc3 0xc4 0xc5 0xc6 0xc7 0xc8 0xc9 0xca 0xcb 0xcc 0xcd 0xce 0xcf 0xd0
0xd1 0xd2 0xd3 0xd4 0xd5 0xd6 0xd7 0xd8 0xd9 0xda 0xe1 0xe2 0xe3 0xe4 0xe5 0xe6
0xe7 0xe8 0xe9 0xea 0xeb 0xec 0xed 0xee 0xef 0xf0 0xf1 0xf2 0xf3 0xf4 0xf5 0xf6
0xf7 0xf8 0xf9 0xfa

せっかく頑張ったけど残念でしたね。
ただ、7ビットASCII空間に限定すればこの式でもいいんじゃね？
分岐除去っていう「下らないこだわり」を捨てられるならね。
そもそも最近のCPUでは分岐って遅くないですし。

0527デフォルトの名無しさん

2011/01/28(金) 06:00:55

スレというか流れ的にはどう見てもASCII限定コードにしか見えん
>>522はS-JIS判定コードのノリだと思うんだが

0528,,・´∀｀・,,）っ-○○○

2011/01/28(金) 06:14:38

char型がsignedがunsignedかによって結果違ったりするのかと思ったけど同じだった（エラーになるコードも）

0529522

2011/01/28(金) 12:47:54

ASCII限定のつもりでした、実用性は考えてません。
大文字変換なら c |= 小文字変換なら c &= ~() にすればOK
8bitなら、~(c >> 2) & を加えればOK
実際に半々とかで分岐する場合、分岐は今でも遅いんじゃないか?

分岐とかをビット演算に直す理論とか考えたら面白いかな、と思って書いてみました

0530デフォルトの名無しさん

2011/01/28(金) 16:02:06

どうでもいいけど分岐は今でも遅いだろ

0531デフォルトの名無しさん

2011/01/28(金) 16:55:14

↑ゴミは黙っててくれ

0532デフォルトの名無しさん

2011/01/28(金) 16:57:34

とゴミが申しております

0533,,・´∀｀・,,）っ-○○○

2011/01/28(金) 21:01:44

#define isupper(c) ( ((c) >= 'A') && ((c) <= 'Z'))
#define islower(c) ( ((c) >= 'a') && ((c) <= 'z'))
char exchange(char c)
{
return (isupper(c) || islower(c)) ? (c^32) : c;
}

これをGCCで最適化したらこうなった
_exchange:
movzx eax, BYTE PTR [esp+4]
lea edx, [eax-97]
cmp dl, 25
ja L7
L4:
xor eax, 32
ret
.p2align 4,,10
L7:
lea edx, [eax-65]
cmp dl, 25
jbe L4
.p2align 4,,3
rep
ret

んでさ手元のPCでテキスト置換速度を比較してみな？
http://sourceforge.jp/projects/sfnet_isalepoint/downloads/iSalePoint/GPLV3.txt/

これで試しにやってみたけど分岐したほうが速かった。
一番速いのはSIMD並列化版。
あとARMなんかだとこれ、全く分岐の無いコードにしてくれるよ

0534デフォルトの名無しさん

2011/01/28(金) 21:21:20

でっていう

0535デフォルトの名無しさん

2011/01/28(金) 23:02:03

>>533
俺の環境(Phenomでvisual c++ 2010)だと10000回で
分岐: 1845ms
522の方法: 1113ms
522をSSEで: 73ms
だったぞ

0536デフォルトの名無しさん

2011/01/28(金) 23:05:02

糞しょぼ

0537デフォルトの名無しさん

2011/01/29(土) 00:11:25

なあ、c ^= 0x20 じゃいかんのか？

0538デフォルトの名無しさん

2011/01/29(土) 00:12:20

お前はアスキー表でも眺めてろ

0539,,・´∀｀・,,）っ-○○○

2011/01/29(土) 00:22:58

SSE4.2使えると本当に便利だな
c ^= pcmpestrm(c, [A-Za-z]) & 0x20

0540デフォルトの名無しさん

2011/01/29(土) 00:40:25

そんな命令あったのか。やりたいことそのものな命令だな

0541,,・´∀｀・,,）っ-○○○

2011/01/29(土) 00:51:47

俺はSSE2でASCIIの小文字→大文字変換やる場合こんな感じでやってるよ

diff_lower: dd 0x1F1F1F1F, 0x1F1F1F1F, 0x1F1F1F1F, 0x1F1F1F1F
cmp_lower: dd 0x99999999, 0x99999999, 0x99999999, 0x99999999
exch_mask: dd 0x20202020, 0x20202020, 0x20202020, 0x20202020

movdqa xmm0, [src]
movdqa xmm1, xmm0
paddb xmm1, [diff_lower]
pcmpeqb xmm1, [cmp_lower]
pand xmm1, [exch_mask]
pxor xmm0, xmm1

pcmpgtbはsignedの比較だから、a～zを -128～-103に持っていくのが味噌
c >= 'a' && c <= 'z' をそのまま比較2回（マスク生成）＋論理積に置き換えるのは頭の悪いやり方

0542,,・´∀｀・,,）っ-○○○

2011/01/29(土) 00:55:15

訂正

movdqa xmm0, [src]
movdqa xmm1, xmm0
paddb xmm1, [diff_lower]
pcmpgtb xmm1, [cmp_lower]
pandn xmm1, [exch_mask]
pxor xmm0, xmm1

0543,,・´∀｀・,,）っ-○○○

2011/01/29(土) 01:03:02

つーか、考えたら+1して101 < c ? 100 : 0でもOKか
cmovとかsbbとか使えばSSE使わなくても分岐の無いコードは書けるよ。

0544,,・´∀｀・,,）っ-○○○

2011/01/29(土) 01:04:29

ミスった
c = (101 < (signed char)(c+1)) ? c ^20 : c;

0545デフォルトの名無しさん

2011/01/29(土) 01:16:18

チラチラチラウラデ

0546デフォルトの名無しさん

2011/01/29(土) 01:50:53

>>543
そりゃそうだよ、522も本質的にはcmovと同じ
(c - 1) & 31 + 38
をすると5bit目がフラグの代わりになる
'a'と'A'の下五桁が00001なので

理論的に面白いかなと。
テーブルを与えると、自動的にそのテーブルと同じ出力のビット演算を出力するツールとか

ビット演算とシフトの数学みたいなの考えればいいのだけど

0547,,・´∀｀・,,）っ-○○○

2011/01/29(土) 02:46:10

暗号のS-boxをビット論理式に展開するツールなら既に作ってたりする。

0548デフォルトの名無しさん

2011/01/29(土) 08:21:20

BSF命令のSSE版ってありますか？

0549,,・´∀｀・,,）っ-○○○

2011/01/29(土) 17:14:59

8ビット16並列

vpand xmm1, xmm0, [mask_0x0f0f0f0f]
vmovdqa xmm2, [bsf_nibble_low]
vpshufb xmm2, xmm2, xmm1
vpsrld xmm1, xmm0, 4
vpand xmm1, xmm1, [mask_0x0f0f0f0f]
vmovdqa xmm3, [bsf_nibble_high]
vpshufb xmm3, xmm3, xmm1
vpminub xmm2 xmm2, xmm3

0550デフォルトの名無しさん

2011/01/30(日) 01:01:39

ごめんなさい
xmmレジスタを128bit整数型と見て、それ全部に対してBSF命令を使いたいんです
destが0～127になるような

0551 ◆0uxK91AxII

2011/01/30(日) 06:47:33

＞(v)cvtpi2psで指数部抽出できるだろ。あとはわかるな。

0552,,・´∀｀・,,）っ-○○○

2011/01/30(日) 14:17:01

しょせん64ビット×2なんだからあんまし複雑なことやる必要無い気が

ptest xmm0, xmm0
jnz .bsf128_error
movq rdx, xmm0
bsf rax, rdx
jnz .bsf128_done
pextrq rdx, xmm0, 1
bsf rax, rdx
add eax, 64
.bsf128_done:

0553デフォルトの名無しさん

2011/01/31(月) 04:17:33

ありがとうございます

0554,,・´∀｀・,,）っ-○○○

2011/01/31(月) 06:42:06

ptest xmm0, xmm0
jz .bsf128_error

あああ

0555 ◆0uxK91AxII

2011/02/01(火) 02:37:39

出だしを書いてみたところでbsf/bsrのlatencyを見て書く気力を失ってみた。
x86ならソコソコいけると思ったのだけど。

0556,,・´∀｀・,,）っ-○○○

2011/02/01(火) 03:02:56

分岐除去＆厨テク駆使

mov ecx, -64
movq rax, xmm0
test rax, rax
pextrq rdx, xmm0, 1
cmovnz ecx, rax
cmovnz rax, rdx
bsf rax, rax
lea rax, [rax + rcx + 64]

0557,,・´∀｀・,,）っ-○○○

2011/02/01(火) 03:07:04

cmovnzじゃなくてcmovzな

0558デフォルトの名無しさん

2011/02/02(水) 00:35:07

>>546
じゃあ、とりあえず x を入力すると x+1 番目の素数 y を出力する
ビット演算大喜利とかやって見る？
x のビット数縛りで。

y = 2|x; // 1 bit ルール
y = (0x7532 >> (x<<2)) & 7; // 2 bit ルール
y = (0x13110d0b07050302 >> (x<<3)) & 255; // 3 bit ルール

あはは…ヘタレで済まんね、、

0559デフォルトの名無しさん

2011/02/02(水) 03:48:04

ほぼテーブル法だった件

0560デフォルトの名無しさん

2011/02/02(水) 06:33:20

何がしたいんだっていう

0561デフォルトの名無しさん

2011/02/02(水) 12:53:17

>>556
こういうのって自力で見つけたりするの？
専門の本があったりするの？

0562デフォルトの名無しさん

2011/02/02(水) 22:18:31

ダンゴの場合は受け売り

0563,,・´∀｀・,,）っ-○○○

2011/02/03(木) 03:14:25

>>561
x86依存の最適化はコンパイラの出力が教科書
てか、こっちのほうがコードサイズ小さくなくるか

mov ecx, 64
movq rax, xmm0
test rax, rax
pextrq rdx, xmm0, 1
cmovz ecx, rax
cmovnz rax, rdx
bsf rax, rax
add eax, ecx

＜余談＞
Penrynのptestってpcmpeqb → pmovmskb → testと大して性能変わらないかも知れん

0564,,・´∀｀・,,）っ-○○○

2011/02/03(木) 04:58:31

逆だった
mov ecx, 64
movq rax, xmm0
test rax, rax
pextrq rdx, xmm0, 1
cmovnz ecx, rax
cmovz rax, rdx
bsf rax, rax
add eax, ecx

0565デフォルトの名無しさん

2011/02/28(月) 03:19:36.80

誘導されてきた。
同じ質問だが、こちらで聞くのでご容赦してくれ。

ビット・オンの最上位のみ残したい場合、
ビットスキャンリバースを使わずに、いい方法ないかな。
ビット・オンの最下位のみ残す場合は、例えば対象の値を80としたとき、

mov eax,80
mov ebx,eax
neg eax
and eax,ebx

こんな感じよね。
これをビット・オンの最上位でやりたいんだが、何かいい方法ないかな。
最下位フラグを消していく方法を繰り返すくらいなら、素直にビットスキャンしちまうんだが。

なければ、ない、と言ってくれ。

0566デフォルトの名無しさん

2011/02/28(月) 03:27:28.13

age

0567デフォルトの名無しさん

2011/02/28(月) 04:25:50.25

>>565
ビットスキャンリバースって何？
まぁ、効率は悪いけど、ぱっと思いつくのは、
シフト(1→2→4…と必要なだけ)と論理和を繰り返して1を加算後シフト。
最後に、必要であれば、元の数の最上位ビットだけ取り出すとかかな…
何か他にもありそうな気がするので思いついたら、また書く

0568デフォルトの名無しさん

2011/02/28(月) 05:38:32.66

>>565
駄目だ、思いつかんかった
取り合えず>>567をコードにするとこんな感じ
アセンブラは数年ぶりなんで、ミスってたらスマソ

mov eax, 80
mov ebx, eax
shr eax, 1
or ebx, eax
mov eax, ebx
shr ebx, 2
or eax, ebx
mov ebx, eax
shr eax, 4
or ebx, eax
mov eax, ebx
shr ebx, 8
or eax, ebx
mov ebx, eax
shr eax, 16
or ebx, eax
and eax, 80000000h
add ebx, 1
shr ebx, 1
or eax, ebx

0569デフォルトの名無しさん

2011/02/28(月) 06:05:49.46

>>567
アンガトさん。
bsr　(Bit Scan Reverse)。bsf　の逆順ですy

おいらにとっては難題なの。
考え始めて早数年。
実現方法はいくらでもあるので、可不可の問題ではない。
でも最下位セットビットに関しては一発二発でいけるわけだから、
どうせならスマートな方法見つけたい。

可能性としては、最大値の商を何とかさへば、どうにかなんべ。
ところがうまくいかんでは。

0570,,・´∀｀・,,）＜一番良い -○○○ を頼む

2011/02/28(月) 06:11:39.07

面倒だからこうする

pcmpeqd xmm1, xmm1
pslld xmm1, 23

movd xmm0, eax
cvtsi2ss xmm0, xmm0
andps xmm0, xmm1
cvtss2si xmm0, xmm0
movd eax, xmm0

Atomでも使わない限りBSR使ったほうが速い気もするけどな。1～2サイクルだし。

0571デフォルトの名無しさん

2011/02/28(月) 06:35:51.04

>>569
一発で行きたいだけなら、fpuのlog使えば？(多分fyl2x当たり)
まぁ、効率が良いかは分からんが…む

0572デフォルトの名無しさん

2011/02/28(月) 07:03:26.85

>>570-571
さんくす。最上位のみ残すという目的は果たせるね。
正直、浮動小数点数変換考えてなかった。

望んだビット操作とは少しちがう感じだけど、
本懐を遂げることは出来る感じ。
しかも符号付整数には変な感じに対応できる。
笑えるし、要所で使えるかも。

でも、整数除算で何ともならないのは如何ともしがたいところ。

0573565

2011/02/28(月) 07:11:54.98

世話になったので借りを返してみる。

>>548
参考までに、用件から大きくずれるが、最下位のみ残すなら、
xmm0に128ビット整数が読まれているとして、

pcmpeqd xmm7,xmm7　//マイナス１作成
paddd xmm7,xmm0　//paddqだろーが何だろーがok
pandn xmm7,xmm0　//128ビット中、最下位セットビットのみ残る

問題は、どうしてもビットスキャンしたい場合（つまりこれが本題）だが、

ビットシフト（まずは右詰め）したい場合
当然１２８ビットのままビット単位でシフトできないので、
そもそもインデックス（合計シフト回数）を求める必要性が疑問。
SIMD使わずに、bsf　の後、非ゼロdest以降は　shrd　の繰り返しが良いのでは？

もしくは、他のビット列を左シフトして最下位をそろえたい場合、
同様にshldの繰り返しになると予想。
条件次第では、上記の例のxmm7を利用し
pmuludq dest,xmm7　//桁あふれ対策は別途。shldよりもこちらの方が楽かも。
でいけばハッピー。
右シフト（除算）と違い、64ビット符号なし整数乗算できるのがミソ。

こんな感じで、作業内容によってはインデックス（シフト回数）を求める必要はないと思う。
本末転倒でスマン。

0574565

2011/02/28(月) 17:50:02.89

書き込んですぐに気づいたが、上記の方法はうまくいかない。
頭わりーな。
paddq xmm7,xmm0
の場合でも、上位６４ビットと下位６４ビットを別に処理しなきゃならん。
３２ビットごとの処理でも、下位の結果を上位に反映させるためのマスク処理必須だし。
結局使えんな。

恩返しにならなくてすまん

0575デフォルトの名無しさん

2011/02/28(月) 21:45:27.21

public static int highestOneBit(int i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}

0576デフォルトの名無しさん

2011/03/01(火) 00:00:08.14

8bit幅なら表引きとかじゃダメかいな？

0577565

2011/03/01(火) 07:38:10.13

>>575
こうしてみると、見やすいですね。
考えてもみれば、非64環境で６４ビットに対応できる貴重な方法だし。
引き出しに入れときます。ありがとう。
変形できそうで、出来ないのが残念。

>>576
今の時代なら16ビットでも問題なさそう。
でも対象ビットが増えたときに、分岐処理が悩ましいのね。

0578デフォルトの名無しさん

2011/03/01(火) 20:42:43.07

Hacker's Delightを読み返したら>>575と同じ方法だった

0579,,・´∀｀・,,）＜一番良い -○○○ を頼む

2011/03/01(火) 23:48:35.21

負の値のときの処理は確かに考えてなかった。
MSBが立ってるときだけ下位31ビットをクリアでいいんじゃね？

FPUを使うというアイディアはHDを紹介してたブログ主が言及してた。
x87とMMXはレジスタ共有してるからダイレクトにビットフィールドにアクセスできるとか云々

0580デフォルトの名無しさん

2011/03/02(水) 01:20:52.15

>>579
>>565が本当に欲しい機能が何なのかは分からんが
負の値を考慮した場合、欲しいのは、絶対値に換算後の結果なのか、
単にMSBを無視した値なのかとか、場合によって欲しい結果は違うからね…

0581,,・´∀｀・,,）＜一番良い -○○○ を頼む

2011/03/02(水) 17:40:30.11

bitscanって基本unsignedじゃね？
つーか、cvtsi2ssはソースレジスタはGPRだった。なのでmovd不要。

0582デフォルトの名無しさん

2011/03/27(日) 00:01:01.84

Javascriptのビット演算が四則演算よりおせぇ。
なんのために付いてんだ？

0583デフォルトの名無しさん

2011/03/27(日) 01:34:50.11

スクリプトにそんなん求めるな

0584デフォルトの名無しさん

2011/03/27(日) 10:07:13.44

JavaScriptは数値は全部doubleだから

0585デフォルトの名無しさん

2011/04/29(金) 21:37:00.25

文字列とかの可変長データを8バイト境界に揃える仕掛けってどうやるんだっけ
数年ブランクがあるから忘れちゃった

0586デフォルトの名無しさん

2011/04/29(金) 21:43:16.84

>>585
単に8の倍数に切り捨てたいだけなら、n & ~(8-1)

0587デフォルトの名無しさん

2011/04/29(金) 22:22:50.68

あー！そんなやつです。
ありがとうございます。

0588デフォルトの名無しさん

2011/04/30(土) 01:14:08.60

n & -(intptr_t)8

0589デフォルトの名無しさん

2011/05/05(木) 20:30:16.23

閏年判定いってみようか

0590デフォルトの名無しさん

2011/05/05(木) 20:34:15.69

!(yearFrom1901To2099 & 3)

0591デフォルトの名無しさん

2011/05/06(金) 11:00:57.16

ビット演算でやるのはパズル過ぎるだろ

0592デフォルトの名無しさん

2011/05/06(金) 19:04:13.47

76543210
を
7060504030201000
みたいに隙間１ビット開けるのってどうする？

0593,,・´∀｀・,,）っ-○○○

2011/05/06(金) 19:06:39.15

それ1ビットじゃなくて4ビットじゃないのか？

0594デフォルトの名無しさん

2011/05/06(金) 19:16:58.40

3ビットかも
っていうか間を空けたいっていう例だろ

0595,,・´∀｀・,,）っ-○○○

2011/05/06(金) 19:24:34.89

Larrabeeにbitinterleave命令があるし、グラフィック関係でよく使うのは知ってる。

16ビットならこれが速いかも(pshufbが使えない場合はunpack命令数回で代替）
pshufb→pand→pcmpeqb→pmovmskb

0596,,・´∀｀・,,）っ-○○○

2011/05/06(金) 19:37:15.13

と思ったけどLUT使ったほうがマシだな

0597,,・´∀｀・,,）っ-○○○

2011/05/06(金) 19:47:57.16

とりあえず16ビット→32ビットはこんな感じになります

n = (n | (n << 8)) & 0x00FF00FF;
n = (n | (n << 4)) & 0x0F0F0F0F;
n = (n | (n << 2)) & 0x33333333;
n = (n | (n << 1)) & 0x55555555;

0598デフォルトの名無しさん

2011/05/06(金) 20:13:08.02

それは1ニブル空ける場合ですか？

0599592

2011/05/06(金) 21:53:29.47

判りづらくてすまん、0を00、1を10みたいにしたかったん。
0000b->00000000b
0001b->00000010b
0010b->00001000b
0100b->00100000b
1001b->10000010b
みたいな
特に用途は思いつかなかったんだけどｗ

0600デフォルトの名無しさん

2011/05/06(金) 22:30:53.41

8Bitのビットマップを8Byteのバイトマップ(0x00,0xff)にするのは
テーブルを持つのが定跡でしょうか？

0601デフォルトの名無しさん

2011/05/07(土) 09:44:12.66

「バイトマップ」なんていう他人に通じない用語で質問されても困りますが。

たとえば 0x36 を 0x00 0x00 0xff 0xff 0x00 0xff 0xff 0x00 のように展開したいとかそういうこと？

0602デフォルトの名無しさん

2011/05/07(土) 10:16:30.98

フラグを配列に格納したいとかそんなんじゃないかと予想

0603,,・´∀｀・,,）っ-○○○

2011/05/07(土) 10:40:19.00

>>598
1ニブルなら2行目まででおｋ

0604600

2011/05/07(土) 10:40:25.52

白黒Bitmap画像を、グレースケールの0x00,0xffに拡張したい感じです

0605,,・´∀｀・,,）っ-○○○

2011/05/07(土) 10:44:19.63

>>599
ないのかよ！
Graphics Gems Iを読んでみたらビットインターリーブの応用例が出ている。

実用性の無い技術を磨くことほど無駄なことは無いからな。
解ってると思うけど、世の中で役に立つのは自己満足のコード書くことより
必要十分な、他の人が読めるコード書くスキルだからな

0606デフォルトの名無しさん

2011/05/07(土) 12:15:23.97

>>604
64ビット1ワードで、8*256=2Kバイトか。64ビットマシンでメモリに余裕があるならテーブルでいいんじゃない？

0607デフォルトの名無しさん

2011/05/07(土) 12:27:25.37

べつに32で2回ロードしてもいいし、それならテーブルは4*16でいいのだが

0608,,・´∀｀・,,）っ-○○○

2011/05/07(土) 13:32:18.05

SSE*ならものすごい簡単にできるよ

1. 16ビットを8ビットずつにわけでpshufbでコピー（なければunpack命令で代用）

AA BB
↓
AA AA AA AA AA AA AA AA BB BB BB BB BB BB BB BB

2. pandでビットマスクとってpcmpeqb
ビットパターンは
0x80 0x40 0x20 0x10 0x8 0x4 0x2 0x1 0x80 0x40 0x20 0x10 0x8 0x4 0x2 0x1
見たいな感じね

0609,,・´∀｀・,,）っ-○○○

2011/05/07(土) 13:33:27.17

おっと、リトルエンディアンだからビットパターン逆か。

0610デフォルトの名無しさん

2011/05/07(土) 13:50:06.86

このスレダンゴばっかになってるぞ

0611デフォルトの名無しさん

2011/05/08(日) 13:18:22.39

ダンゴさんが書き込むとスレが引き締まるな。

0612デフォルトの名無しさん

2011/05/09(月) 00:46:51.85

ご本人は引き締まってなさそう

0613デフォルトの名無しさん

2011/05/09(月) 02:09:53.54

色々ダダ漏れだもんな

0614デフォルトの名無しさん

2011/05/09(月) 02:21:59.26

震災後初めて団子みたからちょっと安心したわ。

0615デフォルトの名無しさん

2011/05/09(月) 03:36:38.65

大丈夫
自作PCあたりで元気に発狂してた

0616・∀・）っ-○○○

2011/05/09(月) 06:58:20.08

>>612
いちおう今60kg台だ
そろそろ痩せだんごやさんに戻すか

0617デフォルトの名無しさん

2011/05/09(月) 07:32:34.39

あらかわいい

0618デフォルトの名無しさん

2011/05/09(月) 07:52:37.53

久しぶりに来たが団子さん元気だな
よかったよかった

0619デフォルトの名無しさん

2011/05/13(金) 23:31:28.61

ビット演算を用いて
ビットの位を反転させる以下のような演算を行うことは可能でしょうか?

概要:
符号なし整数 n, 最上位ビット a から符号なし整数 n' を求める

例:
a = 4 のときの n → n'
0000 0000 → 0000 0000
0000 0001 → 0000 1000
0000 0110 → 0000 0110
0000 1111 → 0000 1111

a = 6 のときの n → n'
0000 0000 → 0000 0000
0000 0001 → 0010 0000
0000 0110 → 0001 1000
0000 1111 → 0011 1100

0620デフォルトの名無しさん

2011/05/13(金) 23:33:19.41

>>619
× 最上位ビット a
○ 最上位の桁数 a

0621デフォルトの名無しさん

2011/05/14(土) 04:01:08.84

ｎを(a-4)回左シフト　じゃないの？

0622デフォルトの名無しさん

2011/05/14(土) 11:11:33.67

掛け算と剰余算と小さなテーブル使っていいなら、適切なテーブル用意して
int revx(int n,int a){
　　return n*table1[a]%table2[a];
}
で行けるけど

ビット演算だけだときつくないか？

0623622

2011/05/14(土) 11:38:00.25

何いってんだ俺。
正しくは
return(n*table1[a]&table2[a])%table3[a];

0624デフォルトの名無しさん

2011/05/14(土) 17:05:31.10

>>619
固定幅の反転は知ってる前提でいいのか？
各固定幅反転コードを各々最適化しておいて switch(a) するのが結局速い

0625デフォルトの名無しさん

2011/05/15(日) 00:37:55.29

ダンゴさん待ち

0626619

2011/05/15(日) 11:17:36.40

みなさまありがとうございます
任意の幅 a に対して処理する必要があるため，今は1ビットごとにループで処理しているのですが
やはりビット演算だけで任意幅は無理があるみたいですね
>>624 の方法で特定の a については分岐する方向で考えてみようと思います

0627デフォルトの名無しさん

2011/06/12(日) 17:44:08.41

流れをぶち破って本当に申し訳ないんだけどｗこのスレならわかる人がいるだろうと思い質問を

○＋△or□というものがあった場合さ
○＋△の2つと□の1つを＝として捉えてどちらか(or)という風に捉えるのか
○の1つに加えて(＋)△の1つか(or)□の1つという風に捉えるのかどっちなのかな？

記号の優先度とか初歩的な話になるんだろうことが想像出来て恥ずかしいんだけど誰か回答を願いたい
ちなみに数式の時の優先度と物に置き換えた時に記号を充てた時の優先度でも変わるのかどうかとかも

0628デフォルトの名無しさん

2011/06/12(日) 17:59:24.40

演算子優先順位

0629デフォルトの名無しさん

2011/06/13(月) 02:37:06.77

>>627 言語で違うことは無いとは言えないが、少なくともＣとASMでは算術演算子は
論理演算子より優先度は高い。　○＋△or□は、
（○＋△）or□　と解釈される。　○＋（△or□）とするためには明示的にカッコが必要。

0630デフォルトの名無しさん

2011/06/27(月) 00:47:29.46

2つの符号無し整数a,bがあったとき, aからbで1が立ってるビットのみを拾ってきて
右詰めで返すのを効率良くできたりしますか?
たとえば a = 10110[2], b = 11011[2] のとき 01010[2] を返して欲しいです.

0631デフォルトの名無しさん

2011/06/27(月) 00:53:31.47

xor?

0632デフォルトの名無しさん

2011/06/27(月) 00:54:14.51

違った

0633デフォルトの名無しさん

2011/06/27(月) 01:33:52.13

意味がわからない上に例で何が起きてるのかもわからない

0634デフォルトの名無しさん

2011/06/27(月) 01:36:58.60

aからbの「から」が分からん。
「拾ってきて」が分からん。
「右詰めで」も意味分からん。

0635デフォルトの名無しさん

2011/06/27(月) 01:57:34.53

>>663, >>664
bで1が立っているビットしか見ないという意味です.
bで0が立っているビットはなかったことにしたいわけです.

0636デフォルトの名無しさん

2011/06/27(月) 01:57:43.34

ソース見て、弄るしか

0637デフォルトの名無しさん

2011/06/27(月) 02:04:26.21

ハッカーのたのしみの7-4

0638デフォルトの名無しさん

2011/06/27(月) 02:16:27.79

符号無し整数のビット数は？
ビット数が8ぐらいなら、
テーブル参照がお手軽そうだけど、CPUによっては早くなるってわけじゃないからな

0639デフォルトの名無しさん

2011/06/27(月) 04:53:48.19

bのマスク値から0の位置で分割していって、
別々に処理して結合しかないな。
「右詰め」は人間にしか判らないし。

b1 = 0b11000;
b2 = 0b00011;
t1 = ((a & b1) >> 1) | ((a & b2));
でt1 = 0b01010が得られる。

0640デフォルトの名無しさん

2011/06/27(月) 06:29:52.82

aの側をシフトしてけばいいか。
これが叩き台かな。
#define BITSIZE 8
int bitstuff(int a, int b) {
int i, mask = 0, maskbit = 1, bit = 1;
for (i = 0; i < BITSIZE; i++, bit <<= 1) {
if (b & bit) {
mask |= maskbit;
maskbit <<= 1;
} else {
a = ((a & ~mask) >> 1) | (a & mask);
}
}
return a;
}
「ハッカーのたのしみ」にずばり載ってたりするの？

0641630

2011/06/27(月) 10:05:14.77

今日職場にあるハッカーのたのしみ見たら出てました
みなさんありがとうございます

0642デフォルトの名無しさん

2011/06/27(月) 11:13:46.61

先ず、1bitずつ転写する事に拘るのをやめる。
立っているbitの数を数えてから、シフトして結果を作ったほうが効率良い。
さらに、ビットカウントをifなしで出来る事を知っていれば、全体でもifもループも要らないよね。

0643デフォルトの名無しさん

2011/06/27(月) 15:24:04.66

http://www.hackersdelight.org/HDcode/compress.c.txt

0644天使 ◆uL5esZLBSE

2011/07/01(金) 16:56:46.17

＞ビット演算だけだときつくないか？

0645デフォルトの名無しさん

2011/07/03(日) 01:53:29.14

オセロ作るときにさ、64bitの変数を白の盤面、
黒の盤面と2個用意して、コマの貼りつけ可能位置を
最速で判定する方法ないかな？

0646デフォルトの名無しさん

2011/07/03(日) 01:55:43.58

その他人本願的な発想が素敵！！！

0647デフォルトの名無しさん

2011/07/03(日) 01:56:27.74

×他人
○他力

0648デフォルトの名無しさん

2011/07/03(日) 02:09:42.91

じゃぁちったぁ自分の考え出すか。
とりあえず、さくっと候補を調べようと思うと

守//守備側
攻//攻め側
候補 = 守<<1 | 守>>1 | 守 << 8 | 守 >> 8 ;
候補 = ( ( 守 | 攻 ) & 候補 ) ^ 候補;

で絞り込めそうな気がする。ある局面でボロが出そうな気もするけど。
あと、八方のひとつに攻め側が存在しないことが解からん。

0649デフォルトの名無しさん

2011/07/03(日) 02:10:09.78

>>645
テーブル

0650デフォルトの名無しさん

2011/07/03(日) 03:05:42.28

~(白 | 黒)
で終わりやん

0651デフォルトの名無しさん

2011/07/03(日) 03:06:46.92

始まってすらねぇよ。

0652デフォルトの名無しさん

2011/07/03(日) 03:13:04.79

アタック25を見ればわかる
今日やるから

0653デフォルトの名無しさん

2011/07/03(日) 03:38:16.11

>>645
ほれ
http://www9.atwiki.jp/othello?cmd=upload&act=open&pageid=28&file=othello_counter4.cpp
俺の知る中での最速
何か質問あればどうぞ

0654ラプラスの天使 ◆daemontaDA

2011/07/03(日) 12:09:43.41

>>2
変態かｗ

それこそアセンブラだろｗ

0655 忍法帖【Lv=6,xxxP】

2011/07/03(日) 13:01:51.07

bit 演算気円斬

0656デフォルトの名無しさん

2011/07/03(日) 15:41:38.01

>>653
ありがとう。じっくり読ませてもらうよ。

0657,,・´∀｀・,,）っ-○○○

2011/07/03(日) 15:55:21.40

ううう・・・SSEを使いたい病気が・・・

0658デフォルトの名無しさん

2011/07/03(日) 16:10:52.05

つこうてもいいけど

0659デフォルトの名無しさん

2011/07/03(日) 16:13:19.30

そういやSSE使ってるのもどこかにあったような気が

0660デフォルトの名無しさん

2011/07/03(日) 16:15:53.64

MMXだった
http://radagast.se/othello/bitmob.c

0661デフォルトの名無しさん

2011/07/03(日) 16:24:40.34

だんごさんが>>653みたいなプログラム作ったらやっぱぶっちぎりで勝っちゃうのかな

0662,,・´∀｀・,,）っ-○○○

2011/07/03(日) 16:27:34.77

ねーよ

0663デフォルトの名無しさん

2011/07/03(日) 16:33:51.08

だんご大丈夫

0664デフォルトの名無しさん

2011/07/03(日) 16:36:58.35

まさかだんごさんから弱音が漏れるとは

0665,,・´∀｀・,,）っ-○○○

2011/07/03(日) 18:32:22.35

128ビットのレジスタがあることだし2並列処理とかできたら効率よさそうだけど
2並列化するメリットってあるのかなと思ってさ

0666デフォルトの名無しさん

2011/07/03(日) 23:00:17.61

ある局面で着手する側の打てる場所の数と
同じ局面で相手が打てると仮定した場合の数は
それぞれAIの評価関数で使い道があるよ

0667デフォルトの名無しさん

2011/07/04(月) 19:03:33.35

スレ違いだったらすいません。
C言語で2つの16bit変数同士を加算して、
0xffff以上になる時は0xffffとしたいのですが、
どうやればいいでしょうか？
アセンブラだとキャリーフラグを見ればいいのは判るのですが。

0668デフォルトの名無しさん

2011/07/04(月) 19:28:24.75

>>667
uint16_t a, b, sum;
sum = (~a < b) ? 0xffff : a + b;

0669デフォルトの名無しさん

2011/07/04(月) 23:26:50.41

横からだけど、~演算子はビット数を勝手に拡張する場合があるから
((uint16_t)~a < b)ってやらないと危険だと思う

0670デフォルトの名無しさん

2011/07/05(火) 00:13:15.31

http://www.emit.jp/prog/prog_b.html
こういうのもあるけど、さすがに>>668の方が速いか。

0671デフォルトの名無しさん

2011/07/05(火) 01:12:15.79

３２ビットレジスタが使えるならこんな感じかなぁ。遅いかもだけどｗ

sum = a+b | (0x80000000-((a+uint32_t(b))>>16) ^ 0x80000000) & 0xffff;

0672天使 ◆uL5esZLBSE

2011/07/05(火) 10:54:50.15

＞３２ビットレジスタが使えるならこんな感じかなぁ。遅いかもだけどｗ
ハアアァァァァァァァァアァァァァアァァァァアァアァアアアァアァァアァアァアァァァァ？？？？？？？？？？？？？？？？

0673デフォルトの名無しさん

2011/07/06(水) 00:25:26.68

私も、ビット演算をしていたらビビっと来ました。
それからは最高の毎日を送っています。

0674デフォルトの名無しさん

2011/07/06(水) 00:57:43.89

ふつうにif文使えよ。
32ビット演算して値でif。

0675デフォルトの名無しさん

2011/07/06(水) 01:37:41.38

>>668-669の方法でうまくいきました。
ありがとうございました。

0676デフォルトの名無しさん

2011/07/06(水) 02:24:40.56

そのビット演算はifより速いのか？
ビット演算使いたいだけちゃうんかと

0677デフォルトの名無しさん

2011/07/06(水) 03:13:14.46

最適化によってifがcmovになるならifが一番速いと思うよ

0678デフォルトの名無しさん

2011/07/06(水) 03:55:01.88

x86でもARMでもないかもしれないじゃないか

0679デフォルトの名無しさん

2011/07/06(水) 07:47:15.13

計測してみた。
http://codepad.org/n3qBdFSG
sadd1: 0.060 sec（ごく普通の分岐）
sadd2: 0.080 sec (ビット演算＋分岐)
sadd3: 0.060 sec (ビット演算分岐なし)

http://ideone.com/SFASM
sadd1: 0.060 sec
sadd2: 0.100 sec
sadd3: 0.090 sec

>>671がダントツいくかと期待してたんだけど、
意外に分岐(条件演算子)が速いね。
ま、こいつらは最適化offでビルドしてそうだけど。
gccなら -O3 -march=pentium3 とかでcmov使ったコード出る。

* VisualStudio
sadd1: 0.203 sec
sadd2: 0.218 sec
sadd3: 0.282 sec

* bcc32(5.5) -O2 -OS -6
sadd1: 0.296 sec
sadd2: 0.422 sec
sadd3: 0.344 sec

* gcc(3.4.4) -Wall -ansi -O3 -march=pentium3
sadd1: 0.219 sec
sadd2: 0.234 sec
sadd3: 0.235 sec

0680,,・´∀｀・,,）っ-○○○

2011/07/06(水) 08:37:26.86

分岐予測甘くみんなってことだな

0681デフォルトの名無しさん

2011/07/06(水) 08:53:29.03

それだと分岐版は分岐する・しないを32k回ずつ交互に繰り返すから
予測がほぼ全て当たる状態になるね

まあ実際の運用でも、入力パターンが予測可能かどうかによって分岐のコストは変わる
全然違う例だけどこのへん参考になるね
http://homepage1.nifty.com/herumi/diary/1011.html#24

0682デフォルトの名無しさん

2011/07/06(水) 09:13:30.05

ブレゼンハムが、分岐予測が当たりにくい、と聞いた

0683デフォルトの名無しさん

2011/07/06(水) 09:41:21.74

なるほど。
>>681の指摘に伴い引数を変えたバージョンを追加してみました。

http://codepad.org/iAanFePF
name: mark1 mark2 total
sadd1: 60 ms 70 ms 130 ms
sadd2: 70 ms 80 ms 150 ms
sadd3: 70 ms 70 ms 140 ms

http://ideone.com/2Umn5
name: mark1 mark2 total
sadd1: 70 ms 80 ms 150 ms
sadd2: 100 ms 110 ms 210 ms
sadd3: 80 ms 90 ms 170 ms

$ VisualStudio
name: mark1 mark2 total
sadd1: 250 ms 218 ms 468 ms
sadd2: 250 ms 234 ms 484 ms
sadd3: 266 ms 266 ms 532 ms

$ gcc -Wall -ansi -O3 -march=pentium3
name: mark1 mark2 total
sadd1: 203 ms 266 ms 469 ms
sadd2: 234 ms 282 ms 516 ms
sadd3: 234 ms 266 ms 500 ms

なぜかVisualStudioではbench_mark2の方が速い謎。

0684デフォルトの名無しさん

2011/07/06(水) 11:04:10.05

っていうか、これでいいことに気が付いた･･･。
return (unsigned short)((a+b) | -((a+b) >> 16U));

0685デフォルトの名無しさん

2011/07/06(水) 12:08:49.40

>>683
いや、それでもほとんど予測されちゃうな
大部分はパターン0101...を繰り返すだけだから、パターン認識の餌食に

乱数使うのが手っ取り早いね
http://codepad.org/KuAExPhP

0686デフォルトの名無しさん

2011/07/06(水) 12:31:09.03

>>685
なるほどプロセッサによってぜんぜん挙動が違うんですね。
一度乱数も使ってみたのですが、当方のマシンでは0101の場合とほとんど変わらずでした。
codepadの使ってるマシンだとビット演算の方が2倍近く速いですね。

ふーむ、私のラップトップではビット演算の面白みがないようですｗ
name: mark1 mark2a total
sadd1: 219 ms 234 ms 453 ms
sadd2: 250 ms 282 ms 532 ms
sadd3: 234 ms 281 ms 515 ms

0687671

2011/07/07(木) 20:36:46.93

需要が無いのは分かってるんだけど、勉強の為に分岐予測も外せるようにしたソース置いておきます
新たに閃いたコードも入ってます
ttp://ideone.com/7wgVs

３項演算子遅すぎ

0688,,・´∀｀・,,）っ-○○○

2011/07/09(土) 10:20:28.81

まあ需要はないな。
飽和演算程度でパフォーマンスのネックになるほど大量に捌かないと
いけないならSSE使えよって話になるし。

0689,,・´∀｀・,,）っ-○○○

2011/07/09(土) 10:34:07.10

fastcall規約ならこれだけですむ
movd xmm0, ecx ;; a
movd xmm1, edx ;; b
psadw xmm0, xmm1
movd eax, xmm0
ret

0690,,・´∀｀・,,）っ-○○○

2011/07/09(土) 11:46:57.72

movd xmm0, ecx ;; a
movd xmm1, edx ;; b
psadw xmm0, xmm1
movd eax, xmm0
and eax, FFFFh ;; ←上位ワードのゴミ掃除
ret

ゴミ掃除しとくか

0691デフォルトの名無しさん

2011/07/09(土) 13:57:46.46

これがいわゆる熱中症です

0692デフォルトの名無しさん

2011/07/09(土) 15:02:28.02

8bitや16bitの変数を使って、そのbit数よりも多く数える方法ありませんか？
符号化か何かで。
例えば8bitなら300まで可能、みたいな感じで。

0693デフォルトの名無しさん

2011/07/09(土) 15:07:33.18

有効桁数が少なくなっていいなら浮動小数点みたいに仮数部と指数部に分けてみたら

0694デフォルトの名無しさん

2011/07/09(土) 15:12:11.32

例えば8bitなら0-256まで数えたいときがあるんだよね。
そういうのでいいです。

0695デフォルトの名無しさん

2011/07/09(土) 15:13:12.57

何をいってるのか、わかってるのかね

0696デフォルトの名無しさん

2011/07/09(土) 15:17:12.10

二桁の数字で０から１００まで数えたいときがあるんだよね。
そういうのでいいです。

0697デフォルトの名無しさん

2011/07/09(土) 15:17:36.48

8bitの変数を2つ使えば簡単だと思うよ！

0698デフォルトの名無しさん

2011/07/09(土) 15:18:13.22

>>692
いくら符号化しても8ビットで表せるビットパターンが増えるわけではないので、そういうのは不可能だと思うよ。

0699デフォルトの名無しさん

2011/07/09(土) 15:20:28.68

「0」は0、「00」は100とする
あったまい～

0700デフォルトの名無しさん

2011/07/09(土) 15:22:26.92

魔法使いでも探してるの？

0701デフォルトの名無しさん

2011/07/09(土) 15:27:22.34

例えばNULLと値の2状態を分けたい時ってありますよね。
その区別のために2バイトも使うなんて許せないです。

0702デフォルトの名無しさん

2011/07/09(土) 15:28:24.21

何をいってるんだい？

0703デフォルトの名無しさん

2011/07/09(土) 15:28:40.21

0.5bitを使うか

0704デフォルトの名無しさん

2011/07/09(土) 15:30:31.31

>701
けちって１ビットだけ使えばいいじゃん。
スペースをけちるとその分ほかにしわよせがいくけど。

PostgreSQLのNULLの処理はカラムの値とは別にカラムごとのNULLフラグを１ビットずつ持って処理しているよ。

0705デフォルトの名無しさん

2011/07/09(土) 15:32:02.47

コードのエリアで表す方法がある

if (他の変数) {
// 0-255のエリア
} else {
// 256-511のエリア
}
見ての通り「他の変数」が必要だが

0706デフォルトの名無しさん

2011/07/09(土) 15:33:53.38

グレイコード辺りで圧縮できませんかね。
よろしくおねがいしまう。

0707デフォルトの名無しさん

2011/07/09(土) 15:35:33.62

圧縮するほどの大きさがあるものなのかい？
パソコンのアプリなら富豪プログラム出来るだろうに

0708デフォルトの名無しさん

2011/07/09(土) 15:37:06.60

数え方を覚えておいて、
254→255と遷移したら255、
254以外→255と遷移したら256
とか。

0709デフォルトの名無しさん

2011/07/09(土) 15:46:20.21

0xaaや0x55みたいな特異な値で何かできないかな

0710デフォルトの名無しさん

2011/07/09(土) 15:50:55.24

難しいことやってる気になりたいのかね？
簡単に考えりゃいいのに、割りきって

0711デフォルトの名無しさん

2011/07/09(土) 15:53:47.76

どこに覚えておくんだ？

0712デフォルトの名無しさん

2011/07/09(土) 16:44:52.16

2進数に変換してそれをｎ進数とみなし、(n-1)の剰余を求めればいいと思うよ

0713デフォルトの名無しさん

2011/07/09(土) 17:03:47.56

天才あらわる！！！

0714デフォルトの名無しさん

2011/07/09(土) 18:45:11.40

昔読んだ本に8ビットで100万まで数えるトリックが載っていたなぁ
通信系情報理論本の序論だった。

0715デフォルトの名無しさん

2011/07/09(土) 18:51:34.97

うまく符号化すれば1ビットで100まで数えられませんかね

0716 ◆0uxK91AxII

2011/07/09(土) 20:52:07.75

>>701
ポインタを使って、MSBが立っていたらNULLとするとか。

0717デフォルトの名無しさん

2011/07/09(土) 21:00:50.26

頭壊れるような話によく釣られるね

0718デフォルトの名無しさん

2011/07/09(土) 21:37:57.99

>>694
完璧な方法は絶対に存在しないけど、使える方法ならある。

例えば、0～256の整数を識別したいけど、奇数は絶対に扱わない、というのであれば
2で割った値を格納しておいて、使うときに2を掛けるような処理を組めば良い。

結局のところ、8つのビットの組み合わせで表現できる、互いに識別可能な元は256個しかないから
8つのビットを使って257種類の状態を識別することは、鳩の巣原理を用いれば簡単に証明できるように、
理論的に不可能なんだよ。

どんなファイルでも必ず可逆圧縮できるようなアルゴリズムがこの世に存在できないのと理由は同じ。

それと一応>>701に突っ込むと、NULLは16bitだったり32bitだったり36bitだったり64bitだったりするけど
あなたがプログラミングで扱うような尋常なマシンだと通常8bitにはならないから
そんな心配はしなくて良い。

あと、よく知られたテクニックとしては、1byte型へのポインタでも無い限り
ポインタ変数が格納するアドレスのLSBのあたりに情報を乗せない方法があるから、
そこから情報を抜き取って、そこに代わりの情報を埋め込む、という方法がある。

0719718 ◆tAo.kQ2STk

2011/07/09(土) 21:40:53.44

もうひとつ突っ込む場所があったのを思い出した。

>>706
グレイコードは圧縮じゃないよ

0720デフォルトの名無しさん

2011/07/09(土) 21:45:07.24

>>692
　　　　　　　＿＿＿_
　　　　／　　　　　＼
　　　　／　　⌒　　⌒ ＼　
　　　／　　（●）　（●）＼
　　 |　　､"　ﾞ)（__人__）"　　）　　　 _＿＿＿＿＿＿＿＿＿_
　　　＼　　　｡｀ ⌒ﾟ:j´　,／　jﾞ~~| | |　　　　　　　　　　　　　|
＿＿／　　　　　　　　　　＼　 |_＿| | |　　　　　　　　　　　　　|
| |　/　　 ,　　　　　　　＼ｎ||　 | |　　　　　　　　　　　　　|
| | /　　 /　　　　　　　　　r.　（こ） | |　　　　　　　　　　　　　|
| | |　⌒ ーnｎｎ　　　　|＼ (⊆ｿ .|_|_＿＿＿＿_＿＿＿＿_|
￣＼＿_､("二）￣￣￣￣￣ｌ二二ｌ二二　＿|_|＿_|＿

0721デフォルトの名無しさん

2011/07/09(土) 22:29:10.38

まあそんなにちっさいもんさらに圧縮したいってことは
それが並列にいっぱいあるからだろうから
ランレングスとかで合宿すればよろし

0722デフォルトの名無しさん

2011/07/10(日) 03:23:08.01

>>720
なんでおでん喰ってんの？

0723デフォルトの名無しさん

2011/07/10(日) 04:23:31.79

アイスだろ季節柄

0724デフォルトの名無しさん

2011/07/10(日) 07:53:13.87

このスレまとめたみたいなライブラリって無いの？
C++でTMPと実行時、固定長と自由長のがあるといい

0725デフォルトの名無しさん

2011/07/10(日) 11:03:39.36

自由帳にでも書いてろカス

0726デフォルトの名無しさん

2011/07/10(日) 11:31:03.57

まず0ビットで1を数える方法を考えればいい
あとは1ビットで100だろうが、8ビットで100万だろうが任意の応用ができる

0727デフォルトの名無しさん

2011/07/10(日) 12:09:21.08

無限桁を1桁に圧縮した世代

0728デフォルトの名無しさん

2011/07/10(日) 16:54:48.24

色なんかだと人間の感覚に応じて端折ることできたりするけどねえ。

0729デフォルトの名無しさん

2011/07/10(日) 17:21:20.54

char increment(char prev){
float f = (float)((unsigned long int)prev<<48);
f = f + 1.0f;
return (char)((unsigned long int)f>>48);
}

0730デフォルトの名無しさん

2011/07/25(月) 15:30:23.74

半角英大文字をインクリメント・デクリメントしたいと思います
Zを超えたらAに、Aを超えたらZにしたい場合どうすれば効率よくできますか

0731デフォルトの名無しさん

2011/07/25(月) 15:50:51.72

そこはテーブルだろうやはり

0732デフォルトの名無しさん

2011/07/25(月) 15:54:34.88

答だけ聞けりゃいいと思ってると身につかんだろうな
ある意味、自分はバカですといってるようなもん

0733デフォルトの名無しさん

2011/07/25(月) 17:23:41.32

>>730
どれも環境依存だけど、テーブル使うならこっち
char inc_tbl(char const c) { return "BCDEFGHIJKLMNOPQRSTUVWXYZA"[c-'A']; }
char dec_tbl(char const c) { return "ZABCDEFGHIJKLMNOPQRSTUVWXY"[c-'A']; }

使いたくないならこっち(最近のコンパイラならcmovにしてくれるはず)
char inc_cmov(char c) { ++c; return c>'Z' ? 'A' : c; }
char dec_cmov(char c) { --c; return c<'A' ? 'Z' : c; }

無理やりビット演算するならこっち(もっといい方法はあると思うけどとりあえず)
char inc_bit(char c) { c-= '@'; return (c & ~((char)(c+102)>>7)) + 'A'; }
char dec_bit(char c) { c-= 'B'; return (c ^ ((c^25) & (c>>7))) + 'A'; }

0734デフォルトの名無しさん

2011/07/25(月) 19:47:10.37

文字といっても文字コードは色々あるし
cmovとかインテルローカルな話はやめろよ

0735デフォルトの名無しさん

2011/07/25(月) 20:03:23.91

cmovはAMDの方が速いし
条件付き移動命令自体はx86に限った話でもないけど
例えばMIPSにもSPARCにもAlphaにもあるし、
ARMやPA-RISCやIA64なんかは移動だけでなくほとんどの命令を条件付き実行できる

0736デフォルトの名無しさん

2011/07/25(月) 20:15:44.91

>>734
そんな事を言い出したらキリがないぞ。言語すら指定されてないんだから。
それとも世界中の全言語全文字コード全CPU対応のソースでもあるの？はやく出してよ

0737730

2011/07/25(月) 20:29:34.64

>>732
質問者に難癖つけるだけよりは、第三者にも参考になることもありうるので
よほど有意義だと思うのですが？

>>733
ありがとうございます
3番目みたいなのは面白いですが、もし実装するなら2番目でしょうね

>>734
長い夏休みの暇つぶしに投稿しただけなので
環境はとくに指定しません

0738デフォルトの名無しさん

2011/07/25(月) 20:49:37.42

>>737
初心者じゃないなら、何やったかぐらい書いたら

0739デフォルトの名無しさん

2011/07/27(水) 11:18:59.11

>>737
> 質問者に難癖つけるだけよりは、第三者にも参考になることもありうるので
> よほど有意義だと思うのですが？

驚くべき思い上がりだな。

0740デフォルトの名無しさん

2011/07/27(水) 12:20:35.75

>>739
自分はおこぼれを頂戴してるだけであって物乞いなどしないとでも言いたいのかｗｗ

0741デフォルトの名無しさん

2011/07/27(水) 12:38:28.19

> 第三者にも参考になることもありうるので

夏厨への対処の仕方という意味で参考になる。

0742デフォルトの名無しさん

2011/07/27(水) 13:20:00.75

どんぐりがなんか言ってるぞ

0743デフォルトの名無しさん

2011/07/29(金) 04:54:23.60

おまいらせめてビット演算で会話しろよ

0744デフォルトの名無しさん

2011/07/29(金) 07:02:31.99

dase

0745デフォルトの名無しさん

2011/07/29(金) 16:23:51.65

8bit x 4 の加算 (幅は違いますが、要はpaddb) を汎用レジスタでやるとき、

inline uint32_t add(uint32_t x, uint32_t y)
{
uint32_t m1 = 0x00ff00ff, m2 = ~m1;
return (((x & m1) + (y & m1)) &m1) | ((x & m2) + (y & m2)) & m2);
}

より効率的な方法はありませんか。

0746デフォルトの名無しさん

2011/07/29(金) 16:47:08.46

uint32_t s = (x & 0x7f7f7f7f) + (y & 0x7f7f7f7f);
return ((x ^ y) & 0x80808080) ^ s;
ってのがハッカーのたのしみ2-17にあったよ

0747デフォルトの名無しさん

2011/07/29(金) 18:25:14.97

x+y からキャリーを引くのは特定条件で駄目だとわかったので、なんとなくその方法はあきらめてました。
ありがとうございました。

0748デフォルトの名無しさん

2011/07/31(日) 11:21:51.05

>>746
下位ビットは普通に加算しつつ
最上位ビットの加算のみxorに置き換える事で
繰り上がりを防いでいるわけか

0749デフォルトの名無しさん

2011/08/11(木) 14:29:27.61

>>745で飽和加算てできるんでしょうか？

0750デフォルトの名無しさん

2011/08/11(木) 14:39:55.33

できません

0751デフォルトの名無しさん

2011/08/11(木) 15:01:16.69

ありがとうございました

0752デフォルトの名無しさん

2011/08/12(金) 06:42:11.15

ハッカーのたのしみかったけど
積みそうな内容だった
イタリック体の数式はダメなんだって

0753デフォルトの名無しさん

2011/08/12(金) 06:53:32.58

アレは辞書代わりに使ってる

0754,,・´∀｀・,,）っ-○○○

2011/08/12(金) 21:27:59.78

あれより濃い本が欲しい

0755デフォルトの名無しさん

2011/08/13(土) 08:14:39.33

数学的な方向ならコンクリート本かな？

0756デフォルトの名無しさん

2011/08/13(土) 08:15:34.94

あとHAKMEMを直接読むとかも面白いかも

0757デフォルトの名無しさん

2011/08/19(金) 19:31:49.48

コンクリート本って何？

0758デフォルトの名無しさん

2011/08/19(金) 19:40:20.90

http://www.amazon.co.jp/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025

0759デフォルトの名無しさん

2011/08/19(金) 23:17:16.83

thx

0760デフォルトの名無しさん

2011/08/20(土) 14:23:07.36

コンクリートジャングル
ってどういう意味？
そういえば

0761デフォルトの名無しさん

2011/08/20(土) 14:27:58.87

《(和)concrete＋jungle》ビルの林立する都会を、ジャングルに見立てた語。

0762デフォルトの名無しさん

2011/08/20(土) 14:30:01.02

ほう、
風流な・・・

0763デフォルトの名無しさん

2011/08/20(土) 18:19:46.48

　　　　　￣￣￣￣￣￣￣l/￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　　　 ∧＿∧
　　　　　　　　　( ´･ω･`) 　　　∧＿∧
　　　　　　　　／　　　＼　　（　　　　）何言ってんだこいつ　
　　　　　.＿＿|　|　　　 .|　|＿　/ 　　　ヽ
　　　　　||＼　￣￣￣￣　　／ .|　　　|　|
　　　　　||＼..∧＿∧　　　(⌒＼|_＿./ ./
　　　　　||.　（　　　）　　　　 ~＼___＿_ノ|　　 ∧＿∧
　　　　　　　/　　　ヽ　空気読めよ　　＼| 　（　　　　）　
　　　　　　　|　　　　　ヽ　　　　　　　　　　＼/ 　　　ヽ. ｵﾏｴ馬鹿だろ
　　　　　　　|　　　　|ヽ、二⌒) 　　　　　　／ .|　　　|　|
　　　　　　　.|　　　　ヽ　＼∧＿∧　　　 (⌒＼|_＿./　/

0764デフォルトの名無しさん

2011/08/26(金) 17:08:16.56

なんか話そうぜ
おれはこんなビット演算してすごい損害出したとか
マ板向きか

0765デフォルトの名無しさん

2011/08/26(金) 20:55:51.67

　　／￣￣＼
　／　　 _ノ　　＼
　|　　　（ ●）（●）
.　|　　　　（__人__）
　 |　　　　　｀ ⌒´ﾉ
.　 |　　　　　　　 }　　ミ　　　　　　　　ﾋﾟｺｯ
.　ヽ　　　　　　 }　ミ　／＼　　,☆＿＿__
　　ヽ　　　　　ノ　　　　＼　＼／　　　　＼
　　　/　　　く　　＼.　　／＼／　─　　 ─　＼　←>>765
　　　|　　　　　`ー一⌒)　／　（●）　（●）　＼
　　 |　　　　i´￣￣￣＼ |　　　（__人__）　　　 |
　　　　　　　　　　　　　　　＼＿　　｀ ⌒´

0766デフォルトの名無しさん

2011/08/26(金) 23:53:47.40

ビット演算を使ってカッコいい告白方法を考えてくれ

0767デフォルトの名無しさん

2011/08/27(土) 00:16:24.67

きみと0xA|0x5としたい

0768デフォルトの名無しさん

2011/08/27(土) 00:34:53.57

16進記法はカッコいいというよりいかがわしいな

0769デフォルトの名無しさん

2011/08/27(土) 09:29:04.30

Oxfordをまともに読むことさえできない私も
自分の心に素直にありたいんだ！

0770デフォルトの名無しさん

2011/09/01(木) 07:59:17.75

0x(f or d) だから、0x000f ですね

0771デフォルトの名無しさん

2011/09/06(火) 16:24:35.09

1100000010

0772デフォルトの名無しさん

2011/09/06(火) 16:27:27.89

まつがえた
1100000100

0773デフォルトの名無しさん

2011/09/07(水) 03:14:37.62

304h＝772d だけど、何の意味が？

0774デフォルトの名無しさん

2011/09/07(水) 03:34:05.45

1100000110

0775デフォルトの名無しさん

2011/09/07(水) 16:02:51.58

>>773 ＋２だけど、これはただの通りすがりかな

0776デフォルトの名無しさん

2011/09/07(水) 16:04:46.34

＋２だけど、その二進数で何やりたいの？ or 言いたいの？

0777デフォルトの名無しさん

2011/09/07(水) 16:29:30.97

1100001001

0778デフォルトの名無しさん

2011/09/07(水) 16:59:57.91

いいかげんにしろ池沼

0779デフォルトの名無しさん

2011/09/07(水) 17:42:39.63

1100001011

0780デフォルトの名無しさん

2011/09/08(木) 14:37:28.79

1100001100

0781デフォルトの名無しさん

2011/09/08(木) 19:10:58.20

おれ、この0が全部1で埋まったらハローワーク行くんだ

0782デフォルトの名無しさん

2011/09/09(金) 01:28:45.54

しかしながら埋まることはないと思います

0783デフォルトの名無しさん

2011/09/09(金) 01:28:59.38

まさにフラグなわけだな

0784デフォルトの名無しさん

2011/09/11(日) 00:20:26.25

1111111111

0785デフォルトの名無しさん

2011/09/16(金) 16:54:50.08

>>767
0xA0|0xFに見えた

0786デフォルトの名無しさん

2011/09/18(日) 03:11:42.46

0xAnull 0xFac ですね

0787 ◆0uxK91AxII

2011/09/18(日) 06:54:43.70

you & I, 相性はAだって。

0788デフォルトの名無しさん

2011/09/18(日) 16:20:17.35

じゃあビット演算で哲学しようぜ
f(x)=1&x の逆関数を考えてみてくれ
実数から複素数に拡張するように
何かを拡張させてもいいので

0789デフォルトの名無しさん

2011/09/18(日) 18:29:27.55

偶数か奇数かってことだから、あまり面白くないのでは？

0790デフォルトの名無しさん

2011/09/18(日) 19:17:59.53

奇数ならFizz
偶数ならBuzz
それ以外ならFizzBuzzと表示させよ

0791デフォルトの名無しさん

2011/09/18(日) 20:03:35.80

いやあ、& や | が非可逆なのが不便に思えてさ。
undo できないよね。計算によって情報が減るというかさ。
計算しつつも元に戻れるような
情報量の減らない論理演算体系が作れないかなぁ
xor は自身が逆関数だからいいよね。（いいかは知らないけどw）

0792デフォルトの名無しさん

2011/09/18(日) 20:08:35.98

フレトキンゲートでぐぐれ

0793デフォルトの名無しさん

2011/09/18(日) 22:31:27.73

ググった。量子コンピュータの話なのね。
可逆計算理論を初めて知った。めっちゃ面白い。
ロムるわ。ありがとう。

0794uy

2011/09/19(月) 07:43:58.00

>>792
こういう何もわかってなくて単語だけ知ってるゴミはどうすればいいんだろうな

>>793
煙に巻かれてるお前もゴミお前なんだけど

マジレスで教えておいてやるけど
量子コンピュータは、「完成しない」

技術的にではなくてね、。
それを作らずとも、人のやりたいことは達成出来るから

ようは速いコンピュータがほしいんだろ
俺はコンピュータの演算速度が-0秒になるところまではみている

0795uy

2011/09/19(月) 07:51:05.46

ようは、人がそこの0秒演算のPCを手に入れちゃう位置にたどり着いても
まだ量子コンピュータは遠い

けど作れないことはない

でも、コストや費用的に、「もう作らなくていいんじゃね？ｗ」ってなる

量子コンピュータは世界と世界とを結ぶ原子核を再帰させて
並列処理ではなく再帰を並列にみせかける再帰並列処理をやろうとしてるから
それをやると、複数の世界の「世界」そのものの力を借りた演算速度になる

俺は0秒演算のPCまで出来たら満足だけど、
そこまでやろうとする奴いるかねぇ
数百万年とか、数億年とか、適当な未来予測は普段なら出来るんだけど
量子コンピュータの完成日については、まったく予想が不可能、

もしこれが完成するとしたら、現在いる俺よりもさらに上のスペックをもった奴が、地上に光臨しない限り　作られない
いわば突然変異みたいな感じ
人がアメーバみたいな生き物から、科学発展をさせたあの「奇跡」を、もう一度起こすぞｗ　くらいの確率でしか
量子コンピュータは完成されない　俺であったら2兆年くらいあれば作れるかもしれない

0796uy

2011/09/19(月) 07:55:25.99

あー　ひとつ方法はあった
俺が結婚して、子供を作り
そいつに技術力のすべてを教え込む
それを何世代か繰り返せば、量子コンピュータの短期完成はありえるかもしれない

けど俺は基本的に結婚の予定はないんだけど

0797デフォルトの名無しさん

2011/09/19(月) 10:20:26.74

気持ち悪い

0798デフォルトの名無しさん

2011/09/19(月) 10:46:15.96

まずいよきみ

0799793

2011/09/19(月) 21:36:58.96

いろいろ調べてると量子コンピュータはあんまり関係なかったかも。
可逆計算理論の話ね。

0800デフォルトの名無しさん

2011/09/19(月) 22:07:49.86

久しぶりにキモいのを見た
キモッ

0801デフォルトの名無しさん

2011/12/06(火) 17:25:24.02

最近気付いたんだが
(x + y) / 2より(x + y) >> 1と書いてある方が何故か安心する

0802デフォルトの名無しさん

2011/12/07(水) 05:45:03.44

今どきどんなアホなコンパイラでも同じコード吐くだろ

0803デフォルトの名無しさん

2011/12/07(水) 06:10:17.11

俺作のアホコンパイラは同じコード吐かない
はい論破

0804デフォルトの名無しさん

2011/12/07(水) 07:37:53.25

いやそれ、自作のコンパイラがアホだと言ってるだけだから。

0805デフォルトの名無しさん

2011/12/07(水) 12:46:03.47

VCだと、対象がsignedの場合に除算とシフトで結果が変わるから、
除算だとその補正のためにcdqとsubが挿入されるね

(x + y) / 2u と書けばシフトと同じコードになる

0806デフォルトの名無しさん

2011/12/07(水) 13:15:49.31

一応念のため補足。除算とシフトで結果が異なるのは対象がsignedで負の奇数のとき
-1 / 2 == 0,　-1 >> 1 == 1
-3 / 2 == -1,　-3 >> 1 == -2

signedを(2^n)で割る演算は基本的に cdq -> sub -> sar になる
cdq, sub は負の場合に+1するため

0807デフォルトの名無しさん

2011/12/07(水) 13:20:32.53

二分探索のバグの話を聞いてからは
x / 2 + y / 2 と書きたくなる
加算でオーバーフローしないのか考えるのはめんどくさい

0808デフォルトの名無しさん

2011/12/07(水) 13:29:26.23

>>807
オーバーフローせずに平均値を求める： ((x^y)/2)+(x&y)
上でも出てる負数の問題を気にしないなら ((x^y)>>1)+(x&y)

0809806

2011/12/07(水) 13:37:17.04

ミスってた…まあ分かるだろうけど
(正)　-1 / 2 == 0,　-1 >> 1 == -1

0810デフォルトの名無しさん

2011/12/07(水) 17:36:56.35

それ以前に優先順位の違いで事故るから
x + y / 2 == x + (y / 2)
x + y >> 1 == (x + y) >> 1
基本的にやめとけ

0811デフォルトの名無しさん

2011/12/08(木) 00:57:45.17

>>733
int IncBit(int char_code) { retrun 'A' + ++char_code % 26; }
int DecBit(int char_code) { retrun 'A' + --char_code % 26; }
こんなんで十分じゃね。あとはコンパイラが上手いことやるだろ。

>>737
調子に乗るなボケ。

0812デフォルトの名無しさん

2011/12/08(木) 01:00:34.71

>>746
これ逆の減算をみたことないんだよな
考えてみれば、わりと簡単なのかもしれんけど

0813デフォルトの名無しさん

2011/12/17(土) 01:58:45.38

byte INPUT_NOT1=0x16;
byte INPUT_NOT2=0x17;
byte INPUT_NOT3=0x18;
byte INPUT_NOT4=0x19;
byte INPUT_NOT5=0x20;
byte INPUT_NOT6=0x21;
byte INPUT_NOT7=0x22;
byte INPUT_NOT8=0x23;
byte INPUT_NOT9=0x24;

こんなふうにバイトに値を変換しておくと早く軽くしょりできるのでしょうか？表記は間違ってないでしょうか？

0814デフォルトの名無しさん

2011/12/17(土) 02:25:19.23

Cの初心者スレに行け

0815デフォルトの名無しさん

2011/12/17(土) 12:01:58.02

多分それではより遅く動く。

0816 ◆0uxK91AxII

2011/12/17(土) 12:18:02.57

ふつー、こうなるよね。
byte INPUT_NOT1=~(byte)1;

0817デフォルトの名無しさん

2011/12/17(土) 17:18:07.34

何がしたいのかわからん

0818デフォルトの名無しさん

2011/12/17(土) 17:30:04.08

エスパー検定です

0819デフォルトの名無しさん

2011/12/18(日) 05:14:37.56

８ビットのポートの入力（Ｌアクティブ）じゃないかと想像したが、
単なる通し番号でビット位置になってないし・・・

0820>>813

2011/12/18(日) 13:21:42.45

すごく恥ずかしくなってきました/////

0821デフォルトの名無しさん

2011/12/18(日) 13:27:15.41

何かが間違ってるのはわかってんだから今さら気にすんな
それよりどういう事だったのか説明しろ
気になるんだよ

0822>>813

2011/12/18(日) 14:19:42.89

実は格ゲーのコマンド入力に使うものだったのですが、初心者のクセに独自アレンジを繰り返してこんなことに・・・

0823>>813

2011/12/18(日) 14:20:09.63

今見ると俺にも謎ですね>>813

0824デフォルトの名無しさん

2011/12/18(日) 15:15:43.45

基本ができてないうちから技巧に手を出すなよ
まずは変数と定数の区別とか、型変換とくに汎整数拡張についてCの教科書で学んでくれ

0825デフォルトの名無しさん

2012/01/23(月) 03:05:56.74

0826 忍法帖【Lv=6,xxxP】

2012/01/23(月) 04:16:22.21

down

0827デフォルトの名無しさん

2012/01/23(月) 05:44:20.14

←→

0828デフォルトの名無しさん

2012/01/23(月) 05:58:58.56

<<&&++--||>>//

0829デフォルトの名無しさん

2012/02/15(水) 04:14:17.00

A/Dを読んで（ダイヤルの左右回転度合い）、変化量を求めるのに、加重平均を
とるやり方を知らなかったので、「前の値との差の絶対値が７以上」とかのアホな
判定してた。平均をとればLSB付近のばたつき成分が消えるんだよね。

0830デフォルトの名無しさん

2012/02/15(水) 20:10:30.67

直前までの平均と現在の値が与えられたときに、平均てどう更新したらいいと思う？
データの個数がやっぱ必要かな

0831デフォルトの名無しさん

2012/02/15(水) 22:35:08.94

>データの個数
データの中身（どう変化するのか）で考えたほうがいいんじゃね
変化量があまりないときは、単純計算できるような

0832デフォルトの名無しさん

2012/02/16(木) 00:49:14.72

ビット演算カンケーねー

フィードバック型とか
out=in*0.001+out*0.999;

もしくはダウンサンプルすればいい
if(count<10000){
tmp+=in;
count++;
}else{
out=tmp;
tmp=0;
count=0;
}

0833デフォルトの名無しさん

2012/02/16(木) 19:34:00.47

>ビット演算カンケーねー
めんごめんご
画像で、でかい範囲の平均化とか一つずれるたびに再計算するのも何だからと思って。

0834デフォルトの名無しさん

2012/02/16(木) 23:02:34.13

ああ、画像認識の境界判定とかかな。
きょうびググれば分かるんじゃね。

0835デフォルトの名無しさん

2012/02/17(金) 09:14:01.51

>>832 私がやったのは、out=out*C-out+in*(1/C); って方式でした。
Cは８か１６ぐらい。Cがどの位だとin のばたつきが均されて結果のつきが遅れないか
というあたりがよく解らないままやってたんですが、その辺、なんか助言ください。
>>832の前者と比べて、-outがあることで何が違うのかな？

0836デフォルトの名無しさん

2012/02/17(金) 16:08:23.50

データの傾向もみんで、当てずっぽうでやるのかい
非力なマシン使ってた頃ならありかもしれんけど

0837デフォルトの名無しさん

2012/02/17(金) 17:22:14.39

その方法に限るならその形は全部 IIR フィルタになるから
ノイズと信号の周波数特性を考えてじゃあどの係数の IIR フィルタを使おう、と決める

でも信号処理は無数にやり方あるし
やりたいことで全然作り方分かる
君の今の情報じゃデータの特性も要求も真っ暗で
全然基本の手法も絞れん
真っ暗闇で相談するより
ググって同じことやってる人見つけて
真似る方が早いよ

0838835

2012/02/18(土) 05:15:39.17

指示されて使ったときは、温度A/D12bitや、電波入力レベルA/D12bitでした。
出力パワーに反映、わりとゆっくり変化→ゆっくり反映　という感じでした。

使ってみたらよかったかな？と思ったのは、ダイヤル入力A/D10bit→受信周波数
微調整の箇所です。指で回す→周波数の追随が良い、だけどノイズは拾いたくない
ぐらいの条件ですね。作ったハード屋さんはこの入力をこの出力に反映してねしか
言わないんです。

0839デフォルトの名無しさん

2012/02/18(土) 13:10:37.30

計算式教えてもらったら、動くとか思ってるのかよ

0840デフォルトの名無しさん

2012/02/19(日) 05:21:12.46

まあここでできるのはいろいろ体験談をサジェストするくらいだろうね
どれが最適かまではデータみないと絶対わからないし
特定の２手法のどちらが適しているかすらも言えることはない

0841デフォルトの名無しさん

2012/02/19(日) 10:47:09.40

ところでこのスレのタイトルを見てくれ、こいつをどう思う？

0842デフォルトの名無しさん

2012/02/19(日) 15:23:13.06

ビット演算に掛け算は入りますか？

0843デフォルトの名無しさん

2012/02/19(日) 15:33:14.32

二乗とか平方根とかのこと？

0844デフォルトの名無しさん

2012/02/19(日) 19:43:55.62

ビット演算ていうと、AND, OR, XOR, NOT, シフトだけじゃないかと思う君。

0845 ◆0uxK91AxII

2012/02/19(日) 21:36:28.55

rotate

0846デフォルトの名無しさん

2012/02/20(月) 03:07:48.29

じゃあせっかくだから平均化に特化した平均化手bit演算を語ろうか

0847営利利用に関するLR審議中＠詳細は自治スレへ

2012/04/03(火) 02:32:51.88

if(a>b)swap(a,b); はどうにかできない？

p.s.
このへんにためてけばよくね？
https://gist.github.com/gists/search?q=bit-manipulation

0848営利利用に関するLR審議中＠詳細は自治スレへ

2012/04/05(木) 15:25:40.82

t=(a^b)&(0-(a>b));
a^=t;
b^=t;
これでいけるかな？

0849営利利用に関するLR審議中＠詳細は自治スレへ

2012/04/05(木) 16:04:16.89

いいんじゃないかな

ただこれが例えばソートの中とかで使われるなら
比較結果は偏るので予測が効いて単純な分岐の方が速くなる可能性が高い
さらにaとbがメモリにあったりすると分岐を排除したら常にストアが発生して具合が悪かったりする

0850デフォルトの名無しさん

2012/04/13(金) 22:47:51.39

00001001001
という13個のビット列を周期的に繰り返して得たいのですが、
下よりコストの少ない方法がありましたら教えてください。

main() {
uint8_t bit, bitcount;

bitcount = 0;
bit = 0x49; // 0b01001001;
for ( ; ; ) {
if (bit & 1) {
// 1の処理
} else {
// 0の処理
}

bit >>= 1;
if (++bitcount == 13) { // リセット
bitcount = 0;
bit = 0x49; // 0b01001001;
}
}
}

>>850 専ブラ用

0851デフォルトの名無しさん

2012/04/13(金) 23:12:49.36

bit = 0x49; // 0b01001001;
for ( ; ; ) {
if (bit & 1) {
// 1の処理
bit |= 1 << 13;
} else {
// 0の処理
}
bit >>= 1;
}
とかどう

0852デフォルトの名無しさん

2012/04/13(金) 23:23:36.19

ROT13の話かと思ったら全然違った牛乳

0853デフォルトの名無しさん

2012/04/13(金) 23:25:22.67

>>851
おおおおお！かなりよさそうです。
ありがとうございました！

0854デフォルトの名無しさん

2012/04/13(金) 23:30:28.10

アセンブラだと右シフト後のキャリーをMSBへ移動するってことか

0855デフォルトの名無しさん

2012/04/14(土) 01:07:43.71

for(;;){
//0の処理
//0の処理
//0の処理
//0の処理
//0の処理
//0の処理
//1の処理
//0の処理
//0の処理
//1の処理
//0の処理
//0の処理
//1の処理
}

0856デフォルトの名無しさん

2012/04/14(土) 11:41:03.94

マジックナンバー埋め込んだらアカンよ

0857デフォルトの名無しさん

2012/04/14(土) 14:21:09.24

？
>>850も>>851も埋め込んでると思うが

なんなら>>855のアセンブラを生成してからそこにジャンプするようにすれば良くね？

0858デフォルトの名無しさん

2012/04/14(土) 14:33:54.72

即値はバグの温床になるから気を付けろという意味

0859デフォルトの名無しさん

2012/04/14(土) 14:40:03.86

そんな唐突に bit 演算スレに向いてない説教されても。
別スレ行って説教した方がいいんじゃないの？

0860デフォルトの名無しさん

2012/04/14(土) 14:42:58.08

そんなカッカするなよw

0861デフォルトの名無しさん

2012/04/14(土) 15:01:35.90

>>851
uint8_tは8bitだから
bit |= 1 << 13;
はダメですぞ

0862デフォルトの名無しさん

2012/04/14(土) 15:58:36.63

じゃあ
<bit |= 1 << 13;
>bit = 0x49;
で

0863デフォルトの名無しさん

2012/04/14(土) 20:06:57.39

え；

0864デフォルトの名無しさん

2012/04/14(土) 21:44:37.23

>>850
ビットが11個しかない件について

元の値を壊すと大変だからコレでいいんじゃね？
uint_fast16_t const bits = 0x49; // ビット列(下位13ビットが有効)
for(uint_fast16_t mask = 1; mask & 0x1fff; mask<<=1) {
if(bits & mask) {
// ビットが1の時の処理
} else {
// ビットが0の時の処理
}
}

最初からビット列を左右反転しておけば僅かに速いかもしれない
uint_fast16_t const bits = 0x1240; // ビット列(下位13ビットが有効)
for(uint_fast16_t mask = 0x1000; mask ; mask>>=1) {
if(bits & mask) {
// ビットが1の時の処理
} else {
// ビットが0の時の処理
}
}

0865デフォルトの名無しさん

2012/04/14(土) 21:48:34.10

>>864
> 13個のビット列を★周期的に繰り返して★得たい

0866デフォルトの名無しさん

2012/04/14(土) 22:18:08.63

そんなのビット列の初期化以外を好きなようにforで囲めばいいじゃないか

0867デフォルトの名無しさん

2012/04/14(土) 22:35:09.57

>>866
＞★下よりコストの少ない方法★ がありましたら教えてください。

全体をforで囲むのは>>850と本質的に同じ
uint8うんぬん以外は>>851でいいと思うんだけどねえ

0868デフォルトの名無しさん

2012/04/14(土) 23:31:47.64

結局>850よりいい答えがないw

0869デフォルトの名無しさん

2012/04/15(日) 00:22:00.51

>>850です。
>>851氏の方法で解決しましたが、bitのuint8_tは、
たまたま00001001001が8bitの範囲に収まる値だったからで、
状況によっては10101010101だったり、ビット列が増えたりなんてことも
ありえましたので、あまり気にしないでください。

0870864

2012/04/15(日) 01:52:34.81

>>867
ベンチマークしてた＆寝ちゃったので遅くなってゴメンよ～

<VC++2010 64bit>　1位:864の下
　2位:851(1位との差は多分気にする程じゃない)
　3位:864の上(2位との差は多分気にする程じゃない)
<VC++2010 32bit>　1位:864の下
　2位:851(1位との差は多分気にする程じゃない)
　3位:864の上(遅すぎ。多分レジスタが足りなくなった)
<mingw-gcc 64bit>
　1位:864の下(一番内側のループが13個のパターン化したmovに置換され超高速。ifの中身が簡単すぎたかも)
　2位:864の上(一番内側のループが13個のパターン化したmovに置換され超高速。ifの中身が簡単すぎたかも)
　3位:851(1位2位の約4倍遅い、VC64/32の1位より僅かに速い。)
<mingw-gcc 32bit> mingw-gcc 64bitと同じ

864の上はVC32bitで遅すぎてダメ。
864の下は速いけどビット列を反転して用意しなければならない。
gccの最適化を期待するなら864のどちらでも。
851は最適化はあまり期待できないけれど、どのコンパイラでも遅くなる事は無い。gccでの結果は気にしないで。

<結論>851でOK

ってここまで書いて置いたら「ビット列が増えたりなんてことも...」
>>869 そういう事は早く言えｗｗ

ソースおいとくので暇な人は実行してみて(汚い＆無駄になったケド)
http://ideone.com/S1zzg

0871デフォルトの名無しさん

2012/04/15(日) 02:10:44.08

>>853でとっくに解決したって言ってるのになんで蒸し返すの(´･ω･`)

0872デフォルトの名無しさん

2012/04/15(日) 02:23:55.14

>>870
if の中身が簡単じゃないとそもそもボトルネックにならんだろうよ

0873864

2012/04/15(日) 06:30:40.83

>>871
蒸し返すっていうかポツポツ話が続いていたので便乗してみただけ。ただしコストを下げるって事に
過敏に反応してしまったのは悪かったけど。
>>872
「ifの中身が簡単すぎるとボトルネックにならない」って意味でいいんですよね？
それはその通りでgccでは差が出すぎてしまったので、その結果は採用せずに851氏(今まで氏を付け
てなかったスミマセン)のコードでという結論になりました。

以下駄文というかスレチですので無視して結構です>>>
何故864を書いたのかというと851氏のはビットが 1 の場合演算が1回増える&依存関係があるので
コンパイラの最適化（アンロール）に支障が出てしまうと思ったからです。アンロールできれば
実行コストが下がり有利になる(最後のシフト命令が省略できる等)はずでしたが、結果が余りにも
極端すぎたのとifの中身の処理が大量にあった場合アンロールされなくなり、逆に不利になる場合も
あるので通常は851氏の考え方でいいんじゃないかという気がします。
汎用性が無いとダメとの事なので意味無かったんですが、依存関係を無くすとか、左右反転してみる
とかの工夫は実行コストを下げるという意味において大事だと思ってます。考え方古いかな。

0874 ◆0uxK91AxII

2012/04/15(日) 14:43:50.16

『ビットがxの時の処理』
っていうのが重杉て、書いている部分の最適化なんて誤作同然になると思うけどね。

0875デフォルトの名無しさん

2012/04/16(月) 00:00:06.25

そのとおり。
そして当該処理が簡単な時は実行時に>>855を動的生成するようなコードを書いてそれに jmp すればよろし

0876デフォルトの名無しさん

2012/04/16(月) 00:09:40.10

forでループ組むよりノベタんで書いたほうがよくね？

0877デフォルトの名無しさん

2012/04/16(月) 03:18:16.98

即値はバグの温床（笑）

0878デフォルトの名無しさん

2012/04/16(月) 04:00:46.42

はああああああああああああああああああああああああ

0879,,・´∀｀・,,）っ-○○○

2012/04/20(金) 08:12:48.71

>>850
こういうのはどうだろ？

static const unsigned int bits_org = 0x80000049;
static const unsigned int mask = 0xFFF80000;
unsigned int bits = bits_org;

for (;;) {
if (bit & 1) { /* 1の処理 */ }
else { /* 0の処理 */ }

bits = bits >> 1;
bits = (bits & mask)? bits : bits_org;
}

x86なら論理積で条件フラグ更新するのはtest命令だけでできる。
強いて言うならビット逆転しておいたほうがいいと思うよ。右シフトより加算の方が速いCPUのほうが多いはずだし。

0880デフォルトの名無しさん

2012/04/20(金) 09:08:47.02

さすがだんごさん
スレの空気が引き締まったな

0881デフォルトの名無しさん

2012/06/23(土) 10:34:30.16

この流れなら貼れる
ttp://ocw.ouj.ac.jp/tv/1542109/08.html

0882デフォルトの名無しさん

2012/06/23(土) 10:43:06.20

このスレにそんな基礎中の基礎の話を今更必要としてる人はいねーよ。
岡部先生もおまえみたいな見境のない信者にはうんざりだろう。
いいかげんにしとけ。

0883デフォルトの名無しさん

2012/06/23(土) 10:49:57.74

岡部洋一があほだってことが良くわかる映像だった

0884デフォルトの名無しさん

2012/06/23(土) 20:05:18.14

群馬大学乙w

0885デフォルトの名無しさん

2012/06/24(日) 14:46:44.71

幕張！幕張！

0886uy

2012/06/25(月) 16:38:51.34

andとorを
xorだけですませる為の分かりやすいサンプルください

0887デフォルトの名無しさん

2012/06/25(月) 18:48:31.85

ではまず屏風から虎を誘き出してください

0888デフォルトの名無しさん

2012/06/26(火) 13:33:35.02

最初にぱんつを脱ぎます

0889デフォルトの名無しさん

2012/06/26(火) 13:52:30.69

脱いだぱんつを履きます

0890デフォルトの名無しさん

2012/06/26(火) 17:19:27.80

これを高速で繰り返します

0891デフォルトの名無しさん

2012/06/26(火) 17:38:23.41

バターが出来上がります

0892uy

2012/06/26(火) 18:21:16.28

はーしね

0893デフォルトの名無しさん

2012/06/26(火) 22:33:57.53

そんな基礎から判らないなら電子回路の本でも借りて読んだ方が早い

0894uy

2012/06/28(木) 14:31:12.57

やっぱ2chのスレってこの程度だよね

さっさと死んでおけよゴミ共

0895デフォルトの名無しさん

2012/06/28(木) 20:13:00.61

ではお得意のルビーでお手本をお願いします

0896デフォルトの名無しさん

2012/06/28(木) 20:14:46.21

andとorでxorじゃねえの？

0897デフォルトの名無しさん

2012/06/28(木) 20:33:18.13

最近みんなWin8が糞すぎてピリピリしてんだよね
あまり怒らせない方がいい

0898デフォルトの名無しさん

2012/06/29(金) 00:06:52.77

andやorをxorから合成するのは端的に言って無理だよ。
(a+b-(a^b))>>1
とかやっていいなら話は別だけど。

0899デフォルトの名無しさん

2012/06/29(金) 12:15:19.20

真理値表も読めない馬鹿が混じっているのか。

0900デフォルトの名無しさん

2012/06/29(金) 12:38:29.46

P = A xor B のとき

C(out) = A・B + (A + B)・C(in)
が
C(out) = ~P・A・B + P・C(in)

になるそうですが
C(out) = A・B + P・C(in)
じゃだめなんですか？

0901デフォルトの名無しさん

2012/06/29(金) 13:41:04.79

勿論、だめじゃありません。

0902デフォルトの名無しさん

2012/06/29(金) 16:30:24.14

まあその状況でxor使う必要もないけどな
結局
A&B | (A|B)&C
を
A&B | (A^B)&C
にしてるだけだから、何の利点もない
オペランドが片方だけ真になるときはxorはorの代用として使える、というだけの自明な話

0903デフォルトの名無しさん

2012/06/29(金) 18:12:17.87

教科書の Manchester Carry Chain のところで出てきた式なのですが
どうしてわざわざ無駄なことをしているのでしょう？

0904デフォルトの名無しさん

2012/06/29(金) 18:14:17.85

つ ttp://en.wikipedia.org/wiki/Carry-lookahead_adder

0905uy ◆pdu1UZmweE

2012/07/02(月) 05:45:22.98

>>898
無理じゃないよ
実際に最近俺がそういうコードを書いてしまったが
読み解くのが面倒だったから聞いただけ
むしろ逆に
or and でかける範囲のアルゴリズムのいくつかをxorで置き換えられるってだけな気がするけど

0906デフォルトの名無しさん

2012/07/05(木) 04:35:27.74

ベン図見ながら考えた。A and B ＝ not(A xor B) だよね。
A or B は、xorとandのorで、xorとandは補集合だからここのorはxorでも同じ。
A or B ＝ not(A xor B) xor (A xor B)　　これで合ってる？

0907デフォルトの名無しさん

2012/07/05(木) 06:30:48.57

>>906
間違ってる

0908デフォルトの名無しさん

2012/07/05(木) 06:36:03.78

四通りしかないんだから自分で確かめてみたらいいよ。
まずは A=0, B=0 ね。

0909デフォルトの名無しさん

2012/07/05(木) 13:54:42.73

>>906
ベン図なんて見なくていいから真理値表を見よう。
--
A B AorB AandB AxorB ~A ~B C<-~AandB D<-Aand~B　 CorD
0　0　　0　　　0　　　　0　　1　 1　　　　　0　　　　　　0　　　　　0
0　1　　1　　　0　　　　1　　1　 0　　　　　1　　　　　　0　　　　　1
1　0　　1　　　0　　　　1　　0　 1　　　　　0　　　　　　1　　　　　1
1　1　　1　　　1　　　　0　　0　 0　　　　　0　　　　　　0　　　　　0

0910デフォルトの名無しさん

2012/07/06(金) 07:53:22.72

xorとnotだけじゃandにはならんだろ
逆はできるけど

0911デフォルトの名無しさん

2012/07/06(金) 09:53:23.78

>>910
どうやって証明できます？

0912デフォルトの名無しさん

2012/07/06(金) 12:00:03.33

xorとnotではand/or/nand/norなどが書けないことを帰納法で示す

0913デフォルトの名無しさん

2012/07/06(金) 12:25:51.28

xorは>909の真理値表から判るように前項と後項が等しい場合(以下条件1)同じ結果(値は0)になる。
また、前項と後項が異なる場合(以下条件2)も同じ結果(1)になる。
条件1で前項を否定(not)すると条件2になり、やはり同じ結果(但し値は1)になる。
条件2でも同様に条件1になり、これまた同じ結果(但し値は0)になる。
勿論前項を否定する代わりに後項を否定しても、全く同様の結果になる。

and/or/nand/norを生成するためには条件1か条件2のどちらかで結果が異ならないといけない。
何故ならばこれらの演算では条件1で値が異なるし、仮に前項を否定した場合も条件2で値が異なる。
にも拘らず、xorとnotだけでは条件1或いは条件2で値が異なる状況を生成できない。
従って、xorとnotだけではand/or/nand/norが生成できない。

0914デフォルトの名無しさん

2012/07/06(金) 12:49:43.44

アプローチはあってるけど証明にはなってない

0915913

2012/07/06(金) 12:55:02.94

試しに説明を試みたが、証明するところまでは考えなかった。
つーか、私にゃ無理w

0916デフォルトの名無しさん

2012/07/06(金) 13:21:31.08

xor と not があれば
A xor B
not (A xor B)
以外に
not A
not B
が作れるだろ
だから何でも作れるのが正解

0917デフォルトの名無しさん

2012/07/06(金) 13:30:12.35

え？

0918デフォルトの名無しさん

2012/07/06(金) 13:31:05.14

最後の一行以外は、誰でも知ってるが
何故「だから何でも作れる」なのか

0919デフォルトの名無しさん

2012/07/06(金) 13:36:21.07

じゃあand作ってみなよ

0920デフォルトの名無しさん

2012/07/06(金) 21:25:28.64

彼は「ひとつ、ふたつ、たくさん」の国から来たんだよ
温かく迎えてやれ

0921デフォルトの名無しさん

2012/07/06(金) 21:43:01.99

1変数ブール関数の国から来たんだな

0922デフォルトの名無しさん

2012/07/06(金) 21:44:29.63

グループA（xor/not）からは、グループB（and/or/nand/nor）を、グループBのどれか一つが無ければ作れない。

なんだか階層構造があるみたいだな。数学で既に誰か考察してそうだが。

0923デフォルトの名無しさん

2012/07/06(金) 21:48:25.36

xorは桁上がりしない足し算？

0924デフォルトの名無しさん

2012/07/07(土) 16:31:07.33

yes

0925デフォルトの名無しさん

2012/07/07(土) 17:03:38.97

1入力、1出力の関数は全部で4個。
素通し、いつも0、いつも1、NOT。
NOTは、もう一段NOTで「素通し」にできる。
「いつも0」「いつも1」は、どちらか片方とNOTがあれば、もう片方にもなる。

2入力、1出力の関数は全部で16個
NAND、NOR、~A AND B、~A OR B、A AND ~B、A OR ~B の 6 個が、
それ1個で他のどれも作ることができる。
AND、ORは、他にNOTを組み合わせる必要がある。

XORとNXOR（XNOR）は自己双対なので、組み合わせて他の論理を
作ったりはできない（常に1とか常に0なら作れるけど）。

今ざっと考えてみたところそんな感じだと思う。

0926デフォルトの名無しさん

2012/07/07(土) 19:27:52.54

とりあえずサラっと書いてみた。
http://www1.axfc.net/uploader/Sc/so/360310.pdf

0927デフォルトの名無しさん

2012/07/07(土) 19:29:24.61

あ、ごめん。
表にちょっと誤りがあるわ←おっちょこちょい

0928デフォルトの名無しさん

2012/07/07(土) 19:36:02.24

http://www1.axfc.net/uploader/Sc/so/360312.pdf
修正入れた。

0929デフォルトの名無しさん

2012/07/07(土) 21:30:12.13

>>928
乙。

0930デフォルトの名無しさん

2012/07/08(日) 00:44:40.13

簡易っていうか、これで十分厳密な証明じゃないの？

0931デフォルトの名無しさん

2012/07/08(日) 00:45:39.94

>>905がどんな面して出てくるか

0932926

2012/07/08(日) 02:00:05.83

簡易だよ。証明のための表をいきなり与えてるし。
本当なら一々式変形やって、「ほら、(not (A xor B)) xor A = not Bはいつも正しいでしょ？」とかって片っ端から言う所。

0933デフォルトの名無しさん

2012/07/08(日) 07:47:24.49

いまどきはCoqで。

0934デフォルトの名無しさん

2012/07/08(日) 09:09:26.60

そういえば、3not 問題って、俺まだよくわかんないんだった。

0935uy ◆Qe4wwDKtLk

2012/07/11(水) 17:37:38.19

アホしかいないのな
^ と ! から
完璧な｜と完璧な＆　作れとか言ってねーからさ
どこで何を勘違いしたんだ、
特定ケースのみでいいから正しく動作するサンプルをね、所望していたわけだけど
もう自分のソース解析して大体理解したからもういいよこの雑魚スレ
&と|を^で置き換えるショートコーディングの技術解説してるのをどっかで見たんだけどな
そのころはまだ自分が絶対記憶能力を持つ前だから忘れてるわ

0936デフォルトの名無しさん

2012/07/11(水) 17:50:25.36

> andとorを
> xorだけですませる為の分かりやすいサンプルください

これを

> ^ と ! から特定ケースのみでいいから正しく動作するサンプルを所望

と読める人はいないよ

0937デフォルトの名無しさん

2012/07/11(水) 17:55:47.89

つーかスレ内検索しただけでわかるけど、こいつ完全な統失電波さんだな
触らない方がよかった…

0938デフォルトの名無しさん

2012/07/11(水) 18:13:10.05

まだNGしてなかったのかよ

0939デフォルトの名無しさん

2012/07/11(水) 18:38:10.33

見えないけど（見えないから？）、何について話しているかわかった

0940デフォルトの名無しさん

2012/07/12(木) 00:50:50.83

ツンデレんがわゆ

0941926

2012/07/12(木) 02:46:18.91

>>935

えっ？

0942デフォルトの名無しさん

2012/07/12(木) 02:52:23.99

>>935
にほんごは　ただしく　せいかくに　かつ　じゅうぶん　ぐたいてきな　かたちで　つかいましょう。

日本語に限った話じゃないし、プログラマならなおさらそうするべきなんだがな。

0943uy ◆Qe4wwDKtLk

2012/07/12(木) 23:50:19.92

「わかりました。大丈夫です。まかせてください」

つって、勘違いしたままいらねーもん開発してる典型じゃん
この流れ

謝れ

0944デフォルトの名無しさん

2012/07/13(金) 07:48:07.38

おいおい、上流工程さんよ
わざわざ要求を不正確に伝えてきたのはそっちじゃんよ。
俺は目の前にある仕様を正しく表現した。俺の仕事は全うし、責任は果たされた。

謝れ

0945デフォルトの名無しさん

2012/07/13(金) 19:12:10.37

and でも or でもないのを、 and とか or とか言ってたわけだね。
わけだね。

0946デフォルトの名無しさん

2012/07/13(金) 23:19:36.10

うん。

0947,,・´∀｀・,,）っ-○○○

2012/07/14(土) 11:35:51.86

NANDかNORのどちらかならまだしもXORで全ての論理ゲート表現するってのは新しいなｗｗｗ

0948uy

2012/07/14(土) 13:55:03.52

人は数字に弱い
人は再帰にはもっと弱い
人は二進数にも弱い

0949,,・´∀｀・,,）っ-○○○

2012/07/14(土) 15:20:59.60

uyは頭が弱い

0950uy

2012/07/14(土) 15:46:35.26

ゴミか

0951デフォルトの名無しさん

2012/07/14(土) 15:49:55.35

うん
uyはゴミ

0952 ◆0uxK91AxII

2012/07/14(土) 16:12:42.00

nandも書いたら可哀想だよ。

っと。

0953デフォルトの名無しさん

2012/07/14(土) 16:20:22.84

norだけはガチ

0954デフォルトの名無しさん

2012/07/14(土) 16:46:17.93

誰うま

0955uy

2012/07/14(土) 17:26:36.92

ショートコーディングすらできないゴミカス共

さっさと謝っとけよ

0956デフォルトの名無しさん

2012/07/14(土) 20:44:57.98

ごめんなさい。

0957デフォルトの名無しさん

2012/07/15(日) 15:23:26.43

いやnandeもない

0958デフォルトの名無しさん

2012/07/15(日) 16:38:17.61

あー、いるよねー。
「ゴルフできるレベル＝必要最低限の技量」だと思ってる人。
いや確かにショートコーディングはそれ単体で深みのある分野なんだけどさ。

「and」が「少なくとも両方共tの時tになる二項一般論理演算」か何かを指すと思い込んで
説明なしに使った挙句指摘されて逆切れするってのは

ゴルフが出来るとか、ポインタや再帰を超高速で扱えるとか、
半年ごとに新しく言語を実装する過程でバッククォートカンマアットの最も簡潔な実装方法について半年おきに同じように悩んだりとか、
去年は最初のセクタに置くことにしていたブートストラップを、El Toritoの規格に合わせるように18セクタ目あたりに移す作業を休日の暇潰しにやったりとか、
あるいは自作の言語や自作のOSに関する話をGoogleのサマーインターンシップへの面接中に楽しんだ挙句
六本木ヒルズ森ビル26階でC言語系の某コンパイラの改造に取り組んでその夏を過ごしたりとか、

そういう技術レベルに関わる以前の問題なんだけどなぁ。

物質的でないもの、形のないものを扱う職業なんだから、
伝える時は「誰が読んでもそうとしか取れないように」書き、
受け取る時はその事を前提にして「誰が読んでもそうとしか取れなかったように」読むもんだと思うんだけど。

0959デフォルトの名無しさん

2012/07/15(日) 16:49:43.90

今日は暑いからね。仕方ないね

0960926=958 ◆tAo.kQ2STk

2012/07/15(日) 16:58:49.95

仕方ないね。暑いしね。

0961デフォルトの名無しさん

2012/07/15(日) 19:01:38.28

>>943
この流れの中でいらねーもん開発したのはお前だけだけどな。

0962デフォルトの名無しさん

2012/07/16(月) 13:39:53.75

次スレのスレタイどうするかねぇ。

とりあえず素案
【分割統治法】ビット演算　0x04

0963デフォルトの名無しさん

2012/07/16(月) 23:09:17.65

__builtin_clz が使えるかどうかの判定ってどうすればいいのかな。

ちょっと調べたらコンパイラのバージョンで判定してて、
直接的に __builtin_clz の有無を判定できるようなマクロはないみたいだけど。

0964デフォルトの名無しさん

2012/07/17(火) 02:43:46.25

>>963
autoconf 使いたくないならハンネにyuって書けよ

0965デフォルトの名無しさん

2012/07/17(火) 09:59:23.24

「ハンネ」ってなに?
まさか、「ハンドルネーム」なんていう間違った表現を更に短縮して
悦に入っている馬鹿とも思えないし、なんか意味があるの?

それはさて、「yu」ってのも判らんが……

0966デフォルトの名無しさん

2012/07/17(火) 10:48:48.60

俺は964じゃないけども、通じてるなら良いんじゃない？

それとも「ホームページ」に始まり「時計皿」やら「催眠術」やら「性癖」やら、その類の
間違って訳されたか、間違って使われることが多い用語に片っ端から突っ込まないと気が済まないわけ？
俺は別に構わないんだけど、やったことがある立場から言わせてもらうとただただ疲れるだけだぜ？
※時計皿は観察する(watch)皿の誤訳、催眠術は該当する語が無かった時代に研究者が見学して「眠気を催す術だ」と誤解したことから、性癖は生来の「性質」からくる癖のこと。

yuってのは多分uyの事なんだろうなぁ。

0967デフォルトの名無しさん

2012/07/17(火) 12:26:17.01

俺は963だけど、964のレスは意味不明だな。

0968デフォルトの名無しさん

2012/07/17(火) 13:01:30.93

いや、まったく通じてないから。

0969デフォルトの名無しさん

2012/07/17(火) 13:41:18.93

ハンネで通じるとか言ってる966は964なんだろうなあ

uy並の脳の壊れ具合。

0970966

2012/07/17(火) 15:04:13.17

脳の壊れ具合は否定出来ないけど、一応別人だよ。

ど田舎から電話回線でチャットしてた日も、10年近く前の事になるのか。
語彙も変わるわけだ。

0971デフォルトの名無しさん

2012/07/17(火) 15:11:51.74

うちは脳の壊れ具合は一緒だけど、一応別人だよ。
10年前はもう光化してたな

0972デフォルトの名無しさん

2012/07/17(火) 22:08:22.08

コレがモノホンのアスペか。

0973デフォルトの名無しさん

2012/07/18(水) 01:05:47.63

ハンネは隣国の変なチョンゲーを想像しますた

0974デフォルトの名無しさん

2012/07/18(水) 11:30:00.31

掲示板が違えば語彙は違う、ということを認識できないだけ

0975デフォルトの名無しさん

2012/07/18(水) 11:45:51.19

ttp://pds.exblog.jp/pds/1/200707/13/10/c0106010_12234370.jpg
これみたいで格好わるいお

0976デフォルトの名無しさん

2012/07/18(水) 12:01:34.77

それはペンネ。

0977デフォルトの名無しさん

2012/07/18(水) 12:06:42.01

ミネストローネにペンネを入れて、翌日に持ち越したら鍋の中が大変なことになった。

0978デフォルトの名無しさん

2012/07/18(水) 12:22:13.48

ああ
むかごみたいになるんだよな

0979uy

2012/07/25(水) 08:39:59.80

>>958
俺思うんだけど、
最適化などを手動で行う事もなくなってきた今
このビット演算を現代で最も使ってるのはゴルフだろうに

このスレってずいぶんおかしな流れになってんのな
ビット演算をゴルフ以外のどこで使ってるんだよ
まさか変数情報関連の「簡単な初期化」にしか使ってないとかいわないよな

そういうレベルで火病っているなら死ね

0980デフォルトの名無しさん

2012/07/25(水) 11:31:03.82

元々の論点はそこじゃないと思うぞ。
「誤解を招かない言い方をしろ」を長々と言っただけ。
重箱の隅を楊枝でほじくるのが楽しいのはよくわかるが

0981デフォルトの名無しさん

2012/07/25(水) 18:13:50.04

>>979
> 最適化などを手動で行う事もなくなってきた今
おめーはそういう仕事してないからな。

ていうか、よく恥ずかしげもなく書き込みできるよな。
できるよな。

0982デフォルトの名無しさん

2012/07/25(水) 18:39:10.19

組み込み系だと最適化禁止だったりするからねぇ。
お蔭様で、どこにregister宣言つければスタック消費量を抑えられるかなんていう
くだらん経験値が増えちまったw

0983デフォルトの名無しさん

2012/07/25(水) 19:02:38.41

組込み系だと、じゃなくて、腐ったコンパイラを使わざるをえなかったりすると、だろ？
ワークステーションだろうがメインフレームだろうが同じ。

0984982

2012/07/26(木) 01:22:56.14

んにゃ、最適化すれば普通にローカル変数をレジスタに置いたり、
無意味なループは消滅させたりするだけの最適化できるコンパイラ使っているんだけどね。
依頼元のソースにvolatileがなかったから、最適化禁止の理由も判るってもんだ。

0985デフォルトの名無しさん

2012/07/26(木) 01:50:51.93

コンパイラは基本的に値については推論しないから
技巧的なビット演算と同じ物を
最適化で実現できるかと言われると微妙なところ

もちろん本来的に、最適化コンパイラが十分な性能のコードを吐けるなら
それで何の問題もないはずではあるのだが

レス数が950を超えています。1000を超えると書き込みができなくなります。

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

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