【高速化】ビット演算　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 266 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:06:16 ] Cだとバリアント型はにっくきCOMの象徴のひとつだからトラウマが・・・ｗ 267 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:11:53 ] 皆がどのレスについてレスしてるのか分からなくなってきた。 つーかビット演算スレでなぜ共用体…。 「そういう発想」というのは共用体をvariantとして使う発想ということかしら。 268 名前：webmaster@気まぐれアナスイ mailto:192.168.0.1 [2007/05/28(月) 23:11:54 ] 　　 { >>>>>>>>985 } 　　　 ζ 　 　　　!(+Φ＿Φ)つ√ζ 　 　 +⊂.　+ 〆∂ 　 {Ж} 　 　 "〆∂∂ 　 　〆〆 　 .:" 269 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:15:15 ] コピペ君って馬鹿だな、まで読んだ。 270 名前：デフォルトの名無しさん [2007/05/28(月) 23:38:38 ] >>256 でも共用体って記述した順番にメモリに保存されるかについて 仕様では未定義ですよね 271 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:40:46 ] >>270 当たり前だろ。 つか struct の仕様と混同してないか? 272 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:43:42 ] >>270 これはひどい 273 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:45:43 ] コンパイラコンパイラ触ってるなら、 このくらい常識だろ？ 274 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:46:54 ] という批判と、このスレでの質問だという事を考えると、>>249　は typedef union { 　　uint32_t *pW; 　　uint8_t *pB; } HogeType; HogeType a; uint8_t w; a.pW = &src; a.pB[0] ^= a.pB[3]; a.pB[1] ^= a.pB[2]; a.pB[2] ^= a.pB[1]; a.pB[3] ^= a.pB[0]; a.pB[0] ^= a.pB[3]; a.pB[1] ^= a.pB[2]; みたいなのが希望って事か？ 275 名前：デフォルトの名無しさん mailto:sage [2007/05/28(月) 23:49:33 ] それは二重に規格違反してて、 おかしくなるコンパイラもあるらしいよ。 俺はそういうの見た事無いけど。 276 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 00:13:33 ] おかしくなるコンパイラがあるのではなく、動作が保証されないということ。 そういうコンパイラが現実にあるのかと言われても、んなこと知らん。 だが、顧客に「正常に動作することが保証されている」プログラムを提供するためには 仕様上未定義とされる書き方をしてはいけないし、意識せずしてしまったらバグとして扱われて然り。 277 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 00:20:53 ] 参考までに>>274の規格違反している点を簡単に指摘してください 278 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 00:32:45 ] 規格違反していても、多分 >>249 がおかしくなる処理系はないんじゃね？ 逆に、規格通り書いてもおかしくなることもある。 規格違反はそれはそれで重要だけど、 実際の処理系でどうなのかという方が時に重要な事もある。 ま、コメントとか残しておいて、 移植時にすぐ検索できるようにしておくべきではあるが。 279 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 00:44:32 ] >>277 共用体の pW メンバに代入した場合、 pW の値しか正当性が保証されない。 そのため、pW に代入したすぐ後に pB を参照したとき、 規格ではその動作を保証しない。 uint32_t * と uint8_t * のアドレス表現が等しいという保証は無い。 この間のキャストで何らかの変換作業が生じる場合には、 このコードは正しく動かない。 そもそもアドレス演算は、配列要素へのポインタでしか保証されない （配列風の参照では p[4] と *(p + 4) は等価で、 　ここには p + 4 というアドレス演算が生じる）。 ここが原因で >>274 のようなことをすると おかしくなる処理系があるという風に聞いている。 （「ハッカーのたしなみ」 の 87 ページを参照） 280 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 01:08:03 ] ハッカーのたしなみ に一致する日本語のページ 約 104 件 ハッカーのたのしみ に一致する日本語のページ 約 26,800 件 281 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 01:15:26 ] すまんよ。まちがえた。 282 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 10:36:39 ] そもそもCの言語仕様で「未定義」な理由は、最初のバイトが最上位か最下位かはエンディアン依存だから。 逆にいうとハードに強く依存する標準仕様はあってはならない。 もちろん環境が特定できる場合なら、エンディアンの違いを理解して使うぶんにはまったく問題ない。 むしろ同一アーキテクチャでならコンパイラのABIレベルではこういう部分も互換性が保障されてないと駄目。 そもそもエンディアンなんて標準仕様外のものを扱うのに、標準仕様を持ち出すほうがおかしいと思うがね 構造体などのデータアラインメントやABIの互換性は言語の規格じゃなくて 各CPUやOSのメーカー、コンパイラメーカーなど同士の取り決めで決まる。 つーか、暗黙の共通仕様や独自仕様にたよらないとTCP/IPすら扱えないぜ。 283 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 10:52:02 ] 構造体のアラインメントはC仕様では未定義だが、アラインメント不整合だと例外を起こすアーキもある。 データレイアウトを実装者で取り決める独自仕様が認められないなら、Cは危険な言語だな逆にいえば。 「仕様では未定義」は逆にいえば実装では各環境のABIに従ってきめていいということ。 284 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 11:17:39 ] >>282-283 仕様上未定義を「未定義の動作」と混同していないか。 Cは移植性を高めるため、特定の環境に依存するような仕様はほとんど盛り込まれておらず よって指摘の通り構造体のメモリ上でのレイアウトも定義されていない。 だが、メンバに正しくアクセスできることは保証されている。 285 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 11:25:40 ] 実は未定義ではなく実装依存という罠 286 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 11:38:48 ] エンディアンの変換はほぼ間違いなくできるがリトルからビッグかビッグからリトルかはエンディアン依存ってことだろ。 逆に>>349が意図しない動きをするコード吐くコンパイラって存在するなら教えてほしい。 変態のCellですら>>349が正しく動くことはABIレベルで保証されてる。 各型のレイアウトを厳密に定義してるからな。 287 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 11:43:14 ] 共用体で　 ビットフィールド　を使えば、マシになるかい？ 288 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 12:21:19 ] >>286 >>276 そして話題はループする。 ABIはCの言語仕様における実装依存の箇所を定めて厳密化するものなので たとえABIの隙をかいくぐって自分の予期した挙動をさせることができたとしても それは立派な規格違反。 あと、もし>>282さんと同一人物なら ＞そもそもCの言語仕様で「未定義」な理由は、最初のバイトが最上位か最下位かはエンディアン依存だから。 これのソースを頼む。探しているんだが、見つからない（汗 289 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 12:27:18 ] 規格にないものを扱うのに規格内のルールを持ち出す馬鹿。 windows.hを使うのも規格違反だとか言い出しそうだな 290 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 12:34:19 ] 厳密にはそうだな。ハンドルをポインタ型とかメチャクチャしたMSは糞。 ちなみに、規格にないものを付け加えるのではなく、規格に抜けているを補うのがABI。 本来は規格に矛盾しないABIを定めなければならない。 ところでここはビット演算についてかたるスレなのか？ 291 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 12:56:10 ] ミドルエンディアンのこともたまには思い出してやってください 292 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 13:13:17 ] GUIがなくてstdioで画面入出力するようなアプリのほうが品質低いと見なすがなうちの顧客は。 「定義するな」なら違反になるが単に未定義のものに一定の動作保証をするだけなら違反じゃない。 何のために#pragmaが規格にあると思ってる。 処理系依存の拡張を、やっていいよと保証すらしてるのが規格だ。 ちなみにunion使った型変換はWindowsでは日常茶飯事だな。ULONG_INTEGERとか。 ここの住人がよく使うであろうMMXやSSEなんかはC用APIなんか、まさに共用体を使った型変換のオンパレード。 それでもパフォーマンスを求める客の「信頼」を得るためにすすんで使うものだ。 ANSI/ISO規格が絶対的に信頼されてて規格外のものは信頼されてないなんて独善的な言い分にすぎん。 getsみたいな危険な関数が野放しにされてるのはなんだね。 極論、信頼性の確保という面ではVC2005のセキュアCRT関数のほうが標準関数よりまとも。 ちなみにポインタをHANDLEという型にtypedefできるのは規定の動作。なんら問題ない。 293 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 13:37:27 ] きもちわるいなあ 294 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 14:40:40 ] エチケット袋持ってきましょうか？ 295 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 15:10:33 ] いえ結構。そのまま吐きます 296 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 15:14:49 ] キッシュを食うのとエチケット袋を使うのはガキ。 297 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 17:55:34 ] 「規格違反のプログラム」 は、 特定の環境では動くことが保証されてるかもしれないけど、 全ての環境で動く保証が無い。 だから、そのプログラムが特定の環境でのみ使用される事が決まってるなら、 規格違反でもその環境でちゃんと動作する事が保証されていれば問題ない。 ただ、色んな環境で使われるプログラムであれば、規格通りに作らないといけない。 つまりは要件次第の問題であって、常にどちらかでないといけないみたいな事を言うのは愚。 >>292 gets の使用は規格で推奨されていない。 未だ存在しているのは単に互換性のため。 セキュアCRT関数は安全だが、 GCC でコンパイルしたいような場合には #if 使って GCC でも大丈夫なようにする必要がある。 あと、ハンドルで問題とされているのは、 ハンドルの値は別にアドレスではないのに ポインタに入れるようにしている点。 ただ、これは int にしてしまうと安全性が低くなるし、 環境依存という程ちゃんと動かなくなる環境もないしで、 いい hack だと思う。 298 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 18:53:41 ] 話は逸れるが、ハンドルも全てがアドレス値（ポインタ）でないとは限らない。 ドラッグ＆ドロップの処理などでGlobalAllocでメモリ確保したものを HDROP型へキャストしてやるという事例がある。 ふうんと言われればそれまでのことだけど。 299 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 18:56:05 ] それをいうなら、そもそもポインタ（というより左辺値）だってアドレス値とは限らないでしょ？ 300 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 19:02:00 ] プログラムごとに論理的なアドレス空間を持ってるんじゃないの？ 昔、物理的なアドレスを使えば一意だろうと思って使ったら、見事に失敗した。 301 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 19:09:48 ] ＞ハンドルの値は別にアドレスではないのに ＃ハンドルの値は別にアドレスとは限らないのに とするか。 302 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 19:13:49 ] まあ、メンバ関数ポインタなんかは 確かにメモリアドレス以上の情報を持ってることもあるけど、 C++ における「アドレス」ってのは、 そういう情報も含むんじゃないのかな。多分。 303 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 20:07:37 ] きょうび、１つのCPUでも「アドレス」が3種類くらいあって当たり前だしなぁ 304 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 20:27:53 ] Cはアドレスの概念を抽象化したから、Cにはアドレスという概念はないと。 どっかで見た。 305 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 20:36:02 ] ところがどっこい&演算子の読み方は・・・ 306 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 21:00:16 ] アドレス演算子だな。 307 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 21:24:50 ] えっ？reference operatorじゃないの？ とか思ったけどそれはC++の話でしたねすいません 308 名前：デフォルトの名無しさん mailto:sage [2007/05/29(火) 21:53:21 ] ANSI C: address operator 別名: reference operator 309 名前：・∀・）っ-○◎● mailto:sage [2007/05/30(水) 01:32:06 ] よーしだんごやさんが燃料投下するぞー 「共用体を使った型変換は、保証されないとむしろ違反」 uint32とuint8[4]の完全なアドレス共用が保証できなければ ・各パートの先頭アドレスの一致 ・char型(=1バイト)配列のデータ連続性 という規格で保証された動作に違反することになる。 断言する。 バイトオーダさえ一致すれば、共用体を使ったビット列の直接変換は保証できる。 つーか、規格にない動きまで保証されると規格【違反】なら、 Cコンパイラは現実のアーキテクチャ向けに実装された時点で違反を抱えることになり 空想の産物でなければならないことになるね。 規格外と規格違反を混同してるんじゃないの。 規格にない機能を実装したり独自の制約・動作保証をしたらいけないなんて規約は 規格に存在しない。 310 名前：・∀・）っ-○◎● mailto:sage [2007/05/30(水) 01:35:52 ] RubyはCで書かれてるけどオブジェクトは共用体を巧みに使うことでで実装されてるね。 それでもさまざまなプラットフォームに移植されてるけどｗｗｗｗ 311 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 01:47:03 ] 最適化でどうなるかとかちゃんと考えてるか？ 312 名前：・∀・）っ-○◎● mailto:sage [2007/05/30(水) 01:59:18 ] まあ、パーシャルリード・ライトはモダンアーキテクチャでは遅いから速度面でのメリットないし バイトオーダーの変換に共用体を持ち出すこと自体は俺としても感心しない。 HDの洗礼受けた人間ならこんな厨コードになるだろう uint32 bswap(uint32 n) { n = (n >> 16 | n << 16); return ((n >> 8) & 0x00FF00FF) | ((n << 8) & ~0x00FF00FF); } こんなコードを書く間にもx86なら即値が使えるとか、 PowerPCならAND-NOT命令があるから定数ロードは1個だけでいいとか アーキの特性を考えながら組む。 速くなるか遅くなるかも実装依存。それがビット演算厨の愉しみ。 書いた後で、「PPCとx86なら組み込みのBSWAPで十分な気もしてきた」とか思うのもまた一興。 313 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 02:07:16 ] んじゃ、燃料投下。 -- template<typename Type> static inline void endian(Type & val) { union foo {Type t; char c[sizeof(Type)];} bar = {val}; std::reverse(bar.c, bar.c + sizeof(bar)); val = bar.t; } 314 名前：・∀・）っ-○◎● mailto:sage [2007/05/30(水) 02:11:59 ] x86のeaxレジスタは下位半分はaxレジスタであり、ahとalでもある レジスタそのものが共用体なんですよ。 315 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 02:18:15 ] >>313 template<> static inline void endian<int>(int & val) { union foo {int t; char c[sizeof(int)];} bar = {val}; char tmp = bar.c[0]; bar.c[0] = bar.c[3]; bar.c[3] = tmp; tmp = bar.c[1]; bar.c[1] = bar.c[2]; bar.c[2] = tmp; val = bar.t; } -- これくらいの特殊化しておかないとw ついでに言うと、これをどう最適化するかがコンパイラの腕の見せ所。 316 名前：・∀・）っ-○◎● mailto:sage [2007/05/30(水) 02:21:07 ] 若本・・・じゃなかった、CellのSPEで実行 #include <algorithm> #include <stdio.h> template<typename Type> static inline void endian(Type & val) { union foo {Type t; char c[sizeof(Type)];} bar = {val}; std::reverse(bar.c, bar.c + sizeof(bar)); val = bar.t; } int main() { unsigned int i = 0x12345678; endian(i); printf("0x%0X\n", i); return 0; } [root@ps3 age]# spu-gcc test.cpp [root@ps3 age]# ./a.out 0x78563412 317 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 02:33:39 ] >>309 混同も何も、そもそも「規格外」とか「規格違反」とかいう用語は規格にあるのか？ 318 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 02:35:52 ] %0X って意味ねー。 %08X っしょ。 319 名前：・∀・）っ-○◎● mailto:sage [2007/05/30(水) 03:08:16 ] 64bitから8ビットだけを取り出して操作するってAESとかCamelliaではありがちな処理なんだよな。 よく最適化されたコードは、MMレジスタからpextrwで16ビットをeaxに転送した後、al, ahを使ってテーブル参照する。 320 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 08:24:42 ] 気色の悪いHN付ける奴の行動パターンやそこから透けて見えるパーソナリティっていうのは、 どいつもこいつもどうしてこう画一的・類型的で凡庸なんだろうなw 恐らく本人の自己イメージはその正反対なんだろうけどさ。 321 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 08:41:04 ] 凡庸乙 322 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 08:48:32 ] >>320 あなたのその発言もまた　画一的・類型的で凡庸　な事に気付いてての発言だとすれば　あなたは勇気がある。 気付いてないなら・・・・・ 323 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 08:56:16 ] 人間なんてみんな一緒だろ。 ハッキリいってイルカよりもマグロの方が頭いいです。 人類の知能は一億年遅れてる。 324 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 14:10:27 ] 【高速化】ビット演算　0x02 325 名前：デフォルトの名無しさん mailto:sage [2007/05/30(水) 20:38:32 ] 俺のアナルも高速化されそうです 326 名前：デフォルトの名無しさん mailto:sage [2007/05/31(木) 01:08:47 ] 俺様の射精は低速化されましたが何か? 327 名前：デフォルトの名無しさん mailto:sage [2007/05/31(木) 01:34:42 ] さらに角度までorz.... 328 名前：デフォルトの名無しさん mailto:sage [2007/05/31(木) 04:34:03 ] 自分の精液を味わって飲んでみましたクセになりそうです 329 名前：デフォルトの名無しさん mailto:sage [2007/05/31(木) 09:31:52 ] 【下ネタ化】ビッチ猥談 330 名前：デフォルトの名無しさん [2007/06/01(金) 01:04:55 ] >>328 なんか体調によって味とか変わってくるらしいね。調子がいいときはどんな味がするん？ 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を掛けた後に ビットシフトと足し算をしていた。それ以上追っかけるのはパス。

---

---

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

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