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

前スレ
【高速化】ビット演算　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

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

Intelはともかく、テーブル作ればいいんじゃない？
8ビット分のテーブルがあるとして

return
　table[ n & 0xff ] << 24
| table [ (n >> 8) & 0xff ] << 16
| table [ (n >> 16) & 0xff ] << 8
| table [ (n >> 24) & 0xff ] ;

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

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

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

ああ、あれね。

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

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

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

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

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

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

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

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

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

更に6バイト縮んだぜ

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

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

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

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

if(hr & (DIERR_INPUTLOST | DIERR_NOTACQUIRED))

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

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

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

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

保守あげ

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

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

以下のような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;
}

短くと言うのは、ソースの行数なのか実行文のサイズなのか？

ソースなら
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];
}

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

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

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

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

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

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

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

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

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

gccだよ>AVR

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

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

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

適当に命令セットを見ながら速そうに書いてみた。
とはいえAVRは使ったこと無いからどうすれば速いかよく分からんけど。

unsigned char d;
h &= 0x1F;
d = (h>>4|h<<4);//swap 命令使ってほしいなっと
d = d-1 & 9;
h = h+d & 0xF;
return h;

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

return (h & ~48) % 55;

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

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

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

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

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

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

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

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

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

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

これでどうだ？

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

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

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

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

ていうか、この方が短くなるんじゃないか？
if (h > '9') h -= 7;
　return h & 0xF;

これを分岐無しにするともっと長くなりそうだが。
int n = (h > '9');
h += n;
n <<= 3;
h -= n;
return h & 0xF;

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

cpi, brvs, subi, andi, ret

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

お世話になっております。

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

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

要らないはず。

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

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

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

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

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

分岐無しのほうを頭捻って1命令 短くしたつもり
しかし分岐使うほうにまだ1命令負けてるのがなぁ

unsigned char d;
h = h + 0x41 & 0x9F;
d = (h >> 4) | (h << 4);
h = h - d & 0xF;
return h;

あげ

あげ

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

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

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

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

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

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

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

ハッカーのたのしみp90

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

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

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

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

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

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

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

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

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

(i%10)["0123456789"]

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

同じだよ。

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

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

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

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

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

同じだよ。

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

NLZって？

ニュージーランド

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

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

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

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

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

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

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

あげ

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

お願いします。

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

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

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

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

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

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

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

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

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

一般変形としてはこんな感じか。
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)))

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

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

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

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

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

もしくはこうかｗ

y + srl(x, 31) * z

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

>>107
それはないｗ

じゃあこれで

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

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

a

ほしゅ

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

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

あんまり変わらなかった

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

反復深化？

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

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

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

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

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

あ

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

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

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

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

unsigned reverse_add(unsigned x, unsigned y) {
do {
unsigned c=x&y;
x^=y; y=c>>1;
} while(c!=0);
return x;
}

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

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

>>127
そーでしたorz

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;

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

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

ぐはぁ。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最近このスレを読み始めた新参だが、気になったので倍数判定法の作り方を探してみたらニコニコがひかっかった。
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では微妙かもな。
まだ最適化できる気がするが飽きた。

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

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

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

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

俺が使ってのはこんなの。
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;
}

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

今更だけど

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

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

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

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

自分で書いたほう、ここが限界か・・・？

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;

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

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

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

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

X=(X+3)&~3;

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

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

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

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

日本語でOK

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

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

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

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

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

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

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

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

>>174
無限ループだね。

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

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

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

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

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

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

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

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

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

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

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

>>179
解析魔法少女美咲ちゃんマジカルオープン！
http://www.amazon.co.jp/exec/obidos/ASIN/4798008532

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

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

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

The Art of Computer Programming.

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

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

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

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

>>141 60 で割り切れるか

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

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

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

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

シトロネラール臭もする

test eax, 3
>>195
x86だとこんな感じかな。悪くない。

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

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

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

訂正

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++なんかでライブラリを書いたりもする

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

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

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

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

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

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

バイト列の各ビットを、それぞれ独立した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;
　　}
　}
}

PMOVMSKB

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>234 == >>237 == baka

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

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

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

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

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

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

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

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

ヒント:夏休み

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

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

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

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

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

>>251
算術シフト・・・

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

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

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

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

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

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

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

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

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

引き算しる
0ならループ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

クヌースと墓寺

枕好き法

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

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

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

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

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

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

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

早い実装は誰かに任せた

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

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

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

これじゃだめかね。

将棋の何の条件だろう

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

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

>>282
あいぢあはそれでいい
16個連続してたときの扱いにバグが有りそう
平均で連続するのは4個か5個だから16分割4bitだともったいない
huffmanとか出現頻度で長さが変わるコードにすれば
もっと圧縮できると思うけど
そのテーブルを81bitに含めるかどうかでも変わってくる

81ビット中、1は15個、0は66個

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

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

それ先頭に1が15連続したとき 3*15 + (81-15)/3 = 67
15個の場合すら未クリアで>>285に劣るようだけども

と思ったら1→10 001→111 で解決するな

81ビットの先頭から見ていって、
1が出てきたら10を吐き出す、
01が出てきたら110を吐き出す、
001が出てきたら1110を吐き出す、
0001が出てきたら1111を吐き出す、
0000が出てきたら0を吐き出す。

>>285,290
要するに、ハフマン符号化？

0が連続する確立が他界から00->0はいいとして
それ以外は逆にbit数殖えちゃうんだよもん

>>293
(0001)^15 0^21

>>290
(01)^15 0^66

(01)^15 0^51 orz

>>280
1になるビットの最低個数は0？

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

>>280
これって、数え上げ符号でいいんじゃないかな？

遅いんじゃないの？

>>299
当初の仕様では1になるビットの最低個数は０でしたが、
今は立ってるビットが極端に少ないときは32ビットまで絞ろうかなーとか思ってます。
よかったら32ビットで何個のビットまで対応できるかもアドバイスください。

>>285をみて理解できた完璧だとか言えるなら全体のbit数に応じて出現最大bit数を計算する応用は出来るはずだろ

>>303

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

出現頻度が常に0>1ならハフマン符号化でいいんじゃないの

データ長 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の出現をカウントし 最大数に達していたら終り

ハフマン符号化の亜種

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

ちゃくちゃくと将棋の終盤戦の圧縮アルゴリズムに向かってるにおいがしてきました…

81bitの約数を選んだだけじゃないの？
というかハフマン符号化について調べてないよねきっと。

将棋の終盤戦で、各々の持駒数計が22個もあるような状態ってよくあることなの？

詰め将棋だとしてもこの持ち方は非効率的だろ

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

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を許容する　　と思う

orz
3bitごとにひとまとまりのデータと見立てた場合でかつ、上であるほど出現頻度が高い場合の符号化パターン
を書こうとしたら誤爆した。

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

そうですね。
期待していた以上の回答がもらえました。
ありがとうございます。
32ビットへの圧縮だと8ビットを1ワードとするくらいのほうがいいですかね。

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

それで効率悪くならなければそれでもいいんじゃない？

実データがある程度作れるなら、辞書持った方がいいと思うけどなあ

ハフマン符号化とか情報理論の勉強初めて一番最初に習うようなもんだと思っていたが

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

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

一日三回くらいまで

多い日も安心

>>320
81Cx <= 2^32 を満たす x までじゃないかなぁ

てか、ビット数も出現率も分かってるんだから、
理論限界値はシャノンの定理で算出できるだろＪＫ。

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を吐く

敬体と常体が入り交じる文章って流行ってるの？

コピペの継ぎ接ぎを読み過ぎてそのように学習してしまったのでしょう
意味が通じればいい、まさに理系の鏡です

鑑。

檻

加々見

今回は高速化数え上げ符号を使いました

4個でいいなら8bitづつにわけて絶対アドレスでおk。

>>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
となり、条件を満たす。

どこの誤爆なんだろう？

>>330
だんごってどれが目なの

´　｀

まじで！
それ眉間のしわで・・が目だと思ってたわ。。。

・・は、ほっぺのりんごですね

>337の所為でもうそのようにしか見えない……_/⌒|○

,, が目とか

◎が目だろ？

・∀・）っ-○◎●
,,・´∀｀・,,）っ-○◎○
明らかに・が目だろ。,,が頬だから・が頬というのはありえん。´は眉だよね？

,,・´∀｀・,,）っ-○◎○
あぁん？俺のダンゴが食えねえってのか？

△と□と○なら、おでんですね

-○◎○

ネギま？

●は最近品切れ？

無職になってクレカ審査通らなくなったらしい

オセロってもう完全回答出たのかな？

出てないよ

オセロはいいよな。8x8マスがちょうど64ビットにおさまって。

一マス保持するのに1.6ビットほど必要だけどな

オセロのビットボードで１マス２ビット以外の実装はしない

ビットボード（笑）ってシフトとかややこしくなるのに速いわけないと思ってるんだが

>>353
このあたりを見てもそう思えるかな?
ttp://www.amy.hi-ho.ne.jp/okuhara/howtoj.htm

普通シフトはしないよ。
ANDとifの羅列だよ。

普通は1マス3ビットだろ

ああ、失礼。

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

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

色以外の情報は何なの？

空き

色毎に置ける置けない

それを持たせるのはどうなの

常に持たせるのは無駄

さすがに将棋でビットボードはないよな？

思いっきりあるよ

1ワード27ビット×3レジスタくらいかな

人口無能を用意しない場合でも自動パス位は必要だからね
2ビットに成るか3ビットに成るかの分かれ目はＡＩの有無

それはない

>>365
掛ける7

だんごさんってこんな人だったっけ。
以前見たレスでは結構賢そうな印象だったけど。
別人なのかな。

本物のだんごはしばらく見てないと思う

馬！鹿！団子！だよ

>>369
前からこんなんだよ。
知ったかぶりしたり大口を叩いたりして自分を不利な状況に追い込んでからの
ディベートを楽しむ人。

組込み開発だ度で、あまり特殊的ではなく、汎用的に使える
ビット演算をまとめてライブラリ化したいと思うけど、
何をピックアップしたらいいのだろうか？

あはは、馬鹿だこいつ

局所的な最適化のためにやるんであって、
変な汎用化をするくらいなら普通に書いてコンパイラに任せなよ

ここ最近のGCCは賢すぎて小手先のテクはあんま意味無さ過ぎる
やるとしたらアルゴリズムレベルでの再考が必要

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

>>376
昔のGCCがアホすぎただけだろ？

そうとも言う

アホの子のほうがかわいい

GCCがなかったらプログラマは今頃もっと幸せだったはずだ

CodeWarrior を使わざるをえなくてもそう思うか!

現在のGCCでも変数の局所性はあまり生かせてないらしい。

>>354
外人はビットボードに掛け算を持ち込んでくるからすごいよな

ビットボードの掛け算って、行列の掛け算みたいな感覚？

>>383
それ何のための計算？

>>354
だとttp://www.amy.hi-ho.ne.jp/okuhara/bitmob.c
のimullのことかな？チェスだと
ttp://chessprogramming.wikispaces.com/Sliding+Piece+Attacks
あたりかね？横方向だけじゃなく縦方向や斜め方向の連続したビットを切り出す感じかなぁ

パイプライニングが職人技すぐる。
現行CPUではAtomでくらいしか役に立たないけど。

奥原さんって一時期は国内有数のオセロプログラムの作者だったけど
今はもう冷めたのかな
これだけの腕があるのに勿体無い

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

これそのまま？

>>389
ごめ、数字の頭が$だったので、１６進に見えたｗ

頭が $ で16進って、何の表記法だったっけ？

モステクノロジー6502 だとか、モトローラ系のアセンブラ、
あとは vz のマクロで使う表記だと思ってたよ

俺はPascalの書き方だと思った

>>124
キャリーの逆ができる回路ってx86CPUに無いのかな？
x86以外ではこれができるCPUってある？

>>123のような命令があるとかなり最適化の
幅が広がると気がするんだけどどうなんだろ
あんまり使い道ない？

そもそもそんなことが要求されるアプリケーションを知らない。
利用頻度の低い回路を実装することほど無駄なものは無いからな。
まあビット逆転なら高速化方法がいくつかあるが

>>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) と簡単になる。

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

pshufbで各バイト4ビットずつビット逆転するとか

この命令の回路って実装の手間とか実行のコストは普通の加算命令と同じだよね？

こういうのは汎用化し辛い。

だんごさんはFPGAやASICには興味ないの？
既存のCPUで満足なの？

満足じゃなくたって、まさかCPUは作れないじゃん。

作れるけど、性能が一昔前なんだな。
たとえばNios II、一般品だとクロックが500M出るのは御の字。

っつーかFPGAでCPU作ってもメリットあまりないだろ
FPGAはCPU使わずに演算した方が高速

こんなのよりよっぽど欲しい命令ならいっぱいあるから
D = (A & B) | (B & C) | (C & A)

とかな

32bit符号なし整数同士の加算でアセンブラを使わずに桁あふれをチェックするいい方法はないでしょうか？
if ( ( x + y ) < x ) {
　　...
}
今のところこれが一番速いのですが

>>394
キャリー先読みの関係で順序入れ替え回路を挟まざるを得ないと思うけれど、そんなニッチな状況に特化した命令を用意するかどうか…

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

利用頻度次第じゃね？
FPGAですらFull Adderとかのよく使う回路は固定機能化されてることが多いぞ

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

ウンチビット　って何だろうと思ってしまった。

>>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 までは分岐の前にやってくれるとか。

>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
とコンパイルした。ちょっと微妙?

zl = xl+yl;
zh = xh+yh+(zl<yl);
ってことか。割と頭いいな gcc。

if (zl < xl)
という比較はいらないの？

Z = mod(X+Y, 2^k)
X+Y<2^k ならば Z>=Y。
対偶をとって
Z<Y ならば X+Y>=2^k。
Z<Y さえ満たせば それで判定ＯＫ。

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

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

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

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

-masm=intel にして出力しなおしてから読むべし

ある変数が0かどうかを分岐無しで調べる方法ってありますか？
ビットが全部0なら0、一つでも立っていたら1みたいな感じで。
無理ですかね？

分岐するより遅いものしか思いつかん

Cなら!!xでいいんじゃね。gccにコンパイルさせてみたら
xorl　　%eax, %eax
setne　%al
になったんで十分かと

>>419
少し速くなりました。
なんか既視感を感じるなと思ったら大昔に自分でそのコードを
書いたのを思い出してしまいました。
どうも退化しているようです。
ありがとうございました。

xorlとcmplだとcmplの方がレジスタへの書き出しを伴わない分速かったりするのかね？

うん、ここ最近のx86の実装では条件フラグ更新と汎用レジスタ更新は同時にはできない。
後続の条件フラグ更新命令の検出で演算をキャンセルすることで

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

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

あげ

乱数x から [a, b)かつ偶数or奇数の乱数 に写像するビット演算ってどうなりますか？

偶数or奇数の乱数の意味がわからね
(x%(b-a))+aじゃダメか？

偶数か奇数か固定したかったら1回左シフトして適宜1をorすればいいと思うよ。

>>427
なんとなくだけど、左シフトはあんまり
よくない気が。
ANDでLSBを0にするほうがいいと思う。
疑似乱数的に考えて。

そこは発生器の質に依るだろう

全ビット詰まってないならシフトした方がいいし
全ビット詰まってて上位ビットほどランダムならシフトしない方がいいし
全ビット詰まってて全ビットがランダムならどっちでもいい

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

>>429
といっても、そういう期待以上のものは
なかなかないだろうな。

発生器にも統計的な国際基準の規定があるから一定の質を期待してもいい

文字通り固定するなら分岐使った方が速いんじゃね？

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

>>433
偶数固定時にaが奇数かつn=aの場合とか、
奇数固定時にbが奇数かつn=b-1の場合…

あげ

保守

age

スレチかも知れませんが
ビットフィールドの定義順って
実際のビット順に反映されますか？
あと先に定義書かれてる方と後の方とでは
どっちが上位ビットになりますか？
例えば64ビットのときのメモリ上のバイト順は？

仕様書読め

処理系依存でFA

お前ら全然役に立たないね

お前には負けるよ

スレチかも、ではなく
スレチである！出てけ！

>>441
処理系依存なら仕方ないだろ

例えばライフボートのIAR ｃのマニュアルでは、デフォがMSBファースト
（ワードのMSB側から割り付けられる）で、#pragma bitfields=reversed を書くと
LSBファーストになる、と書かれてる。441が使うｃでその辺の記述を確認しなきゃ
どっちだか判らないだろ。今は多くがルネ系で、これならMSBファーストがデフォ。

うんちく

Big Endian と Little Endian は英語の言い回しが変が感じがするが、これはガリバー旅行記のリリパット (小人) 国の

話から来ているためである。この国では、卵を小さい方の端から割るように勅令を発した国王の支持派 (Little Endian)

と、しきたり通り大きい方の端から割る反対派 (Big Endian) が争いを起こす。この言い回しは、小さな違いが大きな事

態を引き起こしてしまうことを意味していて良くできていると思う。

それで、どこからコピーしてきたんだい？

1行置きに空行入れんな

>>446
うんち君乙

http://video.google.co.jp/videoplay?docid=6267783675810924557#

ワロタw

ウンチビット

価格のわりに処理速度がすげー速いマイコンって何になる？

>>453
今時の組み込みだとSH、ARM、ATOM辺りかなぁ？

atomってマイコンなのかへー

それを使ってアトムを作ってほしい

マイコンって何かね？

マイコンピュータ
デスクトップにあるやつ

誘電体に雲母を使った（

うちのアラジンのクラシックなストーブも雲母使ってあるな

ま、いーか

ttp://www.yogkan.co.jp/image/top_logo_image/product_top/maikon.png

ビッテンザン

ushortのポート読みとり値がLSB2bitより大きく変化したら、という判定をするのに
　if( ( (current>read) &&
　　　　(current-read)>=3 ) ||
　　　( (read>current) &&
　　　　(read-current)>=3 )　 ) {
とやってるんですが、なんかもう少しスマートな演算がありそうな気がします。
どうすればいいでしょうか？

if( ((current^read) & ~3) != 0) {...

464のコードはLSB2bitより大きく変化ではなくて差が3以上ならばだよね
そういうこと？

>>465
current=5, read=3とかの場合>>464の結果と違う事にならん？

LSB2bitより大きくの意味が曖昧でわからない
仮に>>464から 差が3(11b)より大きいの意味だとすると
(current-read)>=3 ではなく (current-read)>3 とすべきなのでは

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

abs(current-read)

int>shortの環境ならこうすることもできそうだね
if( (unsigned)(c-r+2) > 4U ) {...
int=shortの環境は知らないがw

皆さんありがとう。読んだ値はA/D値なので、LSBは揺らいでいるから変化を見ない
ようにしたいんです。>=3ではなくて>3のほうが判定が軽いならそれでもいいです。
>>465で判定が軽ければ、５→３の変化を拾ってしまってもいいかも・・・　あ！
捨てるマスクを3bitにすれば７→３で４変化だから、引き算>3と同じ判定になるかも。
どうでしょうか？

A/Dの読みが何bit有効かでやり方変わるでしょ

10bitです。つまみの回し具合を取るもので、10bitの0〜1023を、数値の60.0〜0.0
になるように補正して使います。出力値も10bitなのですが、LSBまで変化を拾って
しまっては、bitシリアルな出力コマンドの数が出過ぎるので、間引きしたい訳です。

10bitの中の上から8bitを有効にするとかじゃダメなの？

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　の間で振動するかもしれないからダメだということでしょ。

CPUがどうのってほどの話じゃなさそうなんだが

めんどくさい、1024個のテーブル作っちゃえ！

表引き嫌いな人っているんだよね

cur = ADC >> 2;
if (read != cur) {
read = cur;
}

だよなあ。正規化したいなら
cur = ADC & ~3; とかでいいわけだし。

生データとって、パソコン上でやり方考えたほうがいいんじゃないの？

表現の簡潔さで>>476ですか。でも判定の重さは変わらないようですね。
（このＣのabsは関数コールになるので）　やはり変えないでおきます。
相談に乗ってくれてありがとうございました。

>>483
だから abs() ならコンパイラがイイ具合にしてくれるかもしれないと言ってるんだ。
コンパイラと CPU の組み合わせによっては関数呼び出しではなく、もっといいものにしてくれる。
出荷時に予定している最適化オプションでコンパイルして出力を見てみるといい。

それは確認しました。インテル系ではなくH8S系で、インライン展開される機械語は
割り込みmask操作系、eepmov系、左右ローテート系　ぐらいしかありません。
　if( abs(curr-read)>=3 ) {　は、R6=curr-read で JSR　@abs：24 が出ます。
重さは同じなので、今度書くときには表現の簡潔さでこちらを使うとおもいます。

D/Aは8bitしかないのに何難しく考えてるんだろうね？

(x ^ (x>>31)) - (x>>31)

>>487
算術シフトであることを言わないと。

シフトやら論理積やらしなくてもいいんじゃないか？

INVALID_RANGE = 7; // 差分がこの範囲(-3 〜 +3）は無視する
LOWER_BOUND = -(INVALID_RANGE / 2);

((unsigned)(current - read - LOWER_BOUND) > INVALID_RANGE) ? "ok" : "ignore";

C言語の規格には詳しくないので、これがどの程度ポータブルなのかわからん。
キャストする代わりに、0ではなくINT_MINに片寄せするほうがよいのかも。

>>486
ものにも因るけど、音とかだったら、
折れ線近似程はやらないとダイナミックレンジかせげんちゃう？

それなら、机上じゃなくて
生データとって、パソコンでデータ解析とかやったらいいんじゃん
アルゴリズムとかも生データ見ながらのほうがいいと思うけど

考えすぎなだけのような気がするけど

>>491
音は無条件に下の方がつぶれるよ
人間の耳の感度が対数特性持ってるから…

なに言われてるのか、さっぱり...

2ch は心の荒んだ人の溜り場だな

いまのフレームのカウントから
n秒おきに処理するには
どう計算するのが速い？

n秒おきつっても
前の処理が終了してからn秒後に次の処理を始める
前の処理を開始してからn秒後に次の処理を始める
の2通り考えられるしなぁ

フレームあたりの時間が安定していると仮定するなら(1/60sとか)、
PITみたいにフレーム毎に
A--;
if(A==0){
A=B;
event();
}
するのが良いかと

ははぁ、さてはヒヨコを餓死させたな＞495

fpsに合わせて関数テーブルつくって、間接呼び出しするとか
余計な判定いらないし

>>495-499
スレタイをご覧ください。

ジッタは許容するもの

ひよこ？
自動餌やり器か何かをコーディングするためにビット演算スレで質問ってこと？かわいい！
↓
バグ混入によりひよこが３２７６８日分の餌に埋れて死亡

それは餓死と言うより圧死だな

たまにブログを読んでると Binary Hacks という本がちょくちょく眼に入って気になるんだが
俺らには関係ある話？

目次見ればわかるだろうに
http://www.oreilly.co.jp/books/4873112885/#toc

x & -x
で最下位ビットを取り出せますが、最上位ビットはできませんか？

x >> (sizeof (unsigned int) * 8 - 1)

506ですが自己解決しました

マスクしろよ
(x >> (sizeof (unsigned int) * 8 - 1)) & 1

>>506のいう最下位と最上位の意味が違ったようだ。
先頭／末尾から数えて最初の1だけを取り出すって意味ね

AMDは次の世代のCPUでTZCNT命令を追加する予定のようだね。
新命令を作るよりは今あるBSR/BSFを速くしろと思うんだが。

これが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はもっさりテクノロジー

ゲハでやれ

インテルのCPUは自分の息のかかったベンチさえ速ければ
それで売れるからな

メディアは広告ばんばんだしてやれば、
勝手にインテル有利のベンチだけの提灯記事書いてくれる

さらに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機能はおまけ程度に見ておいた方がいい。

今度は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ユーザーには積極的に高速なディスクを組み合わせて使ってもらいたい。

自作PC板に帰れ！

むしろ宗教板だな

あげ

>>506
ちなみにどうやったんですか？
一発でとれるんですか？

hacker's delightには506も含めて色々載ってる、Webで一部読めるし
ビット演算は左に伝播するため
xの型がわからなければ無理、が教科書的な回答じゃなかろか
それらの技術を駆使すれば
Boostに「熟練したプログラマでも云々」ってソースにコメントが書いてあるNextCombinationを
ビット演算とfor文だけで実装出来たりして面白い

>>519
検索したら見つかったけど、長いから採用しませんでした。

大文字と小文字を逆転させるコード考えたのですが
もっといいのないですか?

c ^= c >> 1 & (c - 1 & 31) + 38 & 32;

見せびらかしたかったんだね

まず実用性がないな。
その程度ならテーブル引いたほうが速いんじゃね？

というか大文字と小文字を逆転する意味が不明。
たとえば大文字を小文字に変換（あるいはその逆）ならそれなりにあるけど
（大文字小文字区別なしの文字列検索・置換処理とかね）

んでもってこの手の処理はSSE*とかで纏めてやったほうが速い。
実際glibcのSSE対応パッチなんかも出てる

ちょっとした遊びだろ
意味が不明とか言ってやるなよ

もしその処理が必要な箇所が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では分岐って遅くないですし。

スレというか流れ的にはどう見てもASCII限定コードにしか見えん
>>522はS-JIS判定コードのノリだと思うんだが

char型がsignedがunsignedかによって結果違ったりするのかと思ったけど同じだった（エラーになるコードも）

ASCII限定のつもりでした、実用性は考えてません。
大文字変換なら c |= 小文字変換なら c &= ~() にすればOK
8bitなら、~(c >> 2) & を加えればOK
実際に半々とかで分岐する場合、分岐は今でも遅いんじゃないか?

分岐とかをビット演算に直す理論とか考えたら面白いかな、と思って書いてみました

どうでもいいけど分岐は今でも遅いだろ

↑ゴミは黙っててくれ

とゴミが申しております

#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なんかだとこれ、全く分岐の無いコードにしてくれるよ

でっていう

>>533
俺の環境(Phenomでvisual c++ 2010)だと10000回で
分岐: 1845ms
522の方法: 1113ms
522をSSEで: 73ms
だったぞ

糞しょぼ

なあ、c ^= 0x20 じゃいかんのか？

お前はアスキー表でも眺めてろ

SSE4.2使えると本当に便利だな
c ^= pcmpestrm(c, [A-Za-z]) & 0x20

そんな命令あったのか。やりたいことそのものな命令だな

俺は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回（マスク生成）＋論理積に置き換えるのは頭の悪いやり方

訂正

movdqa xmm0, [src]
movdqa xmm1, xmm0
paddb xmm1, [diff_lower]
pcmpgtb xmm1, [cmp_lower]
pandn xmm1, [exch_mask]
pxor xmm0, xmm1

つーか、考えたら+1して101 < c ? 100 : 0でもOKか
cmovとかsbbとか使えばSSE使わなくても分岐の無いコードは書けるよ。

ミスった
c = (101 < (signed char)(c+1)) ? c ^20 : c;

チラチラチラウラデ

>>543
そりゃそうだよ、522も本質的にはcmovと同じ
(c - 1) & 31 + 38
をすると5bit目がフラグの代わりになる
'a'と'A'の下五桁が00001なので

理論的に面白いかなと。
テーブルを与えると、自動的にそのテーブルと同じ出力のビット演算を出力するツールとか

ビット演算とシフトの数学みたいなの考えればいいのだけど

暗号のS-boxをビット論理式に展開するツールなら既に作ってたりする。

BSF命令のSSE版ってありますか？

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

ごめんなさい
xmmレジスタを128bit整数型と見て、それ全部に対してBSF命令を使いたいんです
destが0〜127になるような

＞(v)cvtpi2psで指数部抽出できるだろ。あとはわかるな。

しょせん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:

ありがとうございます

ptest xmm0, xmm0
jz .bsf128_error

あああ

出だしを書いてみたところでbsf/bsrのlatencyを見て書く気力を失ってみた。
x86ならソコソコいけると思ったのだけど。

分岐除去＆厨テク駆使

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]

cmovnzじゃなくてcmovzな

>>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 ルール

あはは…ヘタレで済まんね、、

ほぼテーブル法だった件

何がしたいんだっていう

>>556
こういうのって自力で見つけたりするの？
専門の本があったりするの？

ダンゴの場合は受け売り

>>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と大して性能変わらないかも知れん

逆だった
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

誘導されてきた。
同じ質問だが、こちらで聞くのでご容赦してくれ。

ビット・オンの最上位のみ残したい場合、
ビットスキャンリバースを使わずに、いい方法ないかな。
ビット・オンの最下位のみ残す場合は、例えば対象の値を80としたとき、

mov eax,80
mov ebx,eax
neg eax
and eax,ebx

こんな感じよね。
これをビット・オンの最上位でやりたいんだが、何かいい方法ないかな。
最下位フラグを消していく方法を繰り返すくらいなら、素直にビットスキャンしちまうんだが。

なければ、ない、と言ってくれ。

age

>>565
ビットスキャンリバースって何？
まぁ、効率は悪いけど、ぱっと思いつくのは、
シフト(1→2→4…と必要なだけ)と論理和を繰り返して1を加算後シフト。
最後に、必要であれば、元の数の最上位ビットだけ取り出すとかかな…
何か他にもありそうな気がするので思いついたら、また書く

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

>>567
アンガトさん。
bsr　(Bit Scan Reverse)。bsf　の逆順ですy

おいらにとっては難題なの。
考え始めて早数年。
実現方法はいくらでもあるので、可不可の問題ではない。
でも最下位セットビットに関しては一発二発でいけるわけだから、
どうせならスマートな方法見つけたい。

可能性としては、最大値の商を何とかさへば、どうにかなんべ。
ところがうまくいかんでは。

面倒だからこうする

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サイクルだし。

>>569
一発で行きたいだけなら、fpuのlog使えば？(多分fyl2x当たり)
まぁ、効率が良いかは分からんが…む

>>570-571
さんくす。最上位のみ残すという目的は果たせるね。
正直、浮動小数点数変換考えてなかった。

望んだビット操作とは少しちがう感じだけど、
本懐を遂げることは出来る感じ。
しかも符号付整数には変な感じに対応できる。
笑えるし、要所で使えるかも。

でも、整数除算で何ともならないのは如何ともしがたいところ。

世話になったので借りを返してみる。

>>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ビット符号なし整数乗算できるのがミソ。

こんな感じで、作業内容によってはインデックス（シフト回数）を求める必要はないと思う。
本末転倒でスマン。

書き込んですぐに気づいたが、上記の方法はうまくいかない。
頭わりーな。
paddq xmm7,xmm0
の場合でも、上位６４ビットと下位６４ビットを別に処理しなきゃならん。
３２ビットごとの処理でも、下位の結果を上位に反映させるためのマスク処理必須だし。
結局使えんな。

恩返しにならなくてすまん

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

8bit幅なら表引きとかじゃダメかいな？

>>575
こうしてみると、見やすいですね。
考えてもみれば、非64環境で６４ビットに対応できる貴重な方法だし。
引き出しに入れときます。ありがとう。
変形できそうで、出来ないのが残念。

>>576
今の時代なら16ビットでも問題なさそう。
でも対象ビットが増えたときに、分岐処理が悩ましいのね。

Hacker's Delightを読み返したら>>575と同じ方法だった

負の値のときの処理は確かに考えてなかった。
MSBが立ってるときだけ下位31ビットをクリアでいいんじゃね？

FPUを使うというアイディアはHDを紹介してたブログ主が言及してた。
x87とMMXはレジスタ共有してるからダイレクトにビットフィールドにアクセスできるとか云々

>>579
>>565が本当に欲しい機能が何なのかは分からんが
負の値を考慮した場合、欲しいのは、絶対値に換算後の結果なのか、
単にMSBを無視した値なのかとか、場合によって欲しい結果は違うからね…

bitscanって基本unsignedじゃね？
つーか、cvtsi2ssはソースレジスタはGPRだった。なのでmovd不要。

Javascriptのビット演算が四則演算よりおせぇ。
なんのために付いてんだ？

スクリプトにそんなん求めるな

JavaScriptは数値は全部doubleだから

文字列とかの可変長データを8バイト境界に揃える仕掛けってどうやるんだっけ
数年ブランクがあるから忘れちゃった

>>585
単に8の倍数に切り捨てたいだけなら、n & ~(8-1)

あー！そんなやつです。
ありがとうございます。

n & -(intptr_t)8

閏年判定いってみようか

!(yearFrom1901To2099 & 3)

ビット演算でやるのはパズル過ぎるだろ

76543210
を
7060504030201000
みたいに隙間１ビット開けるのってどうする？

それ1ビットじゃなくて4ビットじゃないのか？

3ビットかも
っていうか間を空けたいっていう例だろ

Larrabeeにbitinterleave命令があるし、グラフィック関係でよく使うのは知ってる。

16ビットならこれが速いかも(pshufbが使えない場合はunpack命令数回で代替）
pshufb→pand→pcmpeqb→pmovmskb

と思ったけどLUT使ったほうがマシだな

とりあえず16ビット→32ビットはこんな感じになります

n = (n | (n << 8)) & 0x00FF00FF;
n = (n | (n << 4)) & 0x0F0F0F0F;
n = (n | (n << 2)) & 0x33333333;
n = (n | (n << 1)) & 0x55555555;

それは1ニブル空ける場合ですか？

判りづらくてすまん、0を00、1を10みたいにしたかったん。
0000b->00000000b
0001b->00000010b
0010b->00001000b
0100b->00100000b
1001b->10000010b
みたいな
特に用途は思いつかなかったんだけどｗ

8Bitのビットマップを8Byteのバイトマップ(0x00,0xff)にするのは
テーブルを持つのが定跡でしょうか？

「バイトマップ」なんていう他人に通じない用語で質問されても困りますが。

たとえば 0x36 を 0x00 0x00 0xff 0xff 0x00 0xff 0xff 0x00 のように展開したいとかそういうこと？

フラグを配列に格納したいとかそんなんじゃないかと予想

>>598
1ニブルなら2行目まででおｋ

白黒Bitmap画像を、グレースケールの0x00,0xffに拡張したい感じです

>>599
ないのかよ！
Graphics Gems Iを読んでみたらビットインターリーブの応用例が出ている。

実用性の無い技術を磨くことほど無駄なことは無いからな。
解ってると思うけど、世の中で役に立つのは自己満足のコード書くことより
必要十分な、他の人が読めるコード書くスキルだからな

>>604
64ビット1ワードで、8*256=2Kバイトか。64ビットマシンでメモリに余裕があるならテーブルでいいんじゃない？

べつに32で2回ロードしてもいいし、それならテーブルは4*16でいいのだが

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
見たいな感じね

おっと、リトルエンディアンだからビットパターン逆か。

このスレダンゴばっかになってるぞ

ダンゴさんが書き込むとスレが引き締まるな。

ご本人は引き締まってなさそう

色々ダダ漏れだもんな

震災後初めて団子みたからちょっと安心したわ。

大丈夫
自作PCあたりで元気に発狂してた

>>612
いちおう今60kg台だ
そろそろ痩せだんごやさんに戻すか

あらかわいい

久しぶりに来たが団子さん元気だな
よかったよかった

ビット演算を用いて
ビットの位を反転させる以下のような演算を行うことは可能でしょうか?

概要:
符号なし整数 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

>>619
× 最上位ビット a
○ 最上位の桁数 a

ｎを(a-4)回左シフト　じゃないの？

掛け算と剰余算と小さなテーブル使っていいなら、適切なテーブル用意して
int revx(int n,int a){
　　return n*table1[a]%table2[a];
}
で行けるけど

ビット演算だけだときつくないか？

何いってんだ俺。
正しくは
return(n*table1[a]&table2[a])%table3[a];

>>619
固定幅の反転は知ってる前提でいいのか？
各固定幅反転コードを各々最適化しておいて switch(a) するのが結局速い

ダンゴさん待ち

みなさまありがとうございます
任意の幅 a に対して処理する必要があるため，今は1ビットごとにループで処理しているのですが
やはりビット演算だけで任意幅は無理があるみたいですね
>>624 の方法で特定の a については分岐する方向で考えてみようと思います

流れをぶち破って本当に申し訳ないんだけどｗこのスレならわかる人がいるだろうと思い質問を

○＋△or□というものがあった場合さ
○＋△の2つと□の1つを＝として捉えてどちらか(or)という風に捉えるのか
○の1つに加えて(＋)△の1つか(or)□の1つという風に捉えるのかどっちなのかな？

記号の優先度とか初歩的な話になるんだろうことが想像出来て恥ずかしいんだけど誰か回答を願いたい
ちなみに数式の時の優先度と物に置き換えた時に記号を充てた時の優先度でも変わるのかどうかとかも

演算子 優先順位

>>627 言語で違うことは無いとは言えないが、少なくともＣとASMでは算術演算子は
論理演算子より優先度は高い。　○＋△or□は、
（○＋△）or□　と解釈される。　○＋（△or□）とするためには明示的にカッコが必要。

2つの符号無し整数a,bがあったとき, aからbで1が立ってるビットのみを拾ってきて
右詰めで返すのを効率良くできたりしますか?
たとえば a = 10110[2], b = 11011[2] のとき 01010[2] を返して欲しいです.

xor?

違った

意味がわからない上に例で何が起きてるのかもわからない

aからbの「から」が分からん。
「拾ってきて」が分からん。
「右詰めで」も意味分からん。

>>663, >>664
bで1が立っているビットしか見ないという意味です.
bで0が立っているビットはなかったことにしたいわけです.

ソース見て、弄るしか

ハッカーのたのしみの7-4

符号無し整数のビット数は？
ビット数が8ぐらいなら、
テーブル参照がお手軽そうだけど、CPUによっては早くなるってわけじゃないからな

bのマスク値から0の位置で分割していって、
別々に処理して結合しかないな。
「右詰め」は人間にしか判らないし。

b1 = 0b11000;
b2 = 0b00011;
t1 = ((a & b1) >> 1) | ((a & b2));
でt1 = 0b01010が得られる。

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;
}
「ハッカーのたのしみ」にずばり載ってたりするの？

今日職場にあるハッカーのたのしみ見たら出てました
みなさんありがとうございます

先ず、1bitずつ転写する事に拘るのをやめる。
立っているbitの数を数えてから、シフトして結果を作ったほうが効率良い。
さらに、ビットカウントをifなしで出来る事を知っていれば、全体でもifもループも要らないよね。

http://www.hackersdelight.org/HDcode/compress.c.txt

＞ ビット演算だけだときつくないか？

オセロ作るときにさ、64bitの変数を白の盤面、
黒の盤面と2個用意して、コマの貼りつけ可能位置を
最速で判定する方法ないかな？

その他人本願的な発想が素敵！！！

×他人
○他力

じゃぁちったぁ自分の考え出すか。
とりあえず、さくっと候補を調べようと思うと

守//守備側
攻//攻め側
候補 = 守<<1 | 守>>1 | 守 << 8 | 守 >> 8 ;
候補 = ( ( 守 | 攻 ) & 候補 ) ^ 候補;

で絞り込めそうな気がする。ある局面でボロが出そうな気もするけど。
あと、八方のひとつに攻め側が存在しないことが解からん。

>>645
テーブル

~(白 | 黒)
で終わりやん

始まってすらねぇよ。

アタック25を見ればわかる
今日やるから

>>645
ほれ
http://www9.atwiki.jp/othello?cmd=upload&act=open&pageid=28&file=othello_counter4.cpp
俺の知る中での最速
何か質問あればどうぞ

>>2
変態かｗ

それこそアセンブラだろｗ

bit 演算気円斬

>>653
ありがとう。じっくり読ませてもらうよ。

ううう・・・SSEを使いたい病気が・・・

つこうてもいいけど

そういやSSE使ってるのもどこかにあったような気が

MMXだった
http://radagast.se/othello/bitmob.c

だんごさんが>>653みたいなプログラム作ったらやっぱぶっちぎりで勝っちゃうのかな

ねーよ

だんご大丈夫

まさかだんごさんから弱音が漏れるとは

128ビットのレジスタがあることだし2並列処理とかできたら効率よさそうだけど
2並列化するメリットってあるのかなと思ってさ

ある局面で着手する側の打てる場所の数と
同じ局面で相手が打てると仮定した場合の数は
それぞれAIの評価関数で使い道があるよ

スレ違いだったらすいません。
C言語で2つの16bit変数同士を加算して、
0xffff以上になる時は0xffffとしたいのですが、
どうやればいいでしょうか？
アセンブラだとキャリーフラグを見ればいいのは判るのですが。

>>667
uint16_t a, b, sum;
sum = (~a < b) ? 0xffff : a + b;

横からだけど、~演算子はビット数を勝手に拡張する場合があるから
((uint16_t)~a < b)ってやらないと危険だと思う

http://www.emit.jp/prog/prog_b.html
こういうのもあるけど、さすがに>>668の方が速いか。

３２ビットレジスタが使えるならこんな感じかなぁ。遅いかもだけどｗ

sum = a+b | (0x80000000-((a+uint32_t(b))>>16) ^ 0x80000000) & 0xffff;

＞ ３２ビットレジスタが使えるならこんな感じかなぁ。遅いかもだけどｗ
ハアアァァァァァァァァアァァァァアァァァァアァアァアアアァアァァアァアァアァァァァ？？？？？？？？？？？？？？？？

私も、ビット演算をしていたらビビっと来ました。
それからは最高の毎日を送っています。

ふつうにif文使えよ。
32ビット演算して値でif。

>>668-669の方法でうまくいきました。
ありがとうございました。

そのビット演算はifより速いのか？
ビット演算使いたいだけちゃうんかと

最適化によってifがcmovになるならifが一番速いと思うよ

x86でもARMでもないかもしれないじゃないか

計測してみた。
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

分岐予測甘くみんなってことだな

それだと分岐版は分岐する・しないを32k回ずつ交互に繰り返すから
予測がほぼ全て当たる状態になるね

まあ実際の運用でも、入力パターンが予測可能かどうかによって分岐のコストは変わる
全然違う例だけどこのへん参考になるね
http://homepage1.nifty.com/herumi/diary/1011.html#24

ブレゼンハムが、分岐予測が当たりにくい、と聞いた

なるほど。
>>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の方が速い謎。

っていうか、これでいいことに気が付いた･･･。
return (unsigned short)((a+b) | -((a+b) >> 16U));

>>683
いや、それでもほとんど予測されちゃうな
大部分はパターン0101...を繰り返すだけだから、パターン認識の餌食に

乱数使うのが手っ取り早いね
http://codepad.org/KuAExPhP

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

需要が無いのは分かってるんだけど、勉強の為に分岐予測も外せるようにしたソース置いておきます
新たに閃いたコードも入ってます
ttp://ideone.com/7wgVs

３項演算子遅すぎ

まあ需要はないな。
飽和演算程度でパフォーマンスのネックになるほど大量に捌かないと
いけないならSSE使えよって話になるし。

fastcall規約ならこれだけですむ
movd xmm0, ecx ;; a
movd xmm1, edx ;; b
psadw xmm0, xmm1
movd eax, xmm0
ret

movd xmm0, ecx ;; a
movd xmm1, edx ;; b
psadw xmm0, xmm1
movd eax, xmm0
and eax, FFFFh ;; ←上位ワードのゴミ掃除
ret

ゴミ掃除しとくか

これがいわゆる熱中症です

8bitや16bitの変数を使って、そのbit数よりも多く数える方法ありませんか？
符号化か何かで。
例えば8bitなら300まで可能、みたいな感じで。

有効桁数が少なくなっていいなら浮動小数点みたいに仮数部と指数部に分けてみたら

例えば8bitなら0-256まで数えたいときがあるんだよね。
そういうのでいいです。

何をいってるのか、わかってるのかね

二桁の数字で０から１００まで数えたいときがあるんだよね。
そういうのでいいです。

8bitの変数を2つ使えば簡単だと思うよ！

>>692
いくら符号化しても8ビットで表せるビットパターンが増えるわけではないので、そういうのは不可能だと思うよ。

「0」は0、「00」は100とする
あったまい〜

魔法使いでも探してるの？

例えばNULLと値の2状態を分けたい時ってありますよね。
その区別のために2バイトも使うなんて許せないです。

何をいってるんだい？

0.5bitを使うか

>701
けちって１ビットだけ使えばいいじゃん。
スペースをけちるとその分ほかにしわよせがいくけど。

PostgreSQLのNULLの処理はカラムの値とは別にカラムごとのNULLフラグを１ビットずつ持って処理しているよ。

コードのエリアで表す方法がある

if (他の変数) {
// 0-255のエリア
} else {
// 256-511のエリア
}
見ての通り「他の変数」が必要だが

グレイコード辺りで圧縮できませんかね。
よろしくおねがいしまう。

圧縮するほどの大きさがあるものなのかい？
パソコンのアプリなら富豪プログラム出来るだろうに

数え方を覚えておいて、
254→255と遷移したら255、
254以外→255と遷移したら256
とか。

0xaaや0x55みたいな特異な値で何かできないかな

難しいことやってる気になりたいのかね？
簡単に考えりゃいいのに、割りきって

どこに覚えておくんだ？

2進数に変換してそれをｎ進数とみなし、(n-1)の剰余を求めればいいと思うよ

天才あらわる！！！

昔読んだ本に8ビットで100万まで数えるトリックが載っていたなぁ
通信系情報理論本の序論だった。

うまく符号化すれば1ビットで100まで数えられませんかね

>>701
ポインタを使って、MSBが立っていたらNULLとするとか。

頭壊れるような話によく釣られるね

>>694
完璧な方法は絶対に存在しないけど、使える方法ならある。

例えば、0〜256の整数を識別したいけど、奇数は絶対に扱わない、というのであれば
2で割った値を格納しておいて、使うときに2を掛けるような処理を組めば良い。

結局のところ、8つのビットの組み合わせで表現できる、互いに識別可能な元は256個しかないから
8つのビットを使って257種類の状態を識別することは、鳩の巣原理を用いれば簡単に証明できるように、
理論的に不可能なんだよ。

どんなファイルでも必ず可逆圧縮できるようなアルゴリズムがこの世に存在できないのと理由は同じ。


それと一応>>701に突っ込むと、NULLは16bitだったり32bitだったり36bitだったり64bitだったりするけど
あなたがプログラミングで扱うような尋常なマシンだと通常8bitにはならないから
そんな心配はしなくて良い。

あと、よく知られたテクニックとしては、1byte型へのポインタでも無い限り
ポインタ変数が格納するアドレスのLSBのあたりに情報を乗せない方法があるから、
そこから情報を抜き取って、そこに代わりの情報を埋め込む、という方法がある。

もうひとつ突っ込む場所があったのを思い出した。

>>706
グレイコードは圧縮じゃないよ

>>692
　　　　　　　 ＿＿＿_
　 　 　 　 ／　　　　　＼
　　　　 ／　 　⌒　　⌒ ＼　
　　　／　 　 （●） 　（●） ＼
　 　 |　 　､"　ﾞ)（__人__）"　　）　　　 _＿＿＿＿＿＿＿＿＿_
　　　＼　 　 　 ｡｀ ⌒ﾟ:j´　,／　jﾞ~~| | |　　　　　　　　　　　　　|
＿＿／　　　　　　　　　　＼　 |_＿| | |　　　　　　　　　　　　　|
| |　/　　 ,　 　 　 　 　 　 　 ＼ｎ||　 | |　　　　　　　　　　　　　|
| | /　　 /　　　　　　　　　r.　 （ こ） | |　　　　　　　　　　　　　|
| | |　⌒ ーnｎｎ 　 　 　 　|＼ (⊆ｿ .|_|_＿＿＿＿_＿＿＿＿_|
￣ ＼＿_､("二）￣￣￣￣￣ｌ二二ｌ二二　 ＿|_|＿_|＿

まあそんなにちっさいもんさらに圧縮したいってことは
それが並列にいっぱいあるからだろうから
ランレングスとかで合宿すればよろし

>>720
なんでおでん喰ってんの？

アイスだろ季節柄

このスレまとめたみたいなライブラリって無いの？
C++でTMPと実行時、固定長と自由長のがあるといい

自由帳にでも書いてろカス

まず0ビットで1を数える方法を考えればいい
あとは1ビットで100だろうが、8ビットで100万だろうが任意の応用ができる

無限桁を1桁に圧縮した世代

色なんかだと人間の感覚に応じて端折ることできたりするけどねえ。

char increment(char prev){
float f = (float)((unsigned long int)prev<<48);
f = f + 1.0f;
return (char)((unsigned long int)f>>48);
}

半角英大文字をインクリメント・デクリメントしたいと思います
Zを超えたらAに、Aを超えたらZにしたい場合どうすれば効率よくできますか

そこはテーブルだろうやはり

答だけ聞けりゃいいと思ってると身につかんだろうな
ある意味、自分はバカですといってるようなもん

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

文字といっても文字コードは色々あるし
cmovとかインテルローカルな話はやめろよ

cmovはAMDの方が速いし
条件付き移動命令自体はx86に限った話でもないけど
例えばMIPSにもSPARCにもAlphaにもあるし、
ARMやPA-RISCやIA64なんかは移動だけでなくほとんどの命令を条件付き実行できる

>>734
そんな事を言い出したらキリがないぞ。言語すら指定されてないんだから。
それとも世界中の全言語全文字コード全CPU対応のソースでもあるの？はやく出してよ

>>732
質問者に難癖つけるだけよりは、第三者にも参考になることもありうるので
よほど有意義だと思うのですが？

>>733
ありがとうございます
3番目みたいなのは面白いですが、もし実装するなら2番目でしょうね

>>734
長い夏休みの暇つぶしに投稿しただけなので
環境はとくに指定しません

>>737
初心者じゃないなら、何やったかぐらい書いたら

>>737
> 質問者に難癖つけるだけよりは、第三者にも参考になることもありうるので
> よほど有意義だと思うのですが？

驚くべき思い上がりだな。

>>739
自分はおこぼれを頂戴してるだけであって物乞いなどしないとでも言いたいのかｗｗ

> 第三者にも参考になることもありうるので

夏厨への対処の仕方という意味で参考になる。

どんぐりがなんか言ってるぞ

おまいらせめてビット演算で会話しろよ

dase

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

より効率的な方法はありませんか。

uint32_t s = (x & 0x7f7f7f7f) + (y & 0x7f7f7f7f);
return ((x ^ y) & 0x80808080) ^ s;
ってのがハッカーのたのしみ2-17にあったよ

x+y からキャリーを引くのは特定条件で駄目だとわかったので、なんとなくその方法はあきらめてました。
ありがとうございました。

>>746
下位ビットは普通に加算しつつ
最上位ビットの加算のみxorに置き換える事で
繰り上がりを防いでいるわけか

>>745で飽和加算てできるんでしょうか？

できません

ありがとうございました

ハッカーのたのしみかったけど
積みそうな内容だった
イタリック体の数式はダメなんだって

アレは辞書代わりに使ってる

あれより濃い本が欲しい

数学的な方向ならコンクリート本かな？

あとHAKMEMを直接読むとかも面白いかも

コンクリート本って何？

http://www.amazon.co.jp/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025

thx

コンクリートジャングル
ってどういう意味？
そういえば

《(和)concrete＋jungle》ビルの林立する都会を、ジャングルに見立てた語。

ほう、
風流な・・・

　　　　　￣￣￣￣￣￣￣l/￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　　　 ∧＿∧
　　　　　　　　　( ´･ω･`) 　　 　∧＿∧
　　　　　　　　 ／ 　　　 ＼　 　（　　　　）何言ってんだこいつ　
　　　　　.＿＿|　|　　　 .|　|＿　/ 　　 　 ヽ
　　　　　||＼　￣￣￣￣　　 ／ .|　　　|　|
　　　　　||＼..∧＿∧　 　　(⌒＼|_＿./ ./
　　　　　||.　 （ 　　　）　　　　 ~＼___＿_ノ|　　 ∧＿∧
　　　　　　　/　　　ヽ　空気読めよ　　 ＼| 　 （　　　　）　
　　　　　　　|　　　　　ヽ　　　 　　　　　　　＼/ 　　　 ヽ. ｵﾏｴ馬鹿だろ
　　　　　　　|　　　　|ヽ、二⌒) 　　　　 　　／ .|　　　|　|
　　　　　　　.|　　　　ヽ　＼∧＿∧　　　 (⌒＼|_＿./　/

なんか話そうぜ
おれはこんなビット演算してすごい損害出したとか
マ板向きか

　　 ／￣￣＼
　／　　 _ノ　　＼
　|　　　 （ ●）（●）
.　|　　　　 （__人__）
　 |　　　　　｀ ⌒´ﾉ
.　 |　　　　　　 　 }　　ミ　　　　　　　　ﾋﾟｺｯ
.　 ヽ　　　　　 　 }　ミ　 ／＼　　,☆＿＿__
　　 ヽ　　　　　ノ　　　　＼　 ＼ ／　　 　　＼
　　　/　　　 く　　＼.　　／＼／　─　 　 ─　＼　←>>765
　　　|　　　　　`ー一⌒)　 ／ 　 （●） 　（●）　 ＼
　 　 |　　　　i´￣￣￣ ＼ |　 　 　 （__人__）　　 　 |
　　　　　　　　　　　　　　　＼＿　　 ｀ ⌒´

ビット演算を使ってカッコいい告白方法を考えてくれ

きみと0xA|0x5としたい

16進記法はカッコいいというよりいかがわしいな

Oxfordをまともに読むことさえできない私も
自分の心に素直にありたいんだ！

0x(f or d) だから、0x000f ですね

1100000010

まつがえた
1100000100

304h＝772d だけど、何の意味が？

1100000110

>>773 ＋２ だけど、これはただの通りすがりかな

＋２ だけど、その二進数で何やりたいの？ or 言いたいの？

1100001001

いいかげんにしろ池沼

1100001011

1100001100

おれ、この0が全部1で埋まったらハローワーク行くんだ

しかしながら埋まることはないと思います

まさにフラグなわけだな

1111111111

>>767
0xA0|0xFに見えた

0xAnull 0xFac ですね

you & I, 相性はAだって。

じゃあビット演算で哲学しようぜ
f(x)=1&x の逆関数を考えてみてくれ
実数から複素数に拡張するように
何かを拡張させてもいいので

偶数か奇数かってことだから、あまり面白くないのでは？

奇数ならFizz
偶数ならBuzz
それ以外ならFizzBuzzと表示させよ

いやあ、& や | が非可逆なのが不便に思えてさ。
undo できないよね。計算によって情報が減るというかさ。
計算しつつも元に戻れるような
情報量の減らない論理演算体系が作れないかなぁ
xor は自身が逆関数だからいいよね。（いいかは知らないけどw）

フレトキンゲートでぐぐれ

ググった。量子コンピュータの話なのね。
可逆計算理論を初めて知った。めっちゃ面白い。
ロムるわ。ありがとう。

>>792
こういう何もわかってなくて単語だけ知ってるゴミはどうすればいいんだろうな

>>793
煙に巻かれてるお前もゴミお前なんだけど



マジレスで教えておいてやるけど
量子コンピュータは、「完成しない」

技術的にではなくてね、。
それを作らずとも、人のやりたいことは達成出来るから

ようは速いコンピュータがほしいんだろ
俺はコンピュータの演算速度が-0秒になるところまではみている

ようは、人がそこの0秒演算のPCを手に入れちゃう位置にたどり着いても
まだ量子コンピュータは遠い

けど作れないことはない

でも、コストや費用的に、「もう作らなくていいんじゃね？ｗ」ってなる

量子コンピュータは世界と世界とを結ぶ原子核を再帰させて
並列処理ではなく再帰を並列にみせかける再帰並列処理をやろうとしてるから
それをやると、複数の世界の「世界」そのものの力を借りた演算速度になる

俺は0秒演算のPCまで出来たら満足だけど、
そこまでやろうとする奴いるかねぇ
数百万年とか、数億年とか、適当な未来予測は普段なら出来るんだけど
量子コンピュータの完成日については、まったく予想が不可能、


もしこれが完成するとしたら、現在いる俺よりもさらに上のスペックをもった奴が、地上に光臨しない限り　作られない
いわば突然変異みたいな感じ
人がアメーバみたいな生き物から、科学発展をさせたあの「奇跡」を、もう一度起こすぞｗ　くらいの確率でしか
量子コンピュータは完成されない　俺であったら2兆年くらいあれば作れるかもしれない

あー　ひとつ方法はあった
俺が結婚して、子供を作り
そいつに技術力のすべてを教え込む
それを何世代か繰り返せば、量子コンピュータの短期完成はありえるかもしれない

けど俺は基本的に結婚の予定はないんだけど

気持ち悪い

まずいよきみ

いろいろ調べてると量子コンピュータはあんまり関係なかったかも。
可逆計算理論の話ね。

久しぶりにキモいのを見た
キモッ

最近気付いたんだが
(x + y) / 2より(x + y) >> 1と書いてある方が何故か安心する

今どきどんなアホなコンパイラでも同じコード吐くだろ

俺作のアホコンパイラは同じコード吐かない
はい論破

いやそれ、自作のコンパイラがアホだと言ってるだけだから。

VCだと、対象がsignedの場合に除算とシフトで結果が変わるから、
除算だとその補正のためにcdqとsubが挿入されるね

(x + y) / 2u と書けばシフトと同じコードになる

一応念のため補足。除算とシフトで結果が異なるのは対象がsignedで負の奇数のとき
-1 / 2 == 0,　-1 >> 1 == 1
-3 / 2 == -1,　-3 >> 1 == -2

signedを(2^n)で割る演算は基本的に cdq -> sub -> sar になる
cdq, sub は負の場合に+1するため

二分探索のバグの話を聞いてからは
x / 2 + y / 2 と書きたくなる
加算でオーバーフローしないのか考えるのはめんどくさい

>>807
オーバーフローせずに平均値を求める： ((x^y)/2)+(x&y)
上でも出てる負数の問題を気にしないなら ((x^y)>>1)+(x&y)

ミスってた…まあ分かるだろうけど
(正)　-1 / 2 == 0,　-1 >> 1 == -1

それ以前に優先順位の違いで事故るから
x + y / 2 == x + (y / 2)
x + y >> 1 == (x + y) >> 1
基本的にやめとけ

>>733
int IncBit(int char_code) { retrun 'A' + ++char_code % 26; }
int DecBit(int char_code) { retrun 'A' + --char_code % 26; }
こんなんで十分じゃね。あとはコンパイラが上手いことやるだろ。

>>737
調子に乗るなボケ。

>>746
これ逆の減算をみたことないんだよな
考えてみれば、わりと簡単なのかもしれんけど

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;

こんなふうにバイトに値を変換しておくと早く軽くしょりできるのでしょうか？表記は間違ってないでしょうか？

Cの初心者スレに行け

多分それではより遅く動く。

ふつー、こうなるよね。
byte INPUT_NOT1=~(byte)1;

何がしたいのかわからん

エスパー検定です

８ビットのポートの入力（Ｌアクティブ）じゃないかと想像したが、
単なる通し番号でビット位置になってないし・・・

すごく恥ずかしくなってきました/////

何かが間違ってるのはわかってんだから今さら気にすんな
それよりどういう事だったのか説明しろ
気になるんだよ

実は格ゲーのコマンド入力に使うものだったのですが、初心者のクセに独自アレンジを繰り返してこんなことに・・・

今見ると俺にも謎ですね>>813

基本ができてないうちから技巧に手を出すなよ
まずは変数と定数の区別とか、型変換とくに汎整数拡張についてCの教科書で学んでくれ

up

down

←→

<<&&++--||>>//

A/Dを読んで（ダイヤルの左右回転度合い）、変化量を求めるのに、加重平均を
とるやり方を知らなかったので、「前の値との差の絶対値が７以上」 とかのアホな
判定してた。平均をとればLSB付近のばたつき成分が消えるんだよね。

直前までの平均と現在の値が与えられたときに、平均てどう更新したらいいと思う？
データの個数がやっぱ必要かな

>データの個数
データの中身（どう変化するのか）で考えたほうがいいんじゃね
変化量があまりないときは、単純計算できるような

ビット演算カンケーねー

フィードバック型とか
out=in*0.001+out*0.999;

もしくはダウンサンプルすればいい
if(count<10000){
tmp+=in;
count++;
}else{
out=tmp;
tmp=0;
count=0;
}

>ビット演算カンケーねー
めんごめんご
画像で、でかい範囲の平均化とか一つずれるたびに再計算するのも何だからと思って。

ああ、画像認識の境界判定とかかな。
きょうびググれば分かるんじゃね。

>>832 私がやったのは、out=out*C-out+in*(1/C); って方式でした。
Cは８か１６ぐらい。Cがどの位だとin のばたつきが均されて結果のつきが遅れないか
というあたりがよく解らないままやってたんですが、その辺、なんか助言ください。
>>832の前者と比べて、-outがあることで何が違うのかな？

データの傾向もみんで、当てずっぽうでやるのかい
非力なマシン使ってた頃ならありかもしれんけど

その方法に限るならその形は全部 IIR フィルタになるから
ノイズと信号の周波数特性を考えてじゃあどの係数の IIR フィルタを使おう、と決める

でも信号処理は無数にやり方あるし
やりたいことで全然作り方分かる
君の今の情報じゃデータの特性も要求も真っ暗で
全然基本の手法も絞れん
真っ暗闇で相談するより
ググって同じことやってる人見つけて
真似る方が早いよ

指示されて使ったときは、温度A/D12bitや、電波入力レベルA/D12bitでした。
出力パワーに反映、わりとゆっくり変化→ゆっくり反映　という感じでした。

使ってみたらよかったかな？と思ったのは、ダイヤル入力A/D10bit→受信周波数
微調整の箇所です。指で回す→周波数の追随が良い、だけどノイズは拾いたくない
ぐらいの条件ですね。作ったハード屋さんはこの入力をこの出力に反映してねしか
言わないんです。

計算式教えてもらったら、動くとか思ってるのかよ

まあここでできるのはいろいろ体験談をサジェストするくらいだろうね
どれが最適かまではデータみないと絶対わからないし
特定の２手法のどちらが適しているかすらも言えることはない

ところでこのスレのタイトルを見てくれ、こいつをどう思う？

ビット演算に掛け算は入りますか？

二乗とか平方根とかのこと？

ビット演算ていうと、AND, OR, XOR, NOT, シフトだけじゃないかと思う君。

rotate

じゃあせっかくだから平均化に特化した平均化手bit演算を語ろうか

if(a>b)swap(a,b); はどうにかできない？

p.s.
このへんにためてけばよくね？
https://gist.github.com/gists/search?q=bit-manipulation

t=(a^b)&(0-(a>b));
a^=t;
b^=t;
これでいけるかな？

いいんじゃないかな

ただこれが例えばソートの中とかで使われるなら
比較結果は偏るので予測が効いて単純な分岐の方が速くなる可能性が高い
さらにaとbがメモリにあったりすると分岐を排除したら常にストアが発生して具合が悪かったりする

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 専ブラ用

bit = 0x49; // 0b01001001;
for ( ; ; ) {
if (bit & 1) {
// 1の処理
bit |= 1 << 13;
} else {
// 0の処理
}
bit >>= 1;
}
とかどう

ROT13の話かと思ったら全然違った牛乳

>>851
おおおおお！かなりよさそうです。
ありがとうございました！

アセンブラだと右シフト後のキャリーをMSBへ移動するってことか

for(;;){
//0の処理
//0の処理
//0の処理
//0の処理
//0の処理
//0の処理
//1の処理
//0の処理
//0の処理
//1の処理
//0の処理
//0の処理
//1の処理
}

マジックナンバー埋め込んだらアカンよ

？
>>850も>>851も埋め込んでると思うが

なんなら>>855のアセンブラを生成してからそこにジャンプするようにすれば良くね？

即値はバグの温床になるから気を付けろという意味

そんな唐突に bit 演算スレに向いてない説教されても。
別スレ行って説教した方がいいんじゃないの？

そんなカッカするなよw

>>851
uint8_tは8bitだから
bit |= 1 << 13;
はダメですぞ

じゃあ
<bit |= 1 << 13;
>bit = 0x49;
で

え；

>>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の時の処理
}
}

>>864
> 13個のビット列を★周期的に繰り返して★得たい

そんなのビット列の初期化以外を好きなようにforで囲めばいいじゃないか

>>866
＞★下よりコストの少ない方法★ がありましたら教えてください。

全体をforで囲むのは>>850と本質的に同じ
uint8うんぬん以外は>>851でいいと思うんだけどねえ

結局>850よりいい答えがないw

>>850です。
>>851氏の方法で解決しましたが、bitのuint8_tは、
たまたま00001001001が8bitの範囲に収まる値だったからで、
状況によっては10101010101だったり、ビット列が増えたりなんてことも
ありえましたので、あまり気にしないでください。

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

>>853でとっくに解決したって言ってるのになんで蒸し返すの(´･ω･`)

>>870
if の中身が簡単じゃないとそもそもボトルネックにならんだろうよ

>>871
蒸し返すっていうかポツポツ話が続いていたので便乗してみただけ。ただしコストを下げるって事に
過敏に反応してしまったのは悪かったけど。
>>872
「ifの中身が簡単すぎるとボトルネックにならない」って意味でいいんですよね？
それはその通りでgccでは差が出すぎてしまったので、その結果は採用せずに851氏(今まで氏を付け
てなかったスミマセン)のコードでという結論になりました。

以下駄文というかスレチですので無視して結構です>>>
何故864を書いたのかというと851氏のはビットが 1 の場合演算が1回増える&依存関係があるので
コンパイラの最適化（アンロール）に支障が出てしまうと思ったからです。アンロールできれば
実行コストが下がり有利になる(最後のシフト命令が省略できる等)はずでしたが、結果が余りにも
極端すぎたのとifの中身の処理が大量にあった場合アンロールされなくなり、逆に不利になる場合も
あるので通常は851氏の考え方でいいんじゃないかという気がします。
汎用性が無いとダメとの事なので意味無かったんですが、依存関係を無くすとか、左右反転してみる
とかの工夫は実行コストを下げるという意味において大事だと思ってます。考え方古いかな。

『ビットがxの時の処理』
っていうのが重杉て、書いている部分の最適化なんて誤作同然になると思うけどね。

そのとおり。
そして当該処理が簡単な時は実行時に>>855を動的生成するようなコードを書いてそれに jmp すればよろし

forでループ組むよりノベタんで書いたほうがよくね？

即値はバグの温床（笑）

はああああああああああああああああああああああああ

>>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のほうが多いはずだし。

さすがだんごさん
スレの空気が引き締まったな

この流れなら貼れる
ttp://ocw.ouj.ac.jp/tv/1542109/08.html

このスレにそんな基礎中の基礎の話を今更必要としてる人はいねーよ。
岡部先生もおまえみたいな見境のない信者にはうんざりだろう。
いいかげんにしとけ。

岡部洋一があほだってことが良くわかる映像だった

群馬大学乙w

幕張！幕張！

andとorを
xorだけですませる為の分かりやすいサンプルください

ではまず屏風から虎を誘き出してください

最初にぱんつを脱ぎます

脱いだぱんつを履きます

これを高速で繰り返します

バターが出来上がります

はーしね

そんな基礎から判らないなら電子回路の本でも借りて読んだ方が早い

やっぱ2chのスレってこの程度だよね

さっさと死んでおけよゴミ共

ではお得意のルビーでお手本をお願いします

andとorでxorじゃねえの？

最近みんなWin8が糞すぎてピリピリしてんだよね
あまり怒らせない方がいい

andやorをxorから合成するのは端的に言って無理だよ。
(a+b-(a^b))>>1
とかやっていいなら話は別だけど。

真理値表も読めない馬鹿が混じっているのか。

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)
じゃだめなんですか？

勿論、だめじゃありません。

まあその状況でxor使う必要もないけどな
結局
A&B | (A|B)&C
を
A&B | (A^B)&C
にしてるだけだから、何の利点もない
オペランドが片方だけ真になるときはxorはorの代用として使える、というだけの自明な話

教科書の Manchester Carry Chain のところで出てきた式なのですが
どうしてわざわざ無駄なことをしているのでしょう？

つ ttp://en.wikipedia.org/wiki/Carry-lookahead_adder

>>898
無理じゃないよ
実際に最近俺がそういうコードを書いてしまったが
読み解くのが面倒だったから聞いただけ
むしろ逆に
or and でかける範囲のアルゴリズムのいくつかをxorで置き換えられるってだけな気がするけど

ベン図見ながら考えた。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)　　これで合ってる？

>>906
間違ってる

四通りしかないんだから自分で確かめてみたらいいよ。
まずは A=0, B=0 ね。

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

xorとnotだけじゃandにはならんだろ
逆はできるけど

>>910
どうやって証明できます？

xorとnotではand/or/nand/norなどが書けないことを帰納法で示す

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が生成できない。

アプローチはあってるけど証明にはなってない

試しに説明を試みたが、証明するところまでは考えなかった。
つーか、私にゃ無理w

xor と not があれば
A xor B
not (A xor B)
以外に
not A
not B
が作れるだろ
だから何でも作れるのが正解

え？

最後の一行以外は、誰でも知ってるが
何故「だから何でも作れる」なのか

じゃあand作ってみなよ

彼は「ひとつ、ふたつ、たくさん」の国から来たんだよ
温かく迎えてやれ

1変数ブール関数の国から来たんだな

グループA（xor/not）からは、グループB（and/or/nand/nor）を、グループBのどれか一つが無ければ作れない。

なんだか階層構造があるみたいだな。数学で既に誰か考察してそうだが。

xorは桁上がりしない足し算？

yes

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なら作れるけど）。

今ざっと考えてみたところそんな感じだと思う。

とりあえずサラっと書いてみた。
http://www1.axfc.net/uploader/Sc/so/360310.pdf

あ、ごめん。
表にちょっと誤りがあるわ←おっちょこちょい

http://www1.axfc.net/uploader/Sc/so/360312.pdf
修正入れた。

>>928
乙。

簡易っていうか、これで十分厳密な証明じゃないの？

>>905がどんな面して出てくるか

簡易だよ。証明のための表をいきなり与えてるし。
本当なら一々式変形やって、「ほら、(not (A xor B)) xor A = not Bはいつも正しいでしょ？」とかって片っ端から言う所。

いまどきはCoqで。

そういえば、3not 問題って、俺まだよくわかんないんだった。

アホしかいないのな
^ と ! から
完璧な ｜ と完璧な ＆　作れとか言ってねーからさ
どこで何を勘違いしたんだ、
特定ケースのみでいいから正しく動作するサンプルをね、所望していたわけだけど
もう自分のソース解析して大体理解したからもういいよこの雑魚スレ
&と|を^で置き換えるショートコーディングの技術解説してるのをどっかで見たんだけどな
そのころはまだ自分が絶対記憶能力を持つ前だから忘れてるわ

> andとorを
> xorだけですませる為の分かりやすいサンプルください

これを

> ^ と ! から特定ケースのみでいいから正しく動作するサンプルを所望

と読める人はいないよ

つーかスレ内検索しただけでわかるけど、こいつ完全な統失電波さんだな
触らない方がよかった…

まだNGしてなかったのかよ

見えないけど（見えないから？）、何について話しているかわかった

ツンデレんがわゆ

>>935



えっ？

>>935
にほんごは　ただしく　せいかくに　かつ　じゅうぶん　ぐたいてきな　かたちで　つかいましょう。

日本語に限った話じゃないし、プログラマならなおさらそうするべきなんだがな。

「わかりました。大丈夫です。まかせてください」

つって、勘違いしたままいらねーもん開発してる典型じゃん
この流れ

謝れ

おいおい、上流工程さんよ
わざわざ要求を不正確に伝えてきたのはそっちじゃんよ。
俺は目の前にある仕様を正しく表現した。俺の仕事は全うし、責任は果たされた。

謝れ

and でも or でもないのを、 and とか or とか言ってたわけだね。
わけだね。

うん。

NANDかNORのどちらかならまだしもXORで全ての論理ゲート表現するってのは新しいなｗｗｗ

人は数字に弱い
人は再帰にはもっと弱い
人は二進数にも弱い

uyは頭が弱い

ゴミか

うん
uyはゴミ

nandも書いたら可哀想だよ。

っと。

norだけはガチ

誰うま