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

1 ：08/11/08 〜 最終レス ：11/12/18

前スレ
【高速化】ビット演算　0x02
http://pc11.2ch.net/test/read.cgi/tech/1158367586/
過去スレ
0x01. http://pc8.2ch.net/test/read.cgi/tech/1123918075/
関連スレ
アセンブラ…　(゜□゜) ↑アッー！↓
http://pc8.2ch.net/test/read.cgi/tech/1148402614/
関連情報
Hacker's Delight
ttp://www.hackersdelight.org/
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
ttp://www.amazon.co.jp/exec/obidos/ASIN/4434046683
ビットを数える・探すアルゴリズム
ttp://www.nminoru.jp/~nminoru/programming/bitcount.html
Bitboard
ttp://en.wikipedia.org/wiki/Bitboard

2 ：

Intel系を前提として、
bitの逆転ってどんなコード組んだら一番速い？
int rev(int n){n=(n<<16)|(n>>16);
n=((n&0x00ff00ff)<<8)|((n&0xff00ff00)>>8);
n=((n&0x0f0f0f0f)<<4)|((n&0xf0f0f0f0)>>4);
n=((n&0x33333333)<<2)|((n&0xcccccccc)>>2);
return((n&0x55555555)<<1)|((n&0xaaaaaaaa)>>1);}
より速いのがありそうな気がしてならない

3 ：

Intelはともかく、テーブル作ればいいんじゃない？
8ビット分のテーブルがあるとして
return
　table[ n & 0xff ] << 24
| table [ (n >> 8) & 0xff ] << 16
| table [ (n >> 16) & 0xff ] << 8
| table [ (n >> 24) & 0xff ] ;

4 ：

>>2
とりあえず命令の並列度を高めてみた。
unsigned rev(unsigned n){
    n = (n<<24) |(n<<8&0x00FF0000) | (n>>8&0x0000FF00) |(n >> 24);
    n = (n<<6&0xC0C0C0C0) | (n<<2&0x30303030) | (n>>2&0x0C0C0C0C) | (n>>6&0x03030303);
    n = (n<<1&0xAAAAAAAA) | (n>>1&0x55555555);
    return n;
}

5 ：

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

6 ：

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

7 ：

ああ、あれね。

8 ：

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

9 ：

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

10 ：

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

11 ：

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

12 ：

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

13 ：

if((hr == DIERR_INPUTLOST) || (hr == DIERR_NOTACQUIRED))
この文はもっと縮まないですか？

14 ：

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

15 ：

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

16 ：

更に6バイト縮んだぜ
if(hr==DIERR_INPUTLOST||hr==DIERR_NOTACQUIRED)

17 ：

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

18 ：

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

19 ：

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

20 ：

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

21 ：

いっそマクロでもインライン関数でも作れよ
#define EQUAL_OR2(X, N1, N2) (((X) == (N1)) || ((X) == (N2)))

22 ：

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

23 ：

保守あげ

24 ：

template <typename charT>
static inline charT xorcmp(const charT *s, charT d0, charT d1) {
　return (s[0]^d0) | (s[1]^d1);
}
template <typename charT>
static inline charT xorcmp(const charT *s, charT d0, charT d1, charT d2) {
　return (s[0]^d0) | (s[1]^d1) | (s[2]^d2);
}
template <typename charT>
static inline charT xorcmp(const charT *s, charT d0, charT d1, charT d2, charT d3) {
　return (s[0]^d0) | (s[1]^d1) | (s[2]^d2) | (s[3]^d3);
}
template <typename charT>
static inline charT xorcmp2(const charT *s, const charT *d) {
　return xorcmp(s, d[0], d[1]);
}
template <typename charT>
static inline charT xorcmp3(const charT *s, const charT *d) {
　return xorcmp(s, d[0], d[1], d[2]);
}
template <typename charT>
static inline charT xorcmp4(const charT *s, const charT *d) {
　return xorcmp(s, d[0], d[1], d[2], d[3]);
}

25 ：

template <typename intT>
struct Flags {
　intT value;
　intT get(intT mask) const { return value & mask; }
　void set(intT mask) { value |= mask; }
　void reset(intT mask) { value &= ~mask; }
　void assign(intT mask, intT/*bool*/ cond) {
　　cond = -(cond != 0);
　　value = (value | (mask & cond)) & (~mask | cond);
　}
};

26 ：

以下のような16進文字を値に変換する処理を書いているのですが、
もっと短くする方法がありましたら教えてください。
(引数のhには16進文字しか入ってきません)
unsigned char ascii2hex(unsigned char h) {
if (h <= '9') {
h -= '0';
} else {
if (h > 'F') {
h -= 0x20;
}
h -= 'A' - 10;
}
return h;
}

27 ：

短くと言うのは、ソースの行数なのか実行文のサイズなのか？
ソースなら
unsigned char ascii2hex(unsigned char h) {
　return h - (h <= '9' ? '0' : (h <= 'F' ? 'A' - 10 : 'a' - 10));
}
実行文なら
unsigned char ascii2hex(unsigned char h) {
　static const unsigned char *const t = {
　　0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
　　0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
　　0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
　　0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,
　　0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
　　0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
　　0,10,11,12,13,14,15
　};
return t[h];
}

28 ：

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

29 ：

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

30 ：

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

31 ：

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

32 ：

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

33 ：

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

34 ：

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

35 ：

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

36 ：

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

37 ：

gccだよ>AVR

38 ：

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

39 ：

16進文字以外が無くてASCII限定ならこんなもんじゃねーの。
static unsigned char table[] = {0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,10,11,12,13,14,15,};
return table[(h & ~0x20) - '0'];
速度無視すりゃこっちの方がコードサイズ短くなるかもな。
static char a[2];
a[0] = h;
return strtol(a, NULL, 16);

40 ：

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

41 ：

適当に命令セットを見ながら速そうに書いてみた。
とはいえAVRは使ったこと無いからどうすれば速いかよく分からんけど。
unsigned char d;
h &= 0x1F;
d = (h>>4|h<<4);//swap 命令使ってほしいなっと
d = d-1 & 9;
h = h+d & 0xF;
return h;

42 ：

除算が素直に可能ならこれでいいんだがな・・・。
return (h & ~48) % 55;

43 ：

あー事前にマスクしなければ1命令減らせた。
unsigned char d = (h >> 4 | h << 4);
d = (d&1)-1 & 9;
h = h+d & 0xF;
>>42
除算がサポートされてても速度が微妙じゃね？
でも格好良いなそれ。

44 ：

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

45 ：

みなさんありがとうございました。
AVRには乗除算命令は一部のモデルにしかなく、
ない場合はコンパイラが適当に変換するようになっています。
>>40は>>28と全く同じコードサイズでした。
>>43が1ワード減って、最も小さくなりました。
>>39は上記に比べて50バイト程増えました。
strtol等ライブラリ関数は一応用意されてますが、
リンクするとサイズがとんでもないことになるので使えません。
>>42の割り算は、内部ルーチンが大きいため
テーブルを使うのとと同程度でした。

46 ：

>>28の出力コード
8a 33 cpi r24, 0x3A ; 58
28 f0 brcs .+10
87 34 cpi r24, 0x47 ; 71
08 f0 brcs .+2
80 52 subi r24, 0x20 ; 32
87 53 subi r24, 0x37 ; 55
08 95 ret
80 53 subi r24, 0x30 ; 48
08 95 ret
>>40の出力コード
8f 7d andi r24, 0xDF ; 223
8a 33 cpi r24, 0x3A ; 58
10 f4 brcc .+4
90 e0 ldi r25, 0x00 ; 0
01 c0 rjmp .+2
97 e0 ldi r25, 0x07 ; 7
80 53 subi r24, 0x30 ; 48
89 1b sub r24, r25
08 95 ret
>>43の出力コ−ド
98 2f mov r25, r24
82 95 swap r24
81 70 andi r24, 0x01 ; 1
81 50 subi r24, 0x01 ; 1
89 70 andi r24, 0x09 ; 9
89 0f add r24, r25
8f 70 andi r24, 0x0F ; 15
08 95 ret
きちんとスワップされました

47 ：

unsigned char d = h + 0xC0;
unsigned char e = (d << 4 | d >> 4);
return (9 & ~e) + (h & 15);
これでどうだ？

48 ：

>>47
13ワードになってしましました。
28 2f mov r18, r24
20 54 subi r18, 0x40 ; 64
92 2f mov r25, r18
92 95 swap r25
9f 70 andi r25, 0x0F ; 15
22 95 swap r18
20 7f andi r18, 0xF0 ; 240
92 2b or r25, r18
90 95 com r25
99 70 andi r25, 0x09 ; 9
8f 70 andi r24, 0x0F ; 15
89 0f add r24, r25
08 95 ret

49 ：

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

50 ：

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

51 ：

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

52 ：

ていうか、この方が短くなるんじゃないか？
if (h > '9') h -= 7;
　return h & 0xF;
これを分岐無しにするともっと長くなりそうだが。
int n = (h > '9');
h += n;
n <<= 3;
h -= n;
return h & 0xF;

53 ：

分岐は気になるけど確かに減るね・・・。
cpi, brvs, subi, andi, ret
の５命令でいけそうだ。
分岐なしの方は 1 ビットシフトしかないのでかなり長くなるはず。

54 ：

お世話になっております。
>>52
unsigned char ascii2hex(unsigned char h) {
h &= ~0x20;
if (h > '9') h -= 7;
return h & 0xF;
}
として、6ワードになりました。
8f 7d andi r24, 0xDF ; 223
8a 33 cpi r24, 0x3A ; 58
08 f0 brcs .+2
87 50 subi r24, 0x07 ; 7
8f 70 andi r24, 0x0F ; 15
08 95 ret
すばらしいです。

55 ：

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

56 ：

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

57 ：

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

58 ：

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

59 ：

h &= ~0x20はいらないですね。
5ワードの間違いでした。
>>56
試しに再帰で作ってみました。
unsigned char htoi(unsigned char h, unsigned char l);
2桁の16進文字を値にする関数をこのように宣言すると、
AVRの場合h はr24、 l はr22に入り、戻り値はr24になります。
Cから呼ばれる関数はr0,r18〜r27,r30,r31が破壊を気にせず使えます。
htoi: // 半再帰を使ってみる→ 11ワード
mov r23, r24 // tmp <= h
ldi r24, 0 // 戻り値を0へ初期化
rcall half // 相対コール(tmpの処理)
swap r24 // ニブルを交換
mov r23, r22 // tmp <= l
half: cpi r23, 0x3A ; 58
brcs .+2
subi r23, 0x07 ; 7
andi r23, 0x0F ; 15
or r24, r23 // 結果をr24へor
ret

60 ：

htoi: // 普通にhlを処理した場合→11ワード
cpi r24, 0x3A ; 58
brcs .+2
subi r24, 0x07 ; 7
cpi r22, 0x3A ; 58
brcs .+2
subi r22, 0x07 ; 7
andi r22, 0x0F ; 15
swap r24
andi r24, 0xF0 ; 240
or r24, r22
ret
ワード数的には変わりませんでした。
movとかldiが無駄のような、必要なような。

61 ：

分岐無しのほうを頭捻って1命令 短くしたつもり
しかし分岐使うほうにまだ1命令負けてるのがなぁ
unsigned char d;
h = h + 0x41 & 0x9F;
d = (h >> 4) | (h << 4);
h = h - d & 0xF;
return h;

62 ：

あげ

63 ：

あげ

64 ：

符号なし整数値について、1となっている
ビットのうちで、最下位のビット番号を
求める方法はありますか？
0x00000010 → 1
0x00100000 → 5
みたいな。
1のビット数は任意がいいですけど、
高速なら1ビット限定でもかまいません。

65 ：

シフトしながらカウントか、テーブル参照かな。
x に入ってるとすると、x ^ (x - 1) とか x & (x ^ (x - 1)) とか、
最下位の立ってるビット関係の値を取り出せる演算はあるけど、
ビット位置がうまく出てくる方法はないんじゃないかな。

66 ：

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

67 ：

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

68 ：

ハッカーのたのしみp90

69 ：

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

70 ：

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

71 ：

>>70
まぁx&-xで最下位ビット抽出してからやればなんとかなるかも
int f(unsigned x){
    x = x & -x;
    //x = (x * 0x0722BED3) >> 27; // 64ビット乗算がないならこっち
    x = (x * (0x0722BED3ULL<<5)) >> 32 & 31;
    return "\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"[x];
}

72 ：

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

73 ：

＞＞71
なんでそんなのがわかるの？
天才ですか？
俺にはさっぱり・・・
returnで返しているのも何をしているのかわからん・・・
何かお勧めの本はありますか？
体育大学卒で組込みやってるあんぽんたんですが、
本を読む努力はします。

74 ：

return "\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"[x];
こう書くから判りにくいんだよ。
こう書き直したらどうだ?w
return x["\0\1\13\2\10\14\34\3\11\32\15\17\35\27\4\21\37\12\7\33\31\16\26\20\36\6\30\25\5\24\23\22"];
ギャグはさておき。
static const char table[] = {
0, 1, 11, 2, 8, 12, 28, 3,
9, 26, 13, 15, 29, 23, 4, 17,
31, 10, 7, 27, 25, 14, 22, 16,
30, 6, 24, 21, 5, 20, 19, 18
};
return table[x];
と同じだよ。

75 ：

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

76 ：

(i%10)["0123456789"]

77 ：

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

78 ：

同じだよ。

79 ：

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

80 ：

>>73
文法周りはみんなが言ってくれたから計算回りだけ。
とりあえず前スレに分かりやすく書いてた人が居たから引用
前スレとの違いはp=5になった事ぐらい
ここから引用
周期2^p-1ビットの列があって、そこからpビットを切り出すと、オール0以外の全てのパターンが現れる
p=3の場合のM系列は例えばこう。
0011101
↓ (周期2^3-1=7で同じパターンの繰り返し)
001110100111010011101...
上の桁から3ビットを切り出すと、
001 (1)
_011 (3)
__111 (7)
___110 (6)
____101 (5)
_____010 (2)
______100 (4)
1〜7まで全部出るだろ。これに000だけ追加すればおｋ。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
↓この文字列リテラルの部分な。
"xxxxxxx"[(ハッシュ計算式)]
すると、>>762-763になりますよ、と。ビット溢れによるマスクなども組み合わせているが。

81 ：

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

82 ：

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

83 ：

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

84 ：

同じだよ。

85 ：

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

86 ：

NLZって？

87 ：

ニュージーランド

88 ：

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

89 ：

ないからわざわざそういう命令があったりするんだろうね。POWERとかだっけ？
DSPとかだとビット並びを反転させる命令があるから、それと組み合わせるか。

90 ：

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

91 ：

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

92 ：

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

93 ：

あげ

94 ：

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

95 ：

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

96 ：

2進数や16進数の為の代数学とか無いのかな？
例えば32bit符号付き整数の絶対値を求める式を、定理を使って単純に変形するだけで、
andとかshiftとかmulみたいな単純な操作のみで構成された式に変形できる公理系とかそういうの
x < 0 ? -x : x
={なんか、分岐の融合法則とかそういうの}
(n ^ (n >> 31)) - (n >> 31)
こういう等式変換の形でアルゴリズムを計算でできれば、
勘だけではできないときに色々と役立つんじゃないかなーと思うだけど
つーか絶対ある筈なんだけど、俺はそういう噂すら知らないんで

97 ：

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

98 ：

n < 0 ? -n : n
={ 2の補数 : -n = ~n + 1 }
n < 0 ? ~n+1 : n
={ n+0 = n }
n < 0 ? ~n+1 : n+0
={ --x = x, - 0 = 0 }
n < 0 ? ~n-(-1) : n - 0
={ n < 0 ? -1 : 0 <=> (n>>31) …(*}
(n < 0 ? ~n : n) - (n >>31)
={ ~n = n^(-1), n^0 = n}
(n < 0 ? n^(-1) : n^0) - (n >>31)
={ (*) }
(n^(n>>31)) - (n>>31)
? : 演算子の単調性とか一部証明無しで決め打ちしてますができました
4番目の変形以降は知ってないとできませんね、恐らく常識なんでしょうけど
>>96はその常識をまとめてあったり、こういう演算の性質について
群とかそういった代数学の概念での議論とかが載ってる文献などありませんかという意味でした

99 ：

右シフトが論理シフトだったら
(n^-(n>>31))+(n>>31)
かな？
nが1の補数だったらどうなるんだろう

100read 1read

1read 100read

TOP カテ一覧 スレ一覧 削除依頼 ▲
・　次のスレ
monazilla Part 6
ソースのコメントを英語で書くスレ
真木クラウド
[新作] 日本語プログラミング言語「やまと」 1行目