- 1 名前：デフォルトの名無しさん [2006/09/16(土) 09:46:26 ]
- 前スレ
ビット演算
pc8.2ch.net/test/read.cgi/tech/1123918075/
関連スレ
アセンブラ… (゜□゜) ↑アッー！↓
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
- 560 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 07:26:50 ]
- >>558 さすがに64bit掛算はまだ普及してないだろ
- 561 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 07:28:20 ]
- >>559 SHが特殊で固定シフト命令が1,2,4,8みたいな飛び飛びのシフトしか１命令で出来なかったりするからじゃないの？
- 562 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 12:16:14 ]
- でも、仕事で使用するとしたら、普通に割り算したほうがソースとして見やすいよね。
2で割るのを1ビットシフトするぐらいはいいけど、あえて複雑な演算にするほど処理能力を求められないでしょ？普通の開発は。
でも、このような議論って技術者としては面白いし、ある意味大切だよね。
- 563 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 12:40:03 ]
- >>560
アルゴリズム上の話で、実際に64bit乗算をするわけではないと思う。
元ネタはこれじゃね？
ttp://www.emit.jp/prog/prog_div.html
- 564 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 13:51:33 ]
- >>560
コンパイラがやってくれることもしばしば。
まぁ尤も、コンパイラのアセンブリ出力を見たときに「割り算がない」って悩まないためにも
知識はあったほうがいいのだけれどね。
- 565 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 13:57:31 ]
- Y = (R * X ) >> 64 って事は 、R = 2^64 / D って事だろ？
Dが16bitの範囲なら Rは 48bitって事になるぞ。 64bitモードに以降しないと効率悪いぞ
- 566 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 14:00:28 ]
- もともと
D=100の場合
1 : ( x * 4294967200 + 65536) >> 32
2 : ( x * 4294967200 + 4294967199 >> 32
のどっちが 大きな x までまともに計算出来るかって問題でしょ？
- 567 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 14:01:49 ]
- 違うか
1 : ( x * 42949672 + 65536 ) >> 32
2 : ( x * 42949672 + 42949671 ) >> 32
- 568 名前：デフォルトの名無しさん [2007/11/17(土) 15:24:56 ]
- BCCで出来ないんだけど・・・CPUのせいかもしれない
内部で32+24ビット程度しか保持していない気がする
- 569 名前：デフォルトの名無しさん [2007/11/17(土) 15:33:51 ]
- >>518がちゃんとうごくぱそこんってあるの?
テストプログラム作ったけど上位1ビットの値は壊れているようだ
#include <iostream>
using namespace std;
main(){
int n;
for(n=50;n<=64;n++)
cout<<n<<" "<<(unsigned int)((1<<n)>>(n-1))<<endl;
}
- 570 名前：デフォルトの名無しさん [2007/11/17(土) 15:43:45 ]
- これっていくつになりますか?
1になるはずですよね?
cout << (unsigned int) ( ((1<<64)-2) >> 63 );
- 571 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 17:43:47 ]
- >>570
-1を unsigned にキャストしてるんだからUINT_MAXになると思う。
- 572 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 18:06:10 ]
- 符号付整数の右シフトが論理シフトになるか算術シフトになるかは処理系定義
- 573 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/11/17(土) 19:18:14 ]
- >>569
unsigned __int64かunsigned long longでおｋ
- 574 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/11/17(土) 19:20:40 ]
- >>570
なんで普通のコンピュータで使えるビット数越えたシフト使うんだ。
1 << 64なんてオーバーフローで0になること確定じゃないか。
- 575 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 20:42:48 ]
- ~0ULLでおｋ
- 576 名前：デフォルトの名無しさん mailto:sage [2007/11/17(土) 23:58:43 ]
- >>569
>>563のコードと同じだからそっちでやってみればいいんじゃないか。
- 577 名前：デフォルトの名無しさん [2007/11/18(日) 07:54:51 ]
- #include <iostream>
using namespace std;
main(){
unsigned int n;
for(n=60;n<64;n++)
cout<<n<<" "<<(unsigned int)(((1<<n)-2)>>(n-1))<<endl;
cout<<63<<" "<<(unsigned int) ( ((1<<63)-2) >> 62 );
}
63の値が変わるのはなぜ?
- 578 名前：デフォルトの名無しさん mailto:sage [2007/11/18(日) 08:34:36 ]
- >>577
サイズを超えるシフトは未定義。
- 579 名前：デフォルトの名無しさん mailto:sage [2007/11/18(日) 22:48:23 ]
- ARMは割り算使うと糞遅いから困るな。
- 580 名前：デフォルトの名無しさん [2007/12/03(月) 22:55:09 ]
- age
- 581 名前：デフォルトの名無しさん [2007/12/03(月) 23:13:14 ]
- 32bitパソコンだと、16*16しか値は保証されないよね
a + b * 65536 などと表示して、32bit以上を表現したら
ハードウェア搭載の除算よりビット演算のほうが速い?
除算が現れたらintを16bit数に変換して計算する
- 582 名前：デフォルトの名無しさん [2007/12/04(火) 05:02:29 ]
- X = 65536 、R = 1/Xとすると
(a+bX) / (c+dX) = (b+aR) / (d+cR)であり、
1/(1+R) のテイラー展開は、 1 - R + R^2 - ・・・+(-R)^n+ ・・・
Rの巾は非常に小さいため2乗までを採用すると、
(a+bX) / (c+dX) = ( (b+aR)/d ) * 1/(1 + cR/d)
=( (b+aR)/d ) * (1 - cR/d + (cR/d)^2 )
=1/(X^3 * d^3) * (a + bX ) * (c^2 -cdX + d^2X^2 ) となる
これで32bit除法を高速化出来るか?
- 583 名前：582 [2007/12/04(火) 05:12:33 ]
- 32bit内で処理しようとすると大変だ 普通にCPUに任せた方が楽そう
- 584 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 20:25:38 ]
- BOOL bResultの値が 0 か -1
if (bResult == 0 || bResult == -1)
じゃなくて、一発で調べる方法はないですか？
- 585 名前：デフォルトの名無しさん [2007/12/16(日) 20:42:35 ]
- BOOLなのに何故数値と比較してるんだ？
- 586 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 21:10:40 ]
- GetMessageじゃね？
- 587 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 21:30:22 ]
- BOOLは偽==0、真==0以外じゃなかったか？
定義を調べた方が良さそう。
- 588 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:05:41 ]
- 世の中には変な使い方する椰子がいるのよ。MSとかw
ttp://msdn.microsoft.com/library/ja/default.asp?url=/library/ja/jpwinui/html/_win32_getmessage.asp
- 589 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:08:46 ]
- if(bResult^0==-1)
- 590 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:37:38 ]
- x^0=x
- 591 名前：デフォルトの名無しさん mailto:sage [2007/12/16(日) 22:42:19 ]
- if (((((uint32_t)bResult) + 1) >> 1) == 0)
同じ3演算だけど-1をロードしないだけ早いかも？
uint32_tがいいかどうかはよくわからない。
- 592 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:16:01 ]
- -1か0、限定なんだからそのまま書いたほうが分かりやすいような。
- 593 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:26:58 ]
- >>588
( ･д⊂ヽ゛
- 594 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:29:32 ]
- >>588
>警告 GetMessage 関数は、0 以外の値、0、-1 のいずれかを返します。したがって、次のようなコードは避けてください。
そもそも…
- 595 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:30:54 ]
- まー継ぎ接ぎだからな
- 596 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:39:34 ]
- >>591
右シフト・条件分岐より、比較・条件分岐の方が速くない？
if (((uint32_t)bResult + 1) <= 1)
- 597 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 00:50:04 ]
- >>596
マシン語レベルでは結局0比較に変換されるから同じ程度じゃないかな。
でもCレベルではそっちの方が短くていいと思う。
- 598 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 01:17:11 ]
- >>597
ちょっと前まで主流だった某CPUではシフトは加減算の
8倍遅かったし、それ以外のCPUでも演算器の関係で
シフトの方が並列化されにくいかも、とかそういう話。
- 599 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 01:19:21 ]
- で、何億回呼ぶのよ
- 600 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 02:05:25 ]
- シフトのほうが速いと思ってたのに・・・
- 601 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 03:12:30 ]
- >>599
そんなこと言うならこのスレの意義って一体なんなのさ。
確かにWindows APIをそんなアホみたいに呼ぶ事はないだろうが、
こんな風に一般化してみれば、それなりに使い道はあるだろ。
_Bool bounds_check(int n, int lower, int upper)
{
return (unsigned)(n - lower) < (unsigned)(upper - lower);
}
>>600
加減算よりシフトの方が速いCPUなんてあるのかな？
演算の頻度からいっても普通は加減算を最速に設計すると思うけど。
x86系を数種類しか触った事ないから、他にはあるのかも知れないが。
- 602 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 04:47:19 ]
- ハードウェアの構造上加減算よりシフトの方が圧倒的に単純なんだよ
小さい加算器を作ったことがあればわかるはず
クロック数が一緒ってことはあるかもしれんが、
シフトの方が遅いってことはまずないだろう
- 603 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/17(月) 05:39:05 ]
- ARMだと全命令にプレディケーション使えるからCレベルの単純な分岐は直列化できるよ
分岐は極端に遅いなんていうのはCellプログラマだけにしてください。
- 604 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 07:41:05 ]
- >>602
このケースは1bitだからその通りだけど
x86の8086-286までは、2bit以上のシフトは遅かったんだよ。
最初は直接bit数指定のインストラクションすらなかったし。
- 605 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 13:11:19 ]
- ttp://answers.google.com/answers/threadview?id=388350
- 606 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 13:13:10 ]
- >>603
単純な分岐なら、if文使ってコンパイラに任せた方が速いね。
絶対値求める時とか、NULLならreturnするとか、分岐コストかからなくていい。
- 607 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 14:37:02 ]
- むしろif文にbool型しかとらないJava/C#が異端なんじゃねーの？
俺もbool型オンリーの方が好きだが、スクリプト言語してるとそうじゃない方が多い気がする。
- 608 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 18:27:51 ]
- ifの選択肢にTrueとFalse以外なんてあり得るの？
- 609 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 18:33:36 ]
- if(666){//実行されます。}
- 610 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 19:02:56 ]
- コメントに括弧閉じ書いて意味あんの
- 611 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 21:34:17 ]
- if (GetMessage(...) <= 0)
で充分でね?
- 612 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 21:49:47 ]
- >>602
シフタってのはデータセレクタの塊だから多ビットのシフトは
シリコンの面積を喰うのよ
- 613 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 23:54:21 ]
- >>611
-1以外の負の値が未定義
- 614 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 23:54:34 ]
- シフタのないプロセッサには出会ったことが無いけどね。
- 615 名前：デフォルトの名無しさん mailto:sage [2007/12/17(月) 23:58:16 ]
- if (bResult == 0 || bResult == -1)
は
if (((uint32_t)bResult + 1) <= 1)
と同じコードになったぞ。
gcc賢いな。
ちなにみRISCでどうなるか見たかったので団子の嫌いなCELLのgccでコンパイルしたw
ちなみにCELL(SPE)もヒントブランチあるから。
むしろARMのプリディケーションいまいちだと思うけど。
- 616 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/18(火) 00:11:17 ]
- 知ってるが
Cellのスカラ性能が
気に食わない
- 617 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/18(火) 00:45:11 ]
- 分岐ヒントもBranchの15クロックくらい前くらいに入れないと駄目じゃなかったっけ
しかも二重に使うとハングする致命的なバグ持ちだから始末に困る
- 618 名前：デフォルトの名無しさん [2007/12/18(火) 00:47:47 ]
- if (bResult == 0 || bResult == -1) こんなん対して食わないだろ゜
- 619 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/12/18(火) 00:52:15 ]
- SSE4.1のXMMに対する比較命令が加わったから4条件同時判定とかも便利そうだね
- 620 名前：デフォルトの名無しさん mailto:sage [2007/12/18(火) 08:10:08 ]
- ダンゴさんが連投するとスレが引き締まるな
- 621 名前：デフォルトの名無しさん [2007/12/18(火) 11:30:40 ]
- ダンゴage
- 622 名前：デフォルトの名無しさん mailto:sage [2007/12/18(火) 20:46:31 ]
- test
- 623 名前：デフォルトの名無しさん [2007/12/21(金) 07:08:36 ]
- test
- 624 名前：デフォルトの名無しさん [2007/12/21(金) 07:18:07 ]
- www.nicovideo.jp/watch/sm1779811
- 625 名前：デフォルトの名無しさん [2007/12/30(日) 10:37:00 ]
- 年末あげ
- 626 名前：デフォルトの名無しさん mailto:sage [2008/01/03(木) 18:36:52 ]
- ttp://itl.jisakuita.net/core2_mossari/1162381694.html
ダンゴさんすげえな
- 627 名前：デフォルトの名無しさん [2008/01/09(水) 19:20:08 ]
- sge
- 628 名前：デフォルトの名無しさん [2008/01/14(月) 22:47:23 ]
- V(･∀･)V
- 629 名前：デフォルトの名無しさん [2008/01/21(月) 23:54:19 ]
- あげ
- 630 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 00:09:06 ]
- 以下の2つの値があったとします。
x1 = 0xFF842144
x2 = 0x5400FF33
ユーザからの入力u1、u2が入力された場合
考えられるケースは以下の4つになると思います。
・u1=x1、u2=x2一致
・u1=x1一致
・u2=x2一致
・どちらとも一致しない
最低3回比較しないとどのケースか判断できないって
思い込んでるのですが
何かいいアイディアくれる人いませんか？
- 631 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 00:46:32 ]
- 愚問だと思いますが。。
しかし、そんあ80年代前半のBASICの論理式みたいなアナクロな発想をするって
今日日奇特な人だね。
- 632 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 00:50:58 ]
- u1がx1と一致するケースに
・u1=x1一致、u2=x2一致
・u1=x1一致、u2=x2不一致
がある
u1がx1と一致しないケースに
・u1=x1不一致、u2=x2一致
・u1=x1不一致、u2=x2不一致
がある
つまり４通り
比較は最大２回
- 633 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 01:21:29 ]
- その比較を10^12回通りくらい計算するつもりなら最適化もあり
- 634 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 01:30:35 ]
- あらかじめ
p = x1 XOR x2
の値を取得しておく
q1 = p XOR u1
q2 = p XOR u2
を得る
- 635 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/01/22(火) 01:30:56 ]
- SSE4のptest使えば一回で済む
- 636 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 01:54:14 ]
- >>634
得た後はどうすればいいのw？
q1とq2をどうやって使うの？
- 637 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 02:56:20 ]
- >>632
＞・u1=x1一致、u2=x2一致
あんた馬鹿?
- 638 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 11:10:15 ]
- >>635
無理だろ，あれは and と andnot だから．pcmpeqd の方が良さげ
- 639 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 11:49:49 ]
- 632ってこういうことだろ？
if( u1 == x1 ) {
if( u2 == x2 ) {
//ryouhou
} else {
//u1 nomi
}
} else {// not
if( u2 == x2 ) {
//u2 nomi
} else {
//ryouhou itti sinai
}
}
どこも間違ってるように思えないんだが。
- 640 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 12:34:57 ]
- しかし、BY（文脈読めない）な奴が多いな。
ここがどういうスレかを考えれば、>>630が何を聞きたいか
多少説明不足でもだいたい分かるだろ普通w
- 641 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 13:13:10 ]
- ほうほう。それでそれで?
- 642 名前：デフォルトの名無しさん mailto:sage [2008/01/22(火) 18:32:50 ]
- int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
b1 = (u1 == x1)
b2 = (u2 == x2)
return a[(b1 << 1) | b2];
- 643 名前：642 mailto:sage [2008/01/22(火) 18:33:45 ]
- × int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
○ int a[] = {一致しない, 片方一致, 片方一致, 両方一致};
- 644 名前：デフォルトの名無しさん mailto:sage [2008/01/23(水) 10:32:39 ]
- ゼロフラグでレジスタに0,1をセットする命令があるならソレが効率的だね。
それがないと、減算して、さらに１引いてキャリーを出してローテートしなくちゃいけない
アキュムレータが2個しかないCPUなら
AccA := u1-x1-1;
RotWithC(AccB);
AccA := AccA+x1+1-x2-1;
RotWithC(AccB);
AccB := AccB and 3;
結局、そのあたり何が効率的かはアセンブラで見ないといけないけど
アセンブラで出来る高速化は、リニアにしか効かないから、そんなに意味ないんだよね
- 645 名前：デフォルトの名無しさん mailto:sage [2008/01/23(水) 20:55:34 ]
- 全面的に同意．ただ２倍位速くなることもあるから最後の手としては有効．まぁ今は可能 intrinsic 使うけど．
- 646 名前：デフォルトの名無しさん [2008/01/23(水) 21:06:35 ]
- 割り算を掛け算とビットシフトに置き換える計算式求めるプログラムできた
#include <iostream>
using namespace std;
main(){
unsigned int N,n,k;
for(N=2; N<65000 ; N++){
for(n=0; (1<<n)<N ; n++); n+=15;
double X=(pow(2,n)/N);
unsigned int Y=(unsigned int)X;
unsigned int d=0;
if(X-Y<=Y+1-X)d=(unsigned int)(pow(2,n)- (N-1)*Y)-1; else Y++;
printf("x /%5d = ( x * %5d + %5d ) >> %2d",N,Y,d,n);
for(k=1; k<(1<<16) ; k++) if(k/N != ((k*Y+d)>>n))break;
if(k==(1<<16))printf(" OK\n"); else printf(" ERR\n");
}}
- 647 名前：646 [2008/01/24(木) 15:42:18 ]
- 64bit機か、内部で64bitまで計算結果を保持しているなら
32bitの割り算も出来るけど646は16bit同士です
- 648 名前：デフォルトの名無しさん mailto:sage [2008/01/24(木) 15:52:26 ]
- GCC の中見りゃあるんじゃね？
- 649 名前：デフォルトの名無しさん mailto:sage [2008/01/24(木) 17:46:02 ]
- >>648
gcc のカオス・スパゲッティ状態を知らぬようだな。
勧めるならせめて Small-C くらいにしとけ。
このルーチンなら 工学社から出ていた
Small-C ハンドブックにもちゃんと説明されていたんだし。
- 650 名前：デフォルトの名無しさん mailto:sage [2008/02/04(月) 20:42:37 ]
- ハッカーの楽しみ買ってきました〜
これから読みますﾉｼ
- 651 名前：デフォルトの名無しさん mailto:sage [2008/02/05(火) 23:53:51 ]
- Hacker's Delight やっと届いた
- 652 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/02/06(水) 01:12:31 ]
- 俺もアレ訳本出る前ネットショップで買ったわ
- 653 名前：デフォルトの名無しさん [2008/02/22(金) 06:50:56 ]
- a
- 654 名前：デフォルトの名無しさん [2008/02/28(木) 07:49:51 ]
- a
- 655 名前：デフォルトの名無しさん mailto:sage [2008/03/01(土) 13:50:55 ]
- a << 1
- 656 名前：デフォルトの名無しさん [2008/03/05(水) 07:05:43 ]
- a
- 657 名前：デフォルトの名無しさん [2008/03/11(火) 07:43:25 ]
- あげ
- 658 名前：デフォルトの名無しさん [2008/03/24(月) 22:44:22 ]
- あげ
- 659 名前：デフォルトの名無しさん [2008/03/30(日) 21:00:53 ]
- あげ
- 660 名前：デフォルトの名無しさん mailto:sage [2008/03/30(日) 21:42:47 ]
- なにこのスレきもい。
でも懐かしい。
|
 |
