- 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
- 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 ]
- なにこのスレきもい。
でも懐かしい。
- 661 名前：デフォルトの名無しさん [2008/04/06(日) 18:17:38 ]
- |
|
／￣￣￣￣￣￣
＜⌒／ヽ-、_＿_
／＜_/＿＿＿＿／
- 662 名前：デフォルトの名無しさん mailto:sage [2008/04/06(日) 18:41:01 ]
- ダンゴさんを称えるスレというわけではありませんが、まあ、KY。
- 663 名前：デフォルトの名無しさん mailto:sage [2008/04/06(日) 19:46:30 ]
- GCAの作者のページにビット演算が載ってたけど今いちわからん
- 664 名前：デフォルトの名無しさん mailto:sage [2008/04/07(月) 17:04:46 ]
- ViViの作者のページにもビット演算が載ってたけどだいたい理解した
vivi.dyndns.org/W/254
- 665 名前：デフォルトの名無しさん mailto:sage [2008/04/07(月) 19:44:18 ]
- >配列による状態表現よりも処理が高速になる場合が多い
この表現は凶悪だな。何故なら、高速にならなかった場合にはかなり遅くなる可能性があるからだ。
- 666 名前：デフォルトの名無しさん [2008/04/17(木) 06:42:52 ]
- age
- 667 名前：デフォルトの名無しさん [2008/05/01(木) 06:01:45 ]
- age
- 668 名前：デフォルトの名無しさん mailto:sage [2008/05/01(木) 08:02:29 ]
- 燃料がないな
- 669 名前：デフォルトの名無しさん mailto:sage [2008/05/01(木) 08:50:52 ]
- 16bitカラーで 5：5：5 とか 5：6：5 とか の時代なら色々やったけどな
- 670 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/01(木) 18:55:25 ]
- AltiVecにも16bitカラー用の演算があったな
- 671 名前：デフォルトの名無しさん mailto:sage [2008/05/09(金) 19:08:22 ]
- こちらのスレから誘導されて参りました。よろしくお願いします。
スレ立てるまでもない質問はここで 第91刷
pc11.2ch.net/test/read.cgi/tech/1209716212/171
以下の条件で、32bit値のハミングウェイトが素数か否かを判定する
出来るだけ高速な方法を探しています
・入力はランダム
・（最悪ではなく）平均速度が速いことが望ましい
・0、1は素数ではない（偽になって欲しい）
・ハミングウェイトそのものの値は必要ない
・64bit拡張などは必要ない。32bit決め打ちで良い
・外部メモリはあまり使いたくない
皆様のお知恵を貸していただけませんでしょうか
- 672 名前：デフォルトの名無しさん mailto:sage [2008/05/09(金) 19:25:44 ]
- 一応、今はこんな感じです
ベタな実装で恥ずかしいですが…
int hw_is_prime(unsigned long x)
{
x = ( (x & 0xAAAAAAAA) >> 1 ) + (x & 0x55555555) ;
x = ( (x & 0xCCCCCCCC) >> 2 ) + (x & 0x33333333) ;
x = ( (x & 0xF0F0F0F0) >> 4 ) + (x & 0x0F0F0F0F) ;
x = ( (x & 0xFF00FF00) >> 8 ) + (x & 0x00FF00FF) ;
x = ( (x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF) ;
return (1 << x) & 0xA08A28AC;
}
- 673 名前：デフォルトの名無しさん mailto:sage [2008/05/09(金) 21:56:14 ]
- 1 << 32 の結果って決まってたっけ
- 674 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 10:32:41 ]
- 処理系定義かな。0ビットシフトになる場合と32ビットシフトになる場合が一般的だと思う。
- 675 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 18:51:02 ]
- まぁ 8bit, 16bit, 32bit が int の場合と、
64bit が int の場合では結果は明らかに異なるよな
- 676 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 20:19:59 ]
- 8bitがintになることってありえるっけ
- 677 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 20:51:31 ]
- 規格は一応-32767〜32767だからないんじゃね？
- 678 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/12(月) 21:34:45 ]
- 1ビットマシンとか4ビットマシンとかってCでプログラミング可能なの？
- 679 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 21:44:21 ]
- CHAR_BIT >= 8 だけど、
別に変数１つをレジスタ１つで扱えないといけないわけじゃないし
問題ないんじゃね？
- 680 名前：デフォルトの名無しさん mailto:sage [2008/05/12(月) 21:47:55 ]
- ダンゴさんのカキコでスレが加熱したな
- 681 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/12(月) 21:59:19 ]
- レス番飛んでるな
- 682 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 11:50:54 ]
- ダとかンとかゴとか入ると飛ぶんだよな。
- 683 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 11:56:23 ]
- 実は見えてる
- 684 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 12:39:16 ]
- ダンゴって名前を嫌がるのは、
体型が肉団子だからだよな。
- 685 名前：ヽ・´∀｀・,,）っ-○◎● mailto:sage [2008/05/13(火) 12:47:46 ]
- だんごはこれだろ
━━━━━━┓がどうみたらだんごに見えるねん
あたまわるいんとちゃうか
- 686 名前：ヽ・´∀｀・,,）っ鹵〜＜巛巛巛 mailto:sage [2008/05/13(火) 12:50:40 ]
- 虫除けのようなものだよ
- 687 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 14:33:31 ]
- ダンゴさんってどんな仕事してるの?
- 688 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 16:51:03 ]
- 名無しさんの書き込みでスレがヒートアップしたな。
- 689 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 18:15:31 ]
- 他愛もない雑談だけどな。
と、だけ書くのもなんだから、ちょこっとマジレス。
ANSI C での int の定義は処理系依存で、CPUのレジスタ幅によるらしい。
なので、Z80 なら 8bit の筈だけど、
大体のZ80 C処理系では char=8bit, int=16bit と扱う。
なんで int は 16bit より大きいという誤解があるんだろうなぁ。
その昔は char=7bit なんで処理系もあったというので、
油断は出来ないように思うんだよ。
- 690 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 18:38:03 ]
- INT_MINは-32767以下、INT_MAXは+32767以上じゃないといけないと決まってる
昔の話は知らん
- 691 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2008/05/13(火) 19:01:17 ]
- 1ビットCPUは実際にあった
www.d1.dion.ne.jp/~ytera/1bitcpu.htm
- 692 名前：デフォルトの名無しさん mailto:sage [2008/05/13(火) 21:12:11 ]
- 昔はやりたい放題だったかも知れないが、
今は規格に準拠した処理系であれば int >= 16 bits なのは真理。
あと、int のサイズの定義は CPU のレジスタ幅にして欲しそうな定義ではあるけど、
そう断言している訳じゃない。
実際最近でも 64-bit マシンで int = 32-bit のことがある。
- 693 名前： ◆0uxK91AxII mailto:sage [2008/05/14(水) 01:14:15 ]
- >>689
＞その昔は char=7bit なんで処理系もあったというので、
無い。
- 694 名前： ◆0uxK91AxII mailto:sage [2008/05/14(水) 01:21:20 ]
- ごめん、間違い。
- 695 名前：デフォルトの名無しさん mailto:sage [2008/05/14(水) 03:04:09 ]
- uartと間違えたんだな
- 696 名前：デフォルトの名無しさん mailto:sage [2008/05/14(水) 23:42:41 ]
- ハネウェルの昔のマシンとかは 6bit 単位のマシンとかがあったから、
それとの勘違いだろ。(7bit があったかどうかは知らん。)
まあ単位が 6bit なのは uart と同じ理由だが。
- 697 名前：デフォルトの名無しさん mailto:sage [2008/05/15(木) 02:07:52 ]
- >>691
それはCPUと言うよりリレーの置き換えみたいなもの
Connection Machineのはまともな1bit CPUだけどbit sliceだから何bitにでも
化ける
- 698 名前：デフォルトの名無しさん [2008/05/28(水) 00:29:01 ]
- あげ
- 699 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:17:23 ]
- 11100111
こんなビットがあったとき、0が4と5ビット目に
存在するってどうやって調べるのが効率いいのかな？
個数はわかるけど位置はどうすりゃいいんだろう
- 700 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 00:34:24 ]
- Hacker's Delight 嫁
- 701 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 02:40:11 ]
- >>699
11100111 and 00011000
- 702 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 02:41:22 ]
- 8bitなら256個のﾃｰﾌﾞﾙ持てば最速じゃね？ 16bit以上なら、シフトして端のbitの0/1と
シフト回数で判別。
- 703 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 02:50:48 ]
- >>699
ループ
- 704 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 09:37:40 ]
- >>703
>>701
aビット目とbビット目が動的に変わるなら、マスク作ってandとった方が良いかもしれない。
- 705 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 09:47:01 ]
- >>699
問題文は正確に
- 706 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 11:48:47 ]
- >>699
４、５ビット目というのは変わりうるのよね？
あと個数が２個というのも変わりうるのよね？
- 707 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 11:51:01 ]
- >>699
ああ、あと、いつもがそんな風に左右対称とは限らないのよね？
- 708 名前：デフォルトの名無しさん mailto:sage [2008/05/30(金) 12:36:25 ]
-
一番下の0のビットだけを１にするのなら
y := ( not x ) and ( x +1)
で出来るから、ビットが1の個数が判る命令BitCount があるんなら
BitCount( y-1 ) で求まるよ
で x:= x or y; として一番下の0だったビットを1にしてから $FF になるまで繰り返せばいい
- 709 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:25:23 ]
- >>708
それって並列にできないですかね
無理ですよね.....
- 710 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:30:28 ]
- bit演算で128、64、32bitを扱う場合
みんなどんなふうに宣言しますか？
C/C++でのバターな方法が解りません
- 711 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:34:46 ]
- まずトラを数匹用意します。
- 712 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:41:57 ]
- あるプログラムで実際にあったコード。
普通ループではカウンタを＋＋していくと思うけど、
（iを1,2,3・・・と加算）
一回処理するごとに左に1ビットシフトしていた。
（iを1,2,4,8・・・とシフト）
普通こういうコード書きます？仕事で。
- 713 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 00:49:43 ]
- >>712
1989年ぐらいに見た記憶があるｗ
- 714 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:15:51 ]
- グレイコードを扱うような貧弱なCPUに対するコードなら在り得る。
- 715 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:26:18 ]
- １ビットずつスキャンしていく場合には使う。
- 716 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:27:14 ]
- >>712
普通にあるし、速度面だけでなく、その方が可読性があるものもある。
- 717 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 01:28:54 ]
- 終了条件でいつも悩むんだけどね。
- 718 名前：デフォルトの名無しさん mailto:sage [2008/06/11(水) 07:07:30 ]
- for( bit=1 ; bit ; bit<<=1 ) cnt += ( ( data & bit) >0 );
こういうの？
- 719 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 22:51:52 ]
- アセンブラで１〜８回のループをシフト+キャリーでやることはあったな。
- 720 名前：デフォルトの名無しさん mailto:sage [2008/06/12(木) 23:56:44 ]
- もしかしたらループ回数が３２かいを超えたら・・・
どうするの？
|
 |
