【高速化】ビット演算　0x02

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 331 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 01:06:15 ] ごめん、sage 忘れた。 332 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 14:45:44 ] ごめん、ぬるぽ忘れた。 333 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 15:11:37 ] ぬるぽの話題は参照の話題について直接的ないし間接的に関係のあるスレッドでしか出す事は許さん。 334 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 15:23:11 ] >>329 それを言うなら「低俗化」では? 335 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 17:57:17 ] 風俗化 336 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 18:11:47 ] Jデッ化 337 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 18:35:50 ] つーかおまいらこんなことしてていいの化 338 名前：デフォルトの名無しさん mailto:sage [2007/06/01(金) 23:16:16 ] ばか 339 名前：デフォルトの名無しさん mailto:sage [2007/06/02(土) 12:18:51 ] 珍しく最近妙にスレが伸びてると思ったら、こう言う内容だったの化 340 名前：デフォルトの名無しさん mailto:sage [2007/06/03(日) 02:25:37 ] なんじゃゴラァ、おまいらバカ化 341 名前：デフォルトの名無しさん [2007/06/03(日) 04:24:42 ] あ？ 342 名前：デフォルトの名無しさん [2007/06/19(火) 21:59:45 ] 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 ってどんな意味のあるビット列ですか？ 教えてください。 343 名前：デフォルトの名無しさん mailto:sage [2007/06/19(火) 22:04:20 ] パイオニアだかボイジャーだかのレコード盤に記録されてる奴？ 344 名前：デフォルトの名無しさん mailto:sage [2007/06/19(火) 22:17:46 ] Gray Codeだな 345 名前：デフォルトの名無しさん mailto:sage [2007/06/19(火) 23:13:20 ] entity GRAY_CODE_COUNTER is generic( N : integer := 4 ); port( CK, RESET : in std_logic; Y : out std_logic_vector(N-1 downto 0)); end GRAY_CODE_COUNTER; architecture BEHAVIOR of GRAY_CODE_COUNTER is signal GRAY, COUNT : std_logic_vector(N-1 downto 0); begin process ( RESET, CK ) begin if ( RESET = '1' ) then COUNT <= (others => '0'); elsif ( CK'event and CK = '1' ) then COUNT <= GRAY; end if; end process; process (COUNT) variable BIN : std_logic_vector(N-1 downto 0); begin BIN(N-1) := COUNT(N-1); for I in N-2 downto 0 loop BIN(I) := BIN(I+1) xor COUNT(I); end loop; BIN := BIN + 1; GRAY(N-1) <= BIN(N-1); for I in N-2 downto 0 loop GRAY(I) <= BIN(I+1) xor BIN(I); end loop; end process; Y <= COUNT; end BEHAVIOR; 346 名前：デフォルトの名無しさん mailto:sage [2007/06/19(火) 23:15:55 ] ううまま　うままう　うまう　うままう 347 名前：デフォルトの名無しさん mailto:sage [2007/06/20(水) 12:26:09 ] >>342 たとえば、機械類なんかの位置あわせの目的で　センサーを配置する時に ４入力あれば１６箇所の位置を特定できるわけだけど 同時に２つのセンサーが変化するようになってると巧くゆかない。 そこで移動につれて、一つしかセンサーが変化しないような配置方法を考えたのがそのコード。 348 名前：デフォルトの名無しさん mailto:sage [2007/06/20(水) 14:21:11 ] 要するに>>342は 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 って意味 349 名前：デフォルトの名無しさん mailto:sage [2007/06/20(水) 18:58:03 ] >>347-348が理解できない 350 名前：デフォルトの名無しさん mailto:sage [2007/06/20(水) 19:07:00 ] ばっかー 351 名前：デフォルトの名無しさん mailto:sage [2007/06/20(水) 19:09:51 ] 2ビットのグレイコードは、2相エンコーダと呼ばれてる。　機械式のマウスなんかで使われている。 　00 01 11 10　この順番で動けば 順方向　逆方向なら　00 10 11 01 と動くので区別出来る 2進数 00 01 10 11 でいいじゃないと思うだろうけど　これだと一度に2ビット変化する箇所が2度出来る センサーの取りつけに物凄い精度が要求される事になり安価なマウスに採用出来ない 352 名前：デフォルトの名無しさん mailto:sage [2007/06/21(木) 00:53:52 ] ハミング距離でぐぐるといいよ 353 名前：デフォルトの名無しさん mailto:sage [2007/06/21(木) 01:35:52 ] 上位ビットから順に加算して途中でやめても、下位ビットの影響がそれより上に及ばない、っていう利点もある。 354 名前：デフォルトの名無しさん mailto:sage [2007/06/21(木) 01:46:36 ] >>353 それ、具体的に教えて。 355 名前：デフォルトの名無しさん mailto:sage [2007/06/21(木) 23:48:28 ] 56の余りを求めるビットマスクはどのように書けばいいのでしょうか？ 356 名前：デフォルトの名無しさん mailto:sage [2007/06/21(木) 23:55:04 ] 商か剰余を求めるビット演算を生成する CGI か何かを昔見かけたような気が・・・。 どこだっけかな・・・。 357 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 01:08:45 ] 56の余りってなにさ? 358 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 01:17:06 ] x % 56でも計算したいんじゃね？ 359 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 07:26:57 ] x % 56だと　２のベキ乗じゃないからビット演算1発では出来ないな ttp://www.tensyo.com/urame/date/dayTips.shm ここの後ろの方にビットマスクと繰り返し演算で剰余を求める方法がある 360 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 07:35:52 ] 定数での除算って、こんなに繰り返し必要だったっけ？ ３、４回の演算で書けたような気が・・・って、俺の記憶違いか？ 361 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 07:37:37 ] それ、もしかしたら、２のべき乗での除算？ 362 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 07:40:38 ] いや、それなら１回でいけるし。 あれ？ 乗算だっけ？ 363 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 07:42:31 ] ああ、何か乗算だった気もしてきた。スマン。 364 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 07:50:41 ] 2^N>=b となるNを求める(2^N == 1<<N) ・・・・・　N=6　2^N=64 B=2^N-b ・・・・・・ 64 -56　= 8 C=2^N-1 ・・・・・・ 64 - 1 = 63 while(a>=2*b){ B *(a>>N) + a&C }; while(a >=56*2 ){ 8 *(a>>6) + a&63 }; while(a >=56*2 ){ ( (a>>6) <<3 ) + a&63 }; 1ループで3ビット改善するから 32bitなら　最大10回ちょっとのループか 365 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 08:00:17 ] 56*73 =4088 で 2^12-8 だから a = ( (a>>12)<<3 ) + a & 4095; を　前段でやれば改善するんじゃないかな　 366 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 09:49:41 ] 最近のコンパイラは定数の割り算は掛け算に置き換えるね。 56で割るロジックをコンパイルしたら、-1840700269を掛けた後に ビットシフトと足し算をしていた。それ以上追っかけるのはパス。 367 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 09:51:15 ] インテルのコンパイラで a=a%56 の出力はこんな感じ(aはunsigned int)。 LARGE_INTEGER li; li.QuadPart = UInt32x32To64(a>>3,0x24924925); int d = li.HighPart; a -= ((d<<3)-d)<<3; aがsigned intの場合は、もう少し複雑。 368 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:11:46 ] なるほど、>366の数値が0x92492493だからシフト量が違う同じビットパターンなのか。 369 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:17:29 ] でもまあPCのCPUみたいに掛算が高速だったらって前提だな。 1チップとかだと　掛算はビットサイズに応じたサイクル数かかるし 掛け算持ってないＣＰＵもあるし 370 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:21:39 ] 大丈夫、そういうCPUは割り算も遅い。 371 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:26:29 ] a = ( (a>>18)<<3 ) + a & ((1<<18)-1); a = ( (a>>12)<<3 ) + a & 4095; a = ( (a>>9)<<3 ) + a & 511 a = ( (a>>6) <<3 ) + a & 63; a = ( (a>>6) <<3 ) + a & 63; while(a>=56) a-=56; これならどうだろ？ 372 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:34:31 ] 演算子の数が20を超えてるな。 素直にdiv使った方が速いかもしれない。 373 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 10:45:50 ] もうちょっとバランスをうまく取れば、1行減らせるかもな 374 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:08:06 ] 結局　3bit　単位だからなあ 最初は a = ( (a>>15)&(-7) ) + a & ((1<<18)-1); か a = ( (a>>12)&(-7)) + a & ((1<<15)-1); のどっちかで、どっちも32->18.4bit 次は a = ( (a>>6)&(-7) ) + a & 511 　でも12.5bit a = ( (a>>9)&(-7) ) + a & 4095; でも12.5bit あとは3ビットづつしか落とせない。　無理 375 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:17:53 ] あ、 a = ( (a>>18)<<3 ) + a & ((1<<18)-1); a = ( (a>>12)<<3 ) + a & 4095; a = ( (a>>6) <<3 ) + a & 63; a = ( (a>>6) <<3 ) + a & 63; while(a>=56) a-=56; とやれば、最後の　while はせいぜい3回のループでいいか 376 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:26:49 ] >>372 div 命令は、持っていてもbit数のサイクルかかるのが殆どだよ。　だから >>366-367 のような最適化がされるんだし 377 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:33:21 ] ただ PC の場合はレイテンシがかかるだけだから、divを使った方が速いかもしれないな。 378 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:37:09 ] >>367 ここまでしても idiv より速いのか・・・。 379 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:48:18 ] Pentium II およびPentium III プロセッサの実行ユニット 整数乗算は　レイテンシ4、スループット1/ サイクル 除算は浮動小数点ユニットで行われ FDIV 命令　レイテンシ: 単精度17 サイクル、倍精度36 サイクル、拡張精度56 サイクル だから、桁違いにレイテンシが大きい。 380 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:50:39 ] 浮動小数点ユニットで行われるのか？！ 381 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 11:58:11 ] だって　整数乗算ユニットってのはブロック図にあるが、　整数除算ユニットってのはどこにも無いだろ？ 除算ってのはコストのわりに利用頻度が少ないから、どうせ浮動小数点ユニットもってるからそっちで計算させてるのさ 仮に、整数演算ユニットで除算をしたとしても、結局32サイクルはかかるし、その間加減算比較ユニットの一つが潰れてしまうからな 382 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 12:14:11 ] そうだったのか・・・。 そら遅いわな。 383 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 12:27:02 ] >>381 これ以上はスレ違いになるがつっこませてくれ。 浮動小数点ユニットがIEEE754（だったっけ）で処理する場合、単精度で23ビット、倍精度で52ビットの精度だろ。 被序数が32ビット整数ならともかく、64ビット整数の除算は精度の問題上アウトだぞ。 384 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 12:34:23 ] >>383 Intel 系の浮動小数点ユニットは 拡張倍精度（80ビット/仮数部64ビット）で行われてるから大丈夫。 385 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 12:44:20 ] >>384 まじか！と思って何年も開いていない重たいバインダーを紐解いてみたら、たしかにそう書かれているな。 しかも本当は63ビット精度なのに、ケチりビットをケチらない荒技で対処してるし・・・。 そのうえx87コプロに限ればつねに拡張倍精度で計算されることになってたりして、もうね、馬(ry。 386 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 13:02:46 ] 56 = 7*2^3 だから x % 56 = (x % 7)<<3 + (x & 7) x/7 を round(2^32/7 )>>32 で近似したのが >>367 387 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 13:07:24 ] しかし、1/7って面白いなぁ。10進だけでなく16進でも綺麗な循環小数になるんだな。 388 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 13:08:10 ] もしかして >>375 のような事しても idiv 使うより速いって事はありえるのか？ 389 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 16:51:54 ] >>388 実際に速度を比較してみれば？ Cの場合、&より+の方が優先順位が高いので、 >>375の&演算には括弧が必要だね。 390 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 17:06:59 ] そうだね。 391 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:03:24 ] やってみた。 function getRDTSC: int64; asm　　　DW　　$310F //RDTSC end; var ww:Integer; procedure TForm1.Button1Click(Sender: TObject); const CNT=100000; var t1,t2,t3:int64; i,a:Integer; begin t1:=getRDTSC; 　for i := 1 to CNT do　begin 　　a := i; 　　a := ((a shr 15) and 7) + (a and ((1 shl 18) - 1)); 　　a := ((a shr 9) and 7) + (a and 4095); 　　a := ((a shr 3) and 7) + (a and 63); 　　a := ((a shr 3) and 7) + (a and 63); 　　while a >= 56 do a := a - 56; 　　ww:=a; {mod と同じになるように} 　end; t2:=getRDTSC; 　for i := 1 to CNT do　ww:=i mod 56;{ローカル変数に代入すると最適化で消えるので} t3:=getRDTSC; Memo1.Lines.Add(format('T2-T1 %10d',[t2-t1])); Memo1.Lines.Add(format('T3-T2 %10d',[t3-t2])); end; --------------- T2-T1 1610740 T3-T2 4317497 間違いでなければ　mod 命令より速い 392 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:06:18 ] そうだね。 393 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:09:15 ] 上の and 7 は　 and -8 の間違いだった 394 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:33:37 ] でも、掛算を使うのはさらに半分だった。 for i := 1 to CNT do begin a := i shr 3; asm 　　 mov eax,$24924925; 　　 IMUL a; 　　 mov a,EDX; end; ww := i - ((a * 7) shl 3); // if ww<> (i mod 56) then Memo1.Lines.Add( 'Err'); end; t4 := getRDTSC; T2-T1 169613675 T3-T2 436034967 T4-T3 86040347 395 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:40:43 ] 　結局 idiv : ビット演算 : 掛算の　重さは　およそ　5 : 2 : 1 だった。 ビット演算　思ったよりガンバレるな。 396 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 19:24:47 ] これを高級言語で書いたら他の人に白い目で見られるだけならまだいいんだけど ひどい場合は書き直しすら命じられまする(´・ω・`) 397 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 19:44:35 ] そうだね。 398 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 20:36:07 ] >>396 高級言語の目的の一つが可読性の向上だからね。 コメントで解説いれても却下される場合すらあると思うよ。 399 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 20:48:20 ] 除算命令がないCPUなら有効だろうけど x % 60 が欲しい時とか、いちいち変換が大変だよな 400 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 21:47:03 ] 導出は機械的なプロセスだから、スクリプトみたいなのでサクッと求めるといいと思う。 可能なら、最適化の一環としてコンパイラに組み込むのがベストだが。 401 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 23:23:02 ] だから、掛け算化はgccでもやってるって。 402 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 00:18:01 ] >>401 ほんとにやってる？やらない場合も多いけど 絶対さぼってる 403 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 01:26:20 ] 昔のx86みたいにALUしかないCPUはそういう風にやってたのかぁ、勉強になりました。 404 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 01:29:46 ] >>403 定数割り算の掛け算化が行われない例があれば、逆に教えて欲しい。 まさか、最適化オプションを指定しないとしてくれないなんて言わないよね。 405 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 01:31:50 ] >>404 深く考えず単純に引き算かと 今考えると空恐ろしいやり方だｗ 406 名前：デフォルトの名無しさん mailto:sage [2007/06/25(月) 10:58:28 ] >404は>402宛てなんだろうなぁ。それはいいけど、>405は何を言いたいのだろう…… 407 名前：デフォルトの名無しさん mailto:sage [2007/06/25(月) 19:13:34 ] きっと8086には除算命令が無いと思ってるんだろう。 408 名前：デフォルトの名無しさん mailto:sage [2007/06/25(月) 19:57:27 ] Pen3では除算を浮動小数点ユニットでされるというのを見て、 浮動小数点ユニットが無い時には除算も無かったと思ったのかな 除算そのものはシフト減算比較の繰り返しで出来るから サイクル数さえ必要なだけかければマイクロプログラム方式ならそうコストかからない 掛け算と変わらない。 409 名前：405 mailto:sage [2007/06/26(火) 07:50:34 ] >>406 あ、ほんとだね >>407,408 んにゃ、引き算の連続で商余求めてたのかなと 410 名前：デフォルトの名無しさん mailto:sage [2007/06/26(火) 08:23:37 ] これは固定での剰余だから高速化出来るのであって 変数での剰余になると、結局コードで書いても加え戻し法(復元法)とかになるので 除算命令使った方がやっぱり速い。 411 名前：デフォルトの名無しさん mailto:sage [2007/06/28(木) 00:42:51 ] DSP(やCell)では逆数をニュートン法で求めるのが定番 412 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 16:40:57 ] 8086で除算命令使うとCPUの方で乗算とシフト命令に解釈しなおす訳？ ということは除算命令自体はマクロになるのかな 413 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 18:16:20 ] は？ 414 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 19:57:33 ] 除算命令に出くわして、せっせとメモリ中のコードを書き換える、けなげな86の姿を想像した・・・ 415 名前：デフォルトの名無しさん mailto:sage [2007/07/11(水) 22:50:58 ] 言う事聞かない奴隷なんかいらない 416 名前：デフォルトの名無しさん [2007/07/21(土) 07:45:05 ] >>412 マイクロプログラムで処理してるんだろ ＞8086のマイクロコードは、命令長が21ビットで、プログラムサイズは504ステップであった 417 名前：デフォルトの名無しさん mailto:sage [2007/07/21(土) 10:07:54 ] そろそろダンゴさんに〆てもらうか。 418 名前：デフォルトの名無しさん mailto:sage [2007/07/21(土) 21:50:22 ] うむ 419 名前：デフォルトの名無しさん [2007/08/03(金) 07:04:32 ] あ 420 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 11:40:01 ] ダゴンを深淵から呼びだしては駄目だ 421 名前：だんごの輪島 [2007/08/03(金) 12:15:43 ] ん? 422 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 21:06:03 ] は？ 423 名前：デフォルトの名無しさん [2007/08/12(日) 09:53:59 ] は 424 名前：デフォルトの名無しさん mailto:sage [2007/08/12(日) 10:01:53 ] ビッチ演算 425 名前：デフォルトの名無しさん mailto:sage [2007/08/12(日) 14:27:31 ] ビット大佐 426 名前：デフォルトの名無しさん [2007/08/14(火) 10:07:39 ] age 427 名前：デフォルトの名無しさん mailto:age [2007/08/14(火) 11:48:05 ] あ 428 名前：デフォルトの名無しさん mailto:sage [2007/08/16(木) 20:39:50 ] 〆 429 名前：デフォルトの名無しさん [2007/08/18(土) 23:05:50 ] あｇｗ 430 名前：デフォルトの名無しさん mailto:sage [2007/08/18(土) 23:09:42 ] ぬるぽ 431 名前：デフォルトの名無しさん [2007/08/20(月) 01:29:30 ] ちょっとスレの趣旨と違うと思うんだけど、適当なところが無かったので、 アドバイス頼む。 アドレスのアライメントをチェックするためにポインタをintにキャストして &でビットテストしてる。 extern char *p; if(((int)p & 3) == 0){ //32bit境界にある処理… } だけどアドレスをintにキャストするのは64bit時代的に行儀悪いみたい。 でもアドレスをビットテストしたいという状況は普通にあると思うんで、 こういう場合C系的にはどう書くのが上手な作法なの？

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef