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

【高速化】ビット演算 ..

263:デフォルトの名無しさん
07/05/28 22:38:44
>>261
共用体に入れられるのはそもそも POD 型だけだが、
ポインタで保持しておくことなら可能だな。

264:デフォルトの名無しさん
07/05/28 22:54:29
>>262
> バリアント型とか知らないのかな。

Ｃ言語でそんなもん使う機会があまりないこととか知らないのかな。(w

265:デフォルトの名無しさん
07/05/28 22:59:44
いや、煽り抜きでそういう発想はちょっとないよね。

266:デフォルトの名無しさん
07/05/28 23:06:16
Cだとバリアント型はにっくきCOMの象徴のひとつだからトラウマが・・・ｗ

267:デフォルトの名無しさん
07/05/28 23:11:53
皆がどのレスについてレスしてるのか分からなくなってきた。
つーかビット演算スレでなぜ共用体…。

「そういう発想」というのは共用体をvariantとして使う発想ということかしら。

268:webmaster@気まぐれアナスイ
07/05/28 23:11:54
　　 { >>>>>>>>985 }
　　　 ζ
　　　　!(+Φ＿Φ)つ√ζ
　　 +⊂.　+ 〆∂ 　 {Ж}
　　 "〆∂∂
　　〆〆
　 .:"

269:デフォルトの名無しさん
07/05/28 23:15:15
コピペ君って馬鹿だな、まで読んだ。

270:デフォルトの名無しさん
07/05/28 23:38:38
>>256
でも共用体って記述した順番にメモリに保存されるかについて
仕様では未定義ですよね

271:デフォルトの名無しさん
07/05/28 23:40:46
>>270
当たり前だろ。

つか struct の仕様と混同してないか?

272:デフォルトの名無しさん
07/05/28 23:43:42
>>270
これはひどい

273:デフォルトの名無しさん
07/05/28 23:45:43
コンパイラコンパイラ触ってるなら、
このくらい常識だろ？

274:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/05/28 23:49:33
それは二重に規格違反してて、
おかしくなるコンパイラもあるらしいよ。
俺はそういうの見た事無いけど。

276:デフォルトの名無しさん
07/05/29 00:13:33
おかしくなるコンパイラがあるのではなく、動作が保証されないということ。
そういうコンパイラが現実にあるのかと言われても、んなこと知らん。
だが、顧客に「正常に動作することが保証されている」プログラムを提供するためには
仕様上未定義とされる書き方をしてはいけないし、意識せずしてしまったらバグとして扱われて然り。

277:デフォルトの名無しさん
07/05/29 00:20:53
参考までに>>274の規格違反している点を簡単に指摘してください

278:デフォルトの名無しさん
07/05/29 00:32:45
規格違反していても、多分 >>249 がおかしくなる処理系はないんじゃね？
逆に、規格通り書いてもおかしくなることもある。
規格違反はそれはそれで重要だけど、
実際の処理系でどうなのかという方が時に重要な事もある。
ま、コメントとか残しておいて、
移植時にすぐ検索できるようにしておくべきではあるが。

279:デフォルトの名無しさん
07/05/29 00:44:32
>>277
共用体の pW メンバに代入した場合、
pW の値しか正当性が保証されない。
そのため、pW に代入したすぐ後に pB を参照したとき、
規格ではその動作を保証しない。

uint32_t * と uint8_t * のアドレス表現が等しいという保証は無い。
この間のキャストで何らかの変換作業が生じる場合には、
このコードは正しく動かない。

そもそもアドレス演算は、配列要素へのポインタでしか保証されない
（配列風の参照では p[4] と *(p + 4) は等価で、
　ここには p + 4 というアドレス演算が生じる）。
ここが原因で >>274 のようなことをすると
おかしくなる処理系があるという風に聞いている。
（「ハッカーのたしなみ」の 87 ページを参照）

280:デフォルトの名無しさん
07/05/29 01:08:03
ハッカーのたしなみに一致する日本語のページ約 104 件
ハッカーのたのしみに一致する日本語のページ約 26,800 件

281:デフォルトの名無しさん
07/05/29 01:15:26
すまんよ。まちがえた。

282:デフォルトの名無しさん
07/05/29 10:36:39
そもそもCの言語仕様で「未定義」な理由は、最初のバイトが最上位か最下位かはエンディアン依存だから。
逆にいうとハードに強く依存する標準仕様はあってはならない。

もちろん環境が特定できる場合なら、エンディアンの違いを理解して使うぶんにはまったく問題ない。
むしろ同一アーキテクチャでならコンパイラのABIレベルではこういう部分も互換性が保障されてないと駄目。
そもそもエンディアンなんて標準仕様外のものを扱うのに、標準仕様を持ち出すほうがおかしいと思うがね
構造体などのデータアラインメントやABIの互換性は言語の規格じゃなくて
各CPUやOSのメーカー、コンパイラメーカーなど同士の取り決めで決まる。
つーか、暗黙の共通仕様や独自仕様にたよらないとTCP/IPすら扱えないぜ。

283:デフォルトの名無しさん
07/05/29 10:52:02
構造体のアラインメントはC仕様では未定義だが、アラインメント不整合だと例外を起こすアーキもある。
データレイアウトを実装者で取り決める独自仕様が認められないなら、Cは危険な言語だな逆にいえば。

「仕様では未定義」は逆にいえば実装では各環境のABIに従ってきめていいということ。

284:デフォルトの名無しさん
07/05/29 11:17:39
>>282-283
仕様上未定義を「未定義の動作」と混同していないか。
Cは移植性を高めるため、特定の環境に依存するような仕様はほとんど盛り込まれておらず
よって指摘の通り構造体のメモリ上でのレイアウトも定義されていない。

だが、メンバに正しくアクセスできることは保証されている。

285:デフォルトの名無しさん
07/05/29 11:25:40
実は未定義ではなく実装依存という罠

286:デフォルトの名無しさん
07/05/29 11:38:48
エンディアンの変換はほぼ間違いなくできるがリトルからビッグかビッグからリトルかはエンディアン依存ってことだろ。

逆に>>349が意図しない動きをするコード吐くコンパイラって存在するなら教えてほしい。
変態のCellですら>>349が正しく動くことはABIレベルで保証されてる。
各型のレイアウトを厳密に定義してるからな。

287:デフォルトの名無しさん
07/05/29 11:43:14
共用体で　ビットフィールド　を使えば、マシになるかい？

288:デフォルトの名無しさん
07/05/29 12:21:19
>>286
>>276
そして話題はループする。

ABIはCの言語仕様における実装依存の箇所を定めて厳密化するものなので
たとえABIの隙をかいくぐって自分の予期した挙動をさせることができたとしても
それは立派な規格違反。

あと、もし>>282さんと同一人物なら
＞そもそもCの言語仕様で「未定義」な理由は、最初のバイトが最上位か最下位かはエンディアン依存だから。
これのソースを頼む。探しているんだが、見つからない（汗

289:デフォルトの名無しさん
07/05/29 12:27:18
規格にないものを扱うのに規格内のルールを持ち出す馬鹿。
windows.hを使うのも規格違反だとか言い出しそうだな

290:デフォルトの名無しさん
07/05/29 12:34:19
厳密にはそうだな。ハンドルをポインタ型とかメチャクチャしたMSは糞。
ちなみに、規格にないものを付け加えるのではなく、規格に抜けているを補うのがABI。
本来は規格に矛盾しないABIを定めなければならない。

ところでここはビット演算についてかたるスレなのか？

291:デフォルトの名無しさん
07/05/29 12:56:10
ミドルエンディアンのこともたまには思い出してやってください

292:デフォルトの名無しさん
07/05/29 13:13:17
GUIがなくてstdioで画面入出力するようなアプリのほうが品質低いと見なすがなうちの顧客は。

「定義するな」なら違反になるが単に未定義のものに一定の動作保証をするだけなら違反じゃない。
何のために#pragmaが規格にあると思ってる。
処理系依存の拡張を、やっていいよと保証すらしてるのが規格だ。

ちなみにunion使った型変換はWindowsでは日常茶飯事だな。ULONG_INTEGERとか。
ここの住人がよく使うであろうMMXやSSEなんかはC用APIなんか、まさに共用体を使った型変換のオンパレード。
それでもパフォーマンスを求める客の「信頼」を得るためにすすんで使うものだ。

ANSI/ISO規格が絶対的に信頼されてて規格外のものは信頼されてないなんて独善的な言い分にすぎん。
getsみたいな危険な関数が野放しにされてるのはなんだね。
極論、信頼性の確保という面ではVC2005のセキュアCRT関数のほうが標準関数よりまとも。

ちなみにポインタをHANDLEという型にtypedefできるのは規定の動作。なんら問題ない。

293:デフォルトの名無しさん
07/05/29 13:37:27
きもちわるいなあ

294:デフォルトの名無しさん
07/05/29 14:40:40
エチケット袋持ってきましょうか？

295:デフォルトの名無しさん
07/05/29 15:10:33
いえ結構。そのまま吐きます

296:デフォルトの名無しさん
07/05/29 15:14:49
キッシュを食うのとエチケット袋を使うのはガキ。

297:デフォルトの名無しさん
07/05/29 17:55:34
「規格違反のプログラム」は、
特定の環境では動くことが保証されてるかもしれないけど、
全ての環境で動く保証が無い。
だから、そのプログラムが特定の環境でのみ使用される事が決まってるなら、
規格違反でもその環境でちゃんと動作する事が保証されていれば問題ない。
ただ、色んな環境で使われるプログラムであれば、規格通りに作らないといけない。

つまりは要件次第の問題であって、常にどちらかでないといけないみたいな事を言うのは愚。

>>292
gets の使用は規格で推奨されていない。
未だ存在しているのは単に互換性のため。
セキュアCRT関数は安全だが、
GCC でコンパイルしたいような場合には
#if 使って GCC でも大丈夫なようにする必要がある。

あと、ハンドルで問題とされているのは、
ハンドルの値は別にアドレスではないのに
ポインタに入れるようにしている点。
ただ、これは int にしてしまうと安全性が低くなるし、
環境依存という程ちゃんと動かなくなる環境もないしで、
いい hack だと思う。

298:デフォルトの名無しさん
07/05/29 18:53:41
話は逸れるが、ハンドルも全てがアドレス値（ポインタ）でないとは限らない。
ドラッグ＆ドロップの処理などでGlobalAllocでメモリ確保したものを
HDROP型へキャストしてやるという事例がある。

ふうんと言われればそれまでのことだけど。

299:デフォルトの名無しさん
07/05/29 18:56:05
それをいうなら、そもそもポインタ（というより左辺値）だってアドレス値とは限らないでしょ？

300:デフォルトの名無しさん
07/05/29 19:02:00
プログラムごとに論理的なアドレス空間を持ってるんじゃないの？
昔、物理的なアドレスを使えば一意だろうと思って使ったら、見事に失敗した。

301:デフォルトの名無しさん
07/05/29 19:09:48
＞ハンドルの値は別にアドレスではないのに
＃ハンドルの値は別にアドレスとは限らないのに

とするか。

302:デフォルトの名無しさん
07/05/29 19:13:49
まあ、メンバ関数ポインタなんかは
確かにメモリアドレス以上の情報を持ってることもあるけど、
C++ における「アドレス」ってのは、
そういう情報も含むんじゃないのかな。多分。

303:デフォルトの名無しさん
07/05/29 20:07:37
きょうび、１つのCPUでも「アドレス」が3種類くらいあって当たり前だしなぁ

304:デフォルトの名無しさん
07/05/29 20:27:53
Cはアドレスの概念を抽象化したから、Cにはアドレスという概念はないと。
どっかで見た。

305:デフォルトの名無しさん
07/05/29 20:36:02
ところがどっこい&演算子の読み方は・・・

306:デフォルトの名無しさん
07/05/29 21:00:16
アドレス演算子だな。

307:デフォルトの名無しさん
07/05/29 21:24:50
えっ？reference operatorじゃないの？
とか思ったけどそれはC++の話でしたねすいません

308:デフォルトの名無しさん
07/05/29 21:53:21
ANSI C: address operator
別名: reference operator

309:・∀・）っ-○◎●
07/05/30 01:32:06
よーしだんごやさんが燃料投下するぞー
「共用体を使った型変換は、保証されないとむしろ違反」

uint32とuint8[4]の完全なアドレス共用が保証できなければ

・各パートの先頭アドレスの一致
・char型(=1バイト)配列のデータ連続性
という規格で保証された動作に違反することになる。

断言する。
バイトオーダさえ一致すれば、共用体を使ったビット列の直接変換は保証できる。

つーか、規格にない動きまで保証されると規格【違反】なら、
Cコンパイラは現実のアーキテクチャ向けに実装された時点で違反を抱えることになり
空想の産物でなければならないことになるね。

規格外と規格違反を混同してるんじゃないの。
規格にない機能を実装したり独自の制約・動作保証をしたらいけないなんて規約は
規格に存在しない。

310:・∀・）っ-○◎●
07/05/30 01:35:52
RubyはCで書かれてるけどオブジェクトは共用体を巧みに使うことでで実装されてるね。
それでもさまざまなプラットフォームに移植されてるけどｗｗｗｗ

311:デフォルトの名無しさん
07/05/30 01:47:03
最適化でどうなるかとかちゃんと考えてるか？

312:・∀・）っ-○◎●
07/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:デフォルトの名無しさん
07/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:・∀・）っ-○◎●
07/05/30 02:11:59
x86のeaxレジスタは下位半分はaxレジスタであり、ahとalでもある
レジスタそのものが共用体なんですよ。

315:デフォルトの名無しさん
07/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:・∀・）っ-○◎●
07/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:デフォルトの名無しさん
07/05/30 02:33:39
>>309
混同も何も、そもそも「規格外」とか「規格違反」とかいう用語は規格にあるのか？

318:デフォルトの名無しさん
07/05/30 02:35:52
%0X って意味ねー。
%08X っしょ。

319:・∀・）っ-○◎●
07/05/30 03:08:16
64bitから8ビットだけを取り出して操作するってAESとかCamelliaではありがちな処理なんだよな。
よく最適化されたコードは、MMレジスタからpextrwで16ビットをeaxに転送した後、al, ahを使ってテーブル参照する。

320:デフォルトの名無しさん
07/05/30 08:24:42
気色の悪いHN付ける奴の行動パターンやそこから透けて見えるパーソナリティっていうのは、
どいつもこいつもどうしてこう画一的・類型的で凡庸なんだろうなw

恐らく本人の自己イメージはその正反対なんだろうけどさ。

321:デフォルトの名無しさん
07/05/30 08:41:04
凡庸乙

322:デフォルトの名無しさん
07/05/30 08:48:32
>>320
あなたのその発言もまた　画一的・類型的で凡庸　な事に気付いてての発言だとすれば　あなたは勇気がある。
気付いてないなら・・・・・

323:デフォルトの名無しさん
07/05/30 08:56:16
人間なんてみんな一緒だろ。
ハッキリいってイルカよりもマグロの方が頭いいです。
人類の知能は一億年遅れてる。

324:デフォルトの名無しさん
07/05/30 14:10:27
【高速化】ビット演算　0x02

325:デフォルトの名無しさん
07/05/30 20:38:32
俺のアナルも高速化されそうです

326:デフォルトの名無しさん
07/05/31 01:08:47
俺様の射精は低速化されましたが何か?

327:デフォルトの名無しさん
07/05/31 01:34:42
さらに角度までorz....

328:デフォルトの名無しさん
07/05/31 04:34:03
自分の精液を味わって飲んでみましたクセになりそうです

329:デフォルトの名無しさん
07/05/31 09:31:52
【下ネタ化】ビッチ猥談

330:デフォルトの名無しさん
07/06/01 01:04:55
>>328
なんか体調によって味とか変わってくるらしいね。調子がいいときはどんな味がするん？

331:デフォルトの名無しさん
07/06/01 01:06:15
ごめん、sage 忘れた。

332:デフォルトの名無しさん
07/06/01 14:45:44
ごめん、ぬるぽ忘れた。

333:デフォルトの名無しさん
07/06/01 15:11:37
ぬるぽの話題は参照の話題について直接的ないし間接的に関係のあるスレッドでしか出す事は許さん。

334:デフォルトの名無しさん
07/06/01 15:23:11
>>329
それを言うなら「低俗化」では?

335:デフォルトの名無しさん
07/06/01 17:57:17
風俗化

336:デフォルトの名無しさん
07/06/01 18:11:47
Jデッ化

337:デフォルトの名無しさん
07/06/01 18:35:50
つーかおまいらこんなことしてていいの化

338:デフォルトの名無しさん
07/06/01 23:16:16
ばか

339:デフォルトの名無しさん
07/06/02 12:18:51
珍しく最近妙にスレが伸びてると思ったら、こう言う内容だったの化

340:デフォルトの名無しさん
07/06/03 02:25:37
なんじゃゴラァ、おまいらバカ化

341:デフォルトの名無しさん
07/06/03 04:24:42
あ？

342:デフォルトの名無しさん
07/06/19 21:59:45
0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000

ってどんな意味のあるビット列ですか？
教えてください。

343:デフォルトの名無しさん
07/06/19 22:04:20
パイオニアだかボイジャーだかのレコード盤に記録されてる奴？

344:デフォルトの名無しさん
07/06/19 22:17:46
Gray Codeだな

345:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/19 23:15:55
ううまま　うままう　うまう　うままう

347:デフォルトの名無しさん
07/06/20 12:26:09
>>342
たとえば、機械類なんかの位置あわせの目的で　センサーを配置する時に
４入力あれば１６箇所の位置を特定できるわけだけど
同時に２つのセンサーが変化するようになってると巧くゆかない。
そこで移動につれて、一つしかセンサーが変化しないような配置方法を考えたのがそのコード。

348:デフォルトの名無しさん
07/06/20 14:21:11
要するに>>342は
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
って意味

349:デフォルトの名無しさん
07/06/20 18:58:03
>>347-348が理解できない

350:デフォルトの名無しさん
07/06/20 19:07:00
ばっかー

351:デフォルトの名無しさん
07/06/20 19:09:51
2ビットのグレイコードは、2相エンコーダと呼ばれてる。　機械式のマウスなんかで使われている。
　00 01 11 10　この順番で動けば順方向　逆方向なら　00 10 11 01 と動くので区別出来る

2進数 00 01 10 11 でいいじゃないと思うだろうけど　これだと一度に2ビット変化する箇所が2度出来る
センサーの取りつけに物凄い精度が要求される事になり安価なマウスに採用出来ない

352:デフォルトの名無しさん
07/06/21 00:53:52
ハミング距離でぐぐるといいよ

353:デフォルトの名無しさん
07/06/21 01:35:52
上位ビットから順に加算して途中でやめても、下位ビットの影響がそれより上に及ばない、っていう利点もある。

354:デフォルトの名無しさん
07/06/21 01:46:36
>>353
それ、具体的に教えて。

355:デフォルトの名無しさん
07/06/21 23:48:28
56の余りを求めるビットマスクはどのように書けばいいのでしょうか？

356:デフォルトの名無しさん
07/06/21 23:55:04
商か剰余を求めるビット演算を生成する CGI か何かを昔見かけたような気が・・・。
どこだっけかな・・・。

357:デフォルトの名無しさん
07/06/22 01:08:45
56の余りってなにさ?

358:デフォルトの名無しさん
07/06/22 01:17:06
x % 56でも計算したいんじゃね？

359:デフォルトの名無しさん
07/06/22 07:26:57
x % 56だと　２のベキ乗じゃないからビット演算1発では出来ないな
URLﾘﾝｸ(www.tensyo.com)
ここの後ろの方にビットマスクと繰り返し演算で剰余を求める方法がある

360:デフォルトの名無しさん
07/06/22 07:35:52
定数での除算って、こんなに繰り返し必要だったっけ？
３、４回の演算で書けたような気が・・・って、俺の記憶違いか？

361:デフォルトの名無しさん
07/06/22 07:37:37
それ、もしかしたら、２のべき乗での除算？

362:デフォルトの名無しさん
07/06/22 07:40:38
いや、それなら１回でいけるし。

あれ？乗算だっけ？

363:デフォルトの名無しさん
07/06/22 07:42:31
ああ、何か乗算だった気もしてきた。スマン。

364:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/22 08:00:17
56*73 =4088 で 2^12-8 だから
a = ( (a>>12)<<3 ) + a & 4095; を　前段でやれば改善するんじゃないかな　

366:デフォルトの名無しさん
07/06/22 09:49:41
最近のコンパイラは定数の割り算は掛け算に置き換えるね。
56で割るロジックをコンパイルしたら、-1840700269を掛けた後に
ビットシフトと足し算をしていた。それ以上追っかけるのはパス。

367:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/22 10:11:46
なるほど、>366の数値が0x92492493だからシフト量が違う同じビットパターンなのか。

369:デフォルトの名無しさん
07/06/22 10:17:29
でもまあPCのCPUみたいに掛算が高速だったらって前提だな。
1チップとかだと　掛算はビットサイズに応じたサイクル数かかるし
掛け算持ってないＣＰＵもあるし

370:デフォルトの名無しさん
07/06/22 10:21:39
大丈夫、そういうCPUは割り算も遅い。

371:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/22 10:34:31
演算子の数が20を超えてるな。
素直にdiv使った方が速いかもしれない。

373:デフォルトの名無しさん
07/06/22 10:45:50
もうちょっとバランスをうまく取れば、1行減らせるかもな

374:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/22 11:26:49
>>372
div 命令は、持っていてもbit数のサイクルかかるのが殆どだよ。　だから >>366-367 のような最適化がされるんだし

377:デフォルトの名無しさん
07/06/22 11:33:21
ただ PC の場合はレイテンシがかかるだけだから、divを使った方が速いかもしれないな。

378:デフォルトの名無しさん
07/06/22 11:37:09
>>367
ここまでしても idiv より速いのか・・・。

379:デフォルトの名無しさん
07/06/22 11:48:18
Pentium II およびPentium III プロセッサの実行ユニット

整数乗算は　レイテンシ4、スループット1/ サイクル
除算は浮動小数点ユニットで行われ
FDIV 命令　レイテンシ: 単精度17 サイクル、倍精度36 サイクル、拡張精度56 サイクル

だから、桁違いにレイテンシが大きい。

380:デフォルトの名無しさん
07/06/22 11:50:39
浮動小数点ユニットで行われるのか？！

381:デフォルトの名無しさん
07/06/22 11:58:11
だって　整数乗算ユニットってのはブロック図にあるが、　整数除算ユニットってのはどこにも無いだろ？

除算ってのはコストのわりに利用頻度が少ないから、どうせ浮動小数点ユニットもってるからそっちで計算させてるのさ
仮に、整数演算ユニットで除算をしたとしても、結局32サイクルはかかるし、その間加減算比較ユニットの一つが潰れてしまうからな

382:デフォルトの名無しさん
07/06/22 12:14:11
そうだったのか・・・。
そら遅いわな。

383:デフォルトの名無しさん
07/06/22 12:27:02
>>381
これ以上はスレ違いになるがつっこませてくれ。
浮動小数点ユニットがIEEE754（だったっけ）で処理する場合、単精度で23ビット、倍精度で52ビットの精度だろ。
被序数が32ビット整数ならともかく、64ビット整数の除算は精度の問題上アウトだぞ。

384:デフォルトの名無しさん
07/06/22 12:34:23
>>383
Intel 系の浮動小数点ユニットは
拡張倍精度（80ビット/仮数部64ビット）で行われてるから大丈夫。

385:デフォルトの名無しさん
07/06/22 12:44:20
>>384
まじか！と思って何年も開いていない重たいバインダーを紐解いてみたら、たしかにそう書かれているな。
しかも本当は63ビット精度なのに、ケチりビットをケチらない荒技で対処してるし・・・。
そのうえx87コプロに限ればつねに拡張倍精度で計算されることになってたりして、もうね、馬(ry。

386:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/22 13:07:24
しかし、1/7って面白いなぁ。10進だけでなく16進でも綺麗な循環小数になるんだな。

388:デフォルトの名無しさん
07/06/22 13:08:10
もしかして >>375 のような事しても idiv 使うより速いって事はありえるのか？

389:デフォルトの名無しさん
07/06/22 16:51:54
>>388
実際に速度を比較してみれば？

Cの場合、&より+の方が優先順位が高いので、
>>375の&演算には括弧が必要だね。

390:デフォルトの名無しさん
07/06/22 17:06:59
そうだね。

391:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/22 18:06:18
そうだね。

393:デフォルトの名無しさん
07/06/22 18:09:15
上の and 7 は　 and -8 の間違いだった

394:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/06/22 18:40:43
　結局 idiv : ビット演算 : 掛算の　重さは　およそ　5 : 2 : 1 だった。

ビット演算　思ったよりガンバレるな。

396:デフォルトの名無しさん
07/06/22 19:24:47
これを高級言語で書いたら他の人に白い目で見られるだけならまだいいんだけど
ひどい場合は書き直しすら命じられまする(´・ω・`)

397:デフォルトの名無しさん
07/06/22 19:44:35
そうだね。

398:デフォルトの名無しさん
07/06/22 20:36:07
>>396
高級言語の目的の一つが可読性の向上だからね。
コメントで解説いれても却下される場合すらあると思うよ。

399:デフォルトの名無しさん
07/06/22 20:48:20
除算命令がないCPUなら有効だろうけど
x % 60 が欲しい時とか、いちいち変換が大変だよな

400:デフォルトの名無しさん
07/06/22 21:47:03
導出は機械的なプロセスだから、スクリプトみたいなのでサクッと求めるといいと思う。
可能なら、最適化の一環としてコンパイラに組み込むのがベストだが。

401:デフォルトの名無しさん
07/06/22 23:23:02
だから、掛け算化はgccでもやってるって。

402:デフォルトの名無しさん
07/06/23 00:18:01
>>401
ほんとにやってる？やらない場合も多いけど
絶対さぼってる

403:デフォルトの名無しさん
07/06/23 01:26:20
昔のx86みたいにALUしかないCPUはそういう風にやってたのかぁ、勉強になりました。

404:デフォルトの名無しさん
07/06/23 01:29:46
>>403
定数割り算の掛け算化が行われない例があれば、逆に教えて欲しい。
まさか、最適化オプションを指定しないとしてくれないなんて言わないよね。

405:デフォルトの名無しさん
07/06/23 01:31:50
>>404
深く考えず単純に引き算かと
今考えると空恐ろしいやり方だｗ

406:デフォルトの名無しさん
07/06/25 10:58:28
>404は>402宛てなんだろうなぁ。それはいいけど、>405は何を言いたいのだろう……

407:デフォルトの名無しさん
07/06/25 19:13:34
きっと8086には除算命令が無いと思ってるんだろう。

408:デフォルトの名無しさん
07/06/25 19:57:27
Pen3では除算を浮動小数点ユニットでされるというのを見て、
浮動小数点ユニットが無い時には除算も無かったと思ったのかな

除算そのものはシフト減算比較の繰り返しで出来るから
サイクル数さえ必要なだけかければマイクロプログラム方式ならそうコストかからない
掛け算と変わらない。

409:405
07/06/26 07:50:34
>>406
あ、ほんとだね
>>407,408
んにゃ、引き算の連続で商余求めてたのかなと

410:デフォルトの名無しさん
07/06/26 08:23:37
これは固定での剰余だから高速化出来るのであって
変数での剰余になると、結局コードで書いても加え戻し法(復元法)とかになるので
除算命令使った方がやっぱり速い。

411:デフォルトの名無しさん
07/06/28 00:42:51
DSP(やCell)では逆数をニュートン法で求めるのが定番

412:デフォルトの名無しさん
07/07/08 16:40:57
8086で除算命令使うとCPUの方で乗算とシフト命令に解釈しなおす訳？
ということは除算命令自体はマクロになるのかな

413:デフォルトの名無しさん
07/07/08 18:16:20
は？

414:デフォルトの名無しさん
07/07/08 19:57:33
除算命令に出くわして、せっせとメモリ中のコードを書き換える、けなげな86の姿を想像した・・・

415:デフォルトの名無しさん
07/07/11 22:50:58
言う事聞かない奴隷なんかいらない

416:デフォルトの名無しさん
07/07/21 07:45:05
>>412
マイクロプログラムで処理してるんだろ
＞8086のマイクロコードは、命令長が21ビットで、プログラムサイズは504ステップであった

417:デフォルトの名無しさん
07/07/21 10:07:54
そろそろダンゴさんに〆てもらうか。

418:デフォルトの名無しさん
07/07/21 21:50:22
うむ

419:デフォルトの名無しさん
07/08/03 07:04:32
あ

420:デフォルトの名無しさん
07/08/03 11:40:01
ダゴンを深淵から呼びだしては駄目だ

421:だんごの輪島
07/08/03 12:15:43
ん?

422:デフォルトの名無しさん
07/08/03 21:06:03
は？

423:デフォルトの名無しさん
07/08/12 09:53:59
は

424:デフォルトの名無しさん
07/08/12 10:01:53
ビッチ演算

425:デフォルトの名無しさん
07/08/12 14:27:31
ビット大佐

426:デフォルトの名無しさん
07/08/14 10:07:39
age

427:デフォルトの名無しさん
07/08/14 11:48:05
あ

428:デフォルトの名無しさん
07/08/16 20:39:50
〆

429:デフォルトの名無しさん
07/08/18 23:05:50
あｇｗ

430:デフォルトの名無しさん
07/08/18 23:09:42
ぬるぽ

431:デフォルトの名無しさん
07/08/20 01:29:30
ちょっとスレの趣旨と違うと思うんだけど、適当なところが無かったので、
アドバイス頼む。

アドレスのアライメントをチェックするためにポインタをintにキャストして
&でビットテストしてる。

extern char *p;
if(((int)p & 3) == 0){
//32bit境界にある処理…
}

だけどアドレスをintにキャストするのは64bit時代的に行儀悪いみたい。

でもアドレスをビットテストしたいという状況は普通にあると思うんで、
こういう場合C系的にはどう書くのが上手な作法なの？

432:デフォルトの名無しさん
07/08/20 01:38:30
>>431
Linux界隈じゃ unsigned long へのキャストが一般的とされてるが
個人的には嫌い

433:デフォルトの名無しさん
07/08/20 01:40:50
intptr_t / uintptr_t を使えばいいんじゃない？

434:デフォルトの名無しさん
07/08/20 08:48:31
下位ビットだけ入ればいいので、charでもいい

435:デフォルトの名無しさん
07/08/20 23:58:10
さすがにそれはありえないだろ?

436:デフォルトの名無しさん
07/08/21 00:11:51
なぜそう思うの？

437:デフォルトの名無しさん
07/08/21 00:33:14
バイトオーダー

438:デフォルトの名無しさん
07/08/21 00:37:00
バイトオーダーは関係ないかと

439:・∀・）っ-○◎●
07/08/21 00:52:14
WindowsならUINT_PTRにキャスト

440:デフォルトの名無しさん
07/08/21 01:00:01
ダンゴさんがピシっと〆めたな。

441:・∀・）っ-○◎●
07/08/21 01:19:06
うんこうんこうんｋ

442:デフォルトの名無しさん
07/09/09 23:01:40
う

443:デフォルトの名無しさん
07/09/09 23:35:23
ん

444:デフォルトの名無しさん
07/09/09 23:37:25
ち

445:デフォルトの名無しさん
07/09/09 23:45:20
ゃ

446:デフォルトの名無しさん
07/09/16 06:34:05
あ

447:デフォルトの名無しさん
07/09/19 12:28:31
は

448:デフォルトの名無しさん
07/09/19 12:32:11
た

449:デフォルトの名無しさん
07/09/19 13:50:16
ぼ

450:デフォルトの名無しさん
07/09/19 23:03:56
ぬ

451:デフォルトの名無しさん
07/09/19 23:56:29
る

452:デフォルトの名無しさん
07/09/20 00:04:43
ぽ

453:デフォルトの名無しさん
07/09/20 18:42:49
>>450-452
ｶﾞ

454:デフォルトの名無しさん
07/09/22 00:43:27
ｽﾚﾘﾝｸ(tech板:555番)
これもっと簡単にならないかな？

455:デフォルトの名無しさん
07/09/22 07:06:58
>>454
--------------------
int my_fputwc(wint_t c, FILE *fp)
{ wint_t r = fputwc(c, fp);
return (r == WEOF) ? EOF : r;
}

int wtbl[0x10000];
void dokkade_jikkou(void ) {
int i;
for (i = 0; i < 0x10000; i++)
wtbl[i] = i;
wtbl[0xffff] = EOF;
}
int my_fputwc(wint_t c, FILE *fp) return wtbl[fputwc(c, fp);]; }

みたいなこと(WEOF(wint_tの0xffff)をEOF(intの-1)に変換)
をもっとスマートに行う方法ないですかね。
---------これで何の不満があるんだ？-----------
wtbl[0xffff] = EOF;
for (i = 0; i < 0xffff; i++)
wtbl[i] = i;
}
--------------------

456:デフォルトの名無しさん
07/09/27 20:24:00
age

457:デフォルトの名無しさん
07/09/29 23:03:31
int rotate_0_9(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;}
or
int rotate_0_9(int a){a++;return(a+((a+6)>>4)*6)&15;}

引数が0～8の時1を加算し、引数が9の時0を返す。

458:デフォルトの名無しさん
07/09/29 23:17:24
return ++a%9;

459:デフォルトの名無しさん
07/09/29 23:39:43
% はビット演算じゃないだろう

460:デフォルトの名無しさん
07/09/29 23:58:36
int rotate_0_9(int a){return a<9?a+1:0;}

461:デフォルトの名無しさん
07/09/30 00:06:34
DAA

462:デフォルトの名無しさん
07/09/30 00:15:35
>>457
>>458
>>460
どれが速い？

463:デフォルトの名無しさん
07/09/30 00:20:18
実測あるのみ

464:デフォルトの名無しさん
07/09/30 00:34:05
試してみた！
cl /O2 rot9.c
rot9
rotate_0_9_457_1 1873 msec
rotate_0_9_457_2 1272 msec
rotate_0_9_458 4016 msec
rotate_0_9_460 641 msec
>>460が圧倒的だった(俺もそう思ってた)

ソースに続く

465:デフォルトの名無しさん
07/09/30 00:34:50
>>464のソース (VC6SP4)
----------------------------
#include <windows.h>
#include <stdio.h>
int rotate_0_9_457_1(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;}
int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;}
int rotate_0_9_458(int a){return ++a%9;}
int rotate_0_9_460(int a){return a<9?a+1:0;}
//#define COUNT_TIMES 0x7fffffff
#define COUNT_TIMES 0x7ffffff
#define TEST(func) \
dwTime = GetTickCount(); \
for(i = 0, count = 0; count < COUNT_TIMES ; count++) { \
i=func(i); \
} \
printf( # func " %d msec\n", GetTickCount() - dwTime);
main() {
int i, count;
DWORD dwTime;
SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);
Sleep(100);
TEST(rotate_0_9_457_1)
Sleep(100);
TEST(rotate_0_9_457_2)
Sleep(100);
TEST(rotate_0_9_458)
Sleep(100);
TEST(rotate_0_9_460)
return 0;
}
----------------------------

466:デフォルトの名無しさん
07/09/30 00:38:34
printf( # func " %d msec (i:%d)\n", GetTickCount() - dwTime, i);
と変更して計算結果も表示してみたら>>457の最初の式の結果がおかしい事に
気付いたんだけど。

rotate_0_9_457_1 1862 msec (i:0)
rotate_0_9_457_2 1272 msec (i:7)
rotate_0_9_458 3986 msec (i:7)
rotate_0_9_460 671 msec (i:7)

467:デフォルトの名無しさん
07/09/30 00:40:00
int rotate_0_9_467(int a){
static int t[10]={1,2,3,4,5,6,7,8,9,0};
return t[a];
}
表引き。
これもやってみてくれ。

468:デフォルトの名無しさん
07/09/30 00:49:01
>>457
やってみるよ。

457_1のiの推移
0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14
無茶苦茶だった。

469:デフォルトの名無しさん
07/09/30 00:55:09
rotate_0_9_457_1 1893 msec (i:0)
rotate_0_9_457_2 1272 msec (i:7)
rotate_0_9_458 3996 msec (i:7)
rotate_0_9_460 661 msec (i:7)
rotate_0_9_467 621 msec (i:7)

テーブル引きのがわずかに速いね。
>>460と>>467が微差だったんでカウンタ倍にしてみた。
#define COUNT_TIMES 0xfffffffに変更。

rotate_0_9_457_1 3535 msec (i:2)
rotate_0_9_457_2 2553 msec (i:5)
rotate_0_9_458 7991 msec (i:5)
rotate_0_9_460 1332 msec (i:5)
rotate_0_9_467 1202 msec (i:5)

計ったPCはThinkPad X31 (PenM1.6G Banias) XPSP2

470:デフォルトの名無しさん
07/09/30 00:57:00
あと>>458は0～8の繰り返しで条件が違うんで
int rotate_0_9_458(int a){return ++a%10;}
に修正してる

471:デフォルトの名無しさん
07/09/30 01:13:29
_rotate_0_9_457_2 PROC NEAR
; 13 : int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;}

mov ecx, DWORD PTR _a$[esp-4]
inc ecx
lea eax, DWORD PTR [ecx+6]
sar eax, 4
lea eax, DWORD PTR [eax+eax*2]
lea eax, DWORD PTR [ecx+eax*2]
and eax, 15
ret 0
_rotate_0_9_457_2 ENDP
掛け算消えるんだね

_rotate_0_9_458 PROC NEAR
; 14 : int rotate_0_9_458(int a){return ++a%10;}
mov eax, DWORD PTR _a$[esp-4]
mov ecx, 10
inc eax
cdq
idiv ecx
mov eax, edx
ret 0
_rotate_0_9_458 ENDP
見るからに遅そうな

472:デフォルトの名無しさん
07/09/30 01:16:44
_rotate_0_9_460 PROC NEAR
; 15 : int rotate_0_9_460(int a){return a<9?a+1:0;}
mov eax, DWORD PTR _a$[esp-4]
cmp eax, 9
jge SHORT $L53312
inc eax
ret 0
$L53312:
xor eax, eax
ret 0
_rotate_0_9_460 ENDP
普通だね

_rotate_0_9_467 PROC NEAR ; COMDAT
mov eax, DWORD PTR _a$[esp-4]
mov eax, DWORD PTR _?t@?1??rotate_0_9_467@@9@9[eax*4]
ret 0
_rotate_0_9_467 ENDP
短いね
この短さがテーブル参照のオーバーヘッドを相殺してる？
けどaが10以上だったら脂肪

473:デフォルトの名無しさん
07/09/30 01:27:47
まあ表引きはキャッシュから外れた時にペナルティがあるから
平均的には>460がいいんだろうな。

474:デフォルトの名無しさん
07/09/30 02:05:05
>>473
確かに、別の環境だと逆転してたり。

#Celeron 430@2.4G XPSP2
rotate_0_9_457_1 1750 msec (i:2)
rotate_0_9_457_2 1359 msec (i:5)
rotate_0_9_458 2969 msec (i:5)
rotate_0_9_460 719 msec (i:5)
rotate_0_9_467 860 msec (i:5)

#Core2Duo 4300@3.2G XPSP2
rotate_0_9_457_1 1281 msec (i:2)
rotate_0_9_457_2 1000 msec (i:5)
rotate_0_9_458 2172 msec (i:5)
rotate_0_9_460 516 msec (i:5)
rotate_0_9_467 656 msec (i:5)

475:デフォルトの名無しさん
07/09/30 04:40:29
％は割り算があるから遅いってことか。0～9ではなく0～2^n-1の場合にかぎり使えばいいかな。
でも実際の仕事では0～99のローテートでも％で書いたりするなあ。

476:デフォルトの名無しさん
07/09/30 08:29:40
剰余は定数除算よりも更に遅い。

477:デフォルトの名無しさん
07/09/30 09:14:40
その剰余をビット演算でなんとか．．．

478:デフォルトの名無しさん
07/09/30 10:11:46
このスレの355から、剰余をビット演算でする方法が書かれているよ。

入力が必ず0～9なら
a=((a+7)&15)-6; 　// 0～8 が 1～9 9が-6

(aの符号拡張か　4bitの算術右シフト結果)のビット反転と and

479:457
07/09/30 23:43:50
ふぬぅ、やっぱ分岐しない上にテーブルも使わない奴は遅いな。

480:デフォルトの名無しさん
07/09/30 23:45:02
逆に考えて、分岐する上にテーブルも使う奴は・・・

すまん、逆に遅くなりそうだ。

481:デフォルトの名無しさん
07/10/01 16:44:48
modも内部的には分岐してるだろ。RISCならよくわかる。

482:デフォルトの名無しさん
07/10/01 17:41:59
え～(*o*) それは２のｎ乗の場合とそうでないので分けてるとか？

483:ヽ・´∀｀・,,）っ━━━━━━┓
07/10/04 02:56:19
剰余　＝　披除数－ (除数＊商)

一般的には商と剰余は同時に求めることが可能

484:デフォルトの名無しさん
07/10/21 17:07:33
age

485:デフォルトの名無しさん
07/10/21 18:36:55
剰余のビット演算への変換ならこのページにあるよ。
URLﾘﾝｸ(www.tensyo.com)

縛りを入れるともっと高速化出来そう…

486:デフォルトの名無しさん
07/10/23 00:23:05
ある変数の値が

2018か2019
4049か4050
であるか判別する方法は4回比較するしか
ないかな？

487:デフォルトの名無しさん
07/10/23 00:49:07
愚直な方法だけど比較２回には減らしてみた。
bool check(int value) {
const int mask = ~1;
if( (value & mask) == 2018 || ((value + 1) & mask) == 4050 ) return true;
return false;
}

488:デフォルトの名無しさん
07/10/23 01:56:04
テストしてないけど。
bool check(int value) {
const int mask = ~1;
if (((abs(value - 3034) + 1) & mask) == 1016) return true;
return false;
}

489:デフォルトの名無しさん
07/10/23 09:11:06
AND も加算も比較＝減算も、演算量は同じ、ってこと考えたら、どっちも減ってない。
比較４回に比べてリーダビリティは下がってる。

490:デフォルトの名無しさん
07/10/23 09:53:31
switch (value) {
case 2018: case 2019: case 4049: case 4050:
　　doit();
}

491:デフォルトの名無しさん
07/10/23 11:06:26
if (v == 2018 || v == 2019 || v == 4049 || v == 4050) return 1;
return 0;
0m48.123s
0m2.250s

const int mask = ~1;
if ((v & mask) == 2018 || ((v + 1) & mask) == 4050) return 1;
return 0;
0m53.281s
0m2.278s

const int mask = ~1;
if (((abs (v - 3034) + 1) & mask) == 1016) return 1;
return 0;
0m52.661s
0m2.167s

switch (v) {
case 2018: case 2019: case 4049: case 4050:
return 1;
}
return 0;
0m46.065s
0m2.087s

if (v < 2018 || (v > 2019 && (unsigned int) (v - 4049) > 1)) return 0;
return 1;
0m45.938s
0m2.086s

いろいろ測ってみた
コンパイラやマシンによって違うと思うけど

次ページ