981コメント261KB

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

レス数が950を超えています。1000を超えると書き込みができなくなります。

0001デフォルトの名無しさん

2006/09/16(土) 09:46:26

前スレ
ビット演算
http://pc8.2ch.net/test/read.cgi/tech/1123918075/

関連スレ
アセンブラ…　(゜□゜) ↑アッー！↓
http://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

0002デフォルトの名無しさん

2006/09/16(土) 09:47:52

　　　　/ノ 0ヽ
　　＿|＿＿_|＿　　下がってろウジ虫共！
　　ヽ|・∀・|ﾉ　　　　　訓練教官のようかんマン先任軍曹が2getだ！
　　　　|＿＿|
　　　　　|　|

>>1　貴様！俺のかんてんをどうするつもりだ！
>>3　あんこを入れる前と後に「サー」と言え！
>>4　ふざけるな！茶をだせ！茶っ葉落としたか！
>>5　貴様にはふやけたもなかをかき集めた値打ちしかない！
>>6　異人の手先の駄カステラめ！
>>7　まるでそびえ立つ葛だ！
>>8　栗を切り取って貴様の価値を絶ってやる！
>>9　お茶請けにもなれないゼリー風情が気取った事を言うな！
>>10-999　虎だ！虎になれ！虎屋のようかんを思い出せ！
>>1000　気に入った！家に来て俺を食っていいぞ！

0003デフォルトの名無しさん

2006/09/16(土) 09:48:26

　　　　∧
　　　 < | >　　　　　俺はグラットン持ちの通りすがりのナイトであって
　　　　|.|.|　　　　　　　　　　　　　　3getしたがどうやってブロントって証拠だよ！！
　　　　|.|.|
　　　　|.|.|
　　　 < | > 　　　　　おいィ？お前それで良>>1のか？　
　　　...| | |.　　　　　仏の顔を>>2度までという名セリフを知らないのかよ
　　　...| | |. 　　　　　暗黒が持つと逆に頭がおかしくなって>>4ぬ
　　　...| | |.　　　　　グラットンす>>5いですね
　　 .< .| .>　　　　　>>6駄にaguるなネットポリスに捕まりたいのか？
　/(.._..|..|..|.._..)ヽ　　それほどでも>>7い
　>.─＜＞─.<　　　このままでは俺の寿命がストレスでﾏｯ>>8なんだが・・
　ヾ￣ヾ .√ ")'　　　>>9枚で良い
　　　　.| .|　　　　　　俺の怒りが有頂>>10になった
　　　　.| .|
　　　　.| .|　　　　　　おれパンチングマシンで>>100とか普通に出すし
　　　 ) (
　　　　.▽

0004デフォルトの名無しさん

2006/09/16(土) 10:15:14

廃人向けビット演算の知識を扱うスレはここですか？

0005デフォルトの名無しさん

2006/09/16(土) 11:47:09

団子(◆DanGorION6)はWEBページからデータを自動収集して会話する人工無能なので
必要なコピペを引き出したらあとは放置しましょう。
待機モード中の自動応答に本気でレスすると、無駄にログが流れ読みにくくなりますし
他の利用者の妨げになります。

0006デフォルトの名無しさん

2006/09/16(土) 17:48:57

>>1
乙です

0007デフォルトの名無しさん

2006/09/16(土) 18:00:34

Java使っててもたまにお世話になるから侮れん。

0008デフォルトの名無しさん

2006/09/18(月) 08:19:25

　＊　　　　+　　　　巛ヽ
　　　　　　　　　　　　〒　!　　　+　　　　。　　　　　+　　　　。　　　　　＊　　　　。
　　　　　+　　　　。　 | 　|
　　　＊　　　　+　　 /　/　　　イヤッッホォォォオオォオウ！
　　　　　　 ∧＿∧ /　/
　　　　　　（´∀｀　/　/　+　　　　。　　　　　+　　　　。　　　＊　　　　。
　　　　　　,-　　　　　ｆ
　　　　　 / ュヘ　　　　| ＊　　　　+　　　　。　　　　　+　　　。　+
　　　　　〈＿｝）　　　|
　　　　　　　 /　　　　! +　　　　。　　　　　+　　　　+　　　　　＊
　　　　　　 ./　　,ヘ　 |　　　　　　このスレッドは１０００を超えました。
　ガタン　||| j　　/　|　 | |||　　　　　　　　次スレも…BITクオリティ！！
――――――――――――　　　　　　　 http://pc8.2ch.net/tech/

って1000取ろうとしたらすっかり忘れてた。

0009デフォルトの名無しさん

2006/09/18(月) 11:56:32

何はしゃいでるんだか。
こういう奴死んでくれないかな。

0010デフォルトの名無しさん

2006/09/19(火) 07:48:09

age

0011デフォルトの名無しさん

2006/09/21(木) 22:57:17

age

0012デフォルトの名無しさん

2006/09/22(金) 01:51:44

>>8
取れてるじゃん。

0013デフォルトの名無しさん

2006/09/22(金) 23:28:21

オセロで空白位置 m に打ったときに返るパターンを取得するプログラムで
分岐を使わないのができた

uint64 wh = white & 0x7e7e7e7e7e7e7e7e; // 横移動のための番人
uint64 rev = 0;
uint64 e1, e2, e3, e4, e5, e6; // 空白から続く白石列
uint64 b1, b2, b3, b4, b5, b6; // 黒石から続く白石列
e1 = (mask0 <<1) & wh;
e2 = (e1 << 1) & wh;
e3 = (e2 << 1) & wh;
e4 = (e3 << 1) & wh;
e5 = (e4 << 1) & wh;
e6 = (e5 << 1) & wh;
b1 = (black >> 1) & wh;
b2 = (b1 >> 1) & wh;
b3 = (b2 >> 1) & wh;
b4 = (b3 >> 1) & wh;
b5 = (b4 >> 1) & wh;
b6 = (b5 >> 1) & wh;
rev |=
e1 & b1 |
e1 & b2 | e2 & b1 |
e1 & b3 | e2 & b2 | e3 & b1 |
e1 & b4 | e2 & b3 | e3 & b2 | e4 & b1 |
e1 & b5 | e2 & b4 | e3 & b3 | e4 & b2 | e5 & b1 |
e1 & b6 | e2 & b5 | e3 & b4 | e4 & b3 | e5 & b2 | e6 & b1;

0014デフォルトの名無しさん

2006/09/22(金) 23:29:29

↑は右方向だけのコード。他の7方向についても同様

だけど、条件分岐を使って書いたコードよりかなり遅い
もっと高速化できないものか

0015・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6

2006/09/22(金) 23:46:53

分岐を排除すれば早くなるなんてのは200段くらいのキチガイパイプライン
でもない限りありえない。
2項選択くらいならconditional move使えば簡単に表現できる。

x86ならレジスタ数が少ない上に32ビットレジスタ2本でようやく1つの64ビット値だから
それだとロード・ストアが頻発して全然速くない。
へたに1マス1ビットに割り振るよりは1バイトに振ったほうが小回りが利く分速くなることもある。

0016デフォルトの名無しさん

2006/09/22(金) 23:50:43

最後の部分は
rev |=e1 & (b1 | b2 | b3 | b4 | b5 | b6) |
e2 & (b1 | b2 | b3 | b4 | b5) |
e3 & (b1 | b2 | b3 | b4) |
e4 & (b1 | b2 | b3) |
e5 & (b1 | b2) |
e6 & b1;
とすれば、論理演算の回数を４２から 26回に減る
さらに or の部分をまとめれば
rev |= e6 & b1;
rev |= e5 & (b1 |= b2);
rev |= e4 & (b1 |= b3);
rev |= e3 & (b1 |= b4);
rev |= e2 & (b1 |= b5);
rev |= e1 & (b1 | b6);
論理演算の回数は 17回

0017デフォルトの名無しさん

2006/09/23(土) 00:08:41

WORD単位の方が速いことも多いような。

0018デフォルトの名無しさん

2006/09/23(土) 00:13:59

そういうの考慮したベンチマークとかシミュレーションとか
AMD が出してたのがあるような気がするけどなんだっけ…

0019・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6

2006/09/23(土) 00:59:58

x86の演算は基本的に２オペランドベースで破壊的。
つまり
　　src1 = func(src1, src2)

src1の値を保存したい場合は待避が必要になる。
レジスタ間移動

0020・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6

2006/09/23(土) 01:05:29

失礼

レジスタ間移動だけでも整数の論理算術演算と同様にクロック数と
演算ユニットを使うし、ロード・ストアが絡むとさらに遅延が大きくなる。

x86でこの手の最適化をやる場合、テンポラリ変数をなるべく多用しない
（３２ビットで同時に３～４くらいに抑えるべき）のと、全部 &= や |= で
書いてみれば、吐き出される命令数が最低どのくらいになるかは
見当がつくと思う。

0021デフォルトの名無しさん

2006/09/23(土) 07:59:35

下記のように書き換えれば、使用変数が減る
uint64 wd = white & 0x007e7e7e7e7e7e00;//斜め移動のための番人
uint64 rev = 0;
uint64 e1, e2, e3, e4, e5, e6;//空白から続く白石列
uint64 b1;//黒石から続く白石列
e1 = (m << 9) & wd;
e2 = (e1 << 9) & wd;
e3 = (e2 << 9) & wd;
e4 = (e3 << 9) & wd;
e5 = (e4 << 9) & wd;
e6 = (e5 << 9) & wd;
rev |= e6 & (b1 = (black >> 9) & wd);
rev |= e5 & (b1 |= (b1 >> 9) & wd);
rev |= e4 & (b1 |= (b1 >> 9) & wd);
rev |= e3 & (b1 |= (b1 >> 9) & wd);
rev |= e2 & (b1 |= (b1 >> 9) & wd);
rev |= e1 & (b1 | (b1 >> 9) & wd);

0022デフォルトの名無しさん

2006/09/23(土) 08:01:25

e1～e6 は高々1ビットだけがセットされているので、
e6 = (m << 6*6) & wd;
とし、
rev |= e6 & (b1 = (black >> 9) & wd);
rev |= (e6>>=6) & (b1 |= (b1 >> 9) & wd);
としてもよさそうだが、一度にシフトすると番人を飛び越してしまうのでよろしくない

0023デフォルトの名無しさん

2006/09/27(水) 04:29:00

結局は子供の遊びだな

0024デフォルトの名無しさん

2006/09/27(水) 06:33:35

子供が遊びでこんなことをするとは恐ろしい時代になったんだな。

0025デフォルトの名無しさん

2006/09/27(水) 09:22:57

子供の遊びを大人がやっているだけだろ。

0026デフォルトの名無しさん

2006/09/27(水) 13:18:53

大人の遊びを子供がやる時代だから。

0027デフォルトの名無しさん

2006/09/27(水) 19:57:00

つかお前らも子供の頃MSXBASICからマシン語打ち込んだり
ニーモニック丸暗記して作ったプログラムに独自のチェックサムﾓﾄﾞｷつけたりして
紙に書いてセーブしてﾜｸﾜｸしてただろ。

大人はそんな無駄でアホな事まずやらねぇ

0028デフォルトの名無しさん

2006/09/27(水) 22:52:33

ビットボードによるオセロの話

A1, B1, ... H1 などの横一列の状態を一意の数字（インデックス）に変換し、
あらかじめ作成しておいたテーブルを引きたい
マスの状態は白黒空の3種類なので、空:0,黒：1,白２として 3倍しながら値を足していけば
インデックスを計算できる。

#define isB(p) ((black&p)!=0)
#define isW(p) ((white&p)!=0)
#define V(p) (isB(p) ? 1 : isW(p) ? 2 : 0)
#define INDEX8(p1, p2, p3, p4, p5, p6, p7, p8)\
(((((((V(p1)*3+V(p2))*3+V(p3))*3+V(p4))*3+V(p5))*3+V(p6))*3+V(p7))*3+V(p8))

INDEX8(A1, B1, C1, D1, E1, F1, G1, H1);

この処理をビット演算を使って、華麗に高速に行う方法はないのでしょうか？

0029デフォルトの名無しさん

2006/09/28(木) 07:42:57

1マスが2ビット（黒：01, 白：10, 空：00）で、8マス分の情報が下位16ビットに並んでいれば
分割統治法が使えそうだ

t = x & 0xcccc; x = (x & 0x3333) + (t >>= 1); x += t >>2;
t = x & 0xf0f0; x = (x & 0x0f0f) + (t >>= 3); x += t >> 4;
t = x & 0xff00; x = (x & 0x00ff) + (t >>= 7); x += t >> 8;

論理演算 6回、シフト 6回、加算 6回

3倍して足していく方法は、乗算 7回、加算7回なので、少し速そう

0030デフォルトの名無しさん

2006/09/28(木) 08:12:34

t = x & 0xcccccccc; x = (x & 0x33333333) + (t >>= 1); x += t >> 2;
t = x & 0xf0f0f0f0; x = (x & 0x0f0f0f0f) + (t >>= 3); x += t >> 4;
t = x & 0xff00ff00; x = (x & 0x00ff00ff) + (t >>= 7); x += t >> 8;
ix1 = x >> 16;
ix2 = x & 0xffff;

とすれば、2行分のインデックスを同時にもとめることができる。
64ビット変数を使えば4行分をまとめて計算できる。
それならかなり高速になりそう

しかし、ビットボードは白黒別々なので、それを2ビットごとにまとめなくてはいけない
その処理に時間がかかりそうだ

0031デフォルトの名無しさん

2006/09/28(木) 08:34:46

2ビットごとにまとめる処理は、いわゆるシャフルだ
下位32ビットについて、

b = black & 0xffffffff;
b = ((b & 0xffff0000) << 16) | (b & 0xffff);
b = ((b & 0xff00ff00ff00) << 8) | (b & 0xff00ff00ff);
b = ((b << 4) | b) & 0x0f0f0f0f0f0f0f0f;
b = ((b << 2) | b) & 0x3333333333333333;
b = ((b << 1) | b) & 0x5555555555555555;

で間に０を入れ、白も同様に処理し、

x = b | (w << 1);

とすれば、2ビットごとにまとめることができる。
あとは >>30 の処理を行えば、下4行分のインデックスが求まる。

0032デフォルトの名無しさん

2006/10/06(金) 12:00:35

>>29
間違ってない？

0033デフォルトの名無しさん

2006/10/06(金) 13:43:55

ビット演算だけで四則演算ってできるの？

0034デフォルトの名無しさん

2006/10/06(金) 22:17:36

それはギャグで言ってるのか

0035デフォルトの名無しさん

2006/10/08(日) 11:28:06

加算器って基本はビット演算だそ。

回路図や真理値表は以下のページにあるぞ。
http://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8

いわゆるCPUだとかマイクロ・プロセッサつーのは、
その奥深くに加算器に演算レジスタがあって、
ノイマン型にプログラム通りに計算をするためのものなんだから。

減算や負の数を扱うには「2の補数」
http://ja.wikipedia.org/wiki/2%E3%81%AE%E8%A3%9C%E6%95%B0
と言った捉え方で数を扱うのだ。

0036デフォルトの名無しさん

2006/10/08(日) 11:38:50

ビット演算だけで発明ってできるの？

0037デフォルトの名無しさん

2006/10/10(火) 23:41:36

ビット演算があれば、何でもできる。

0038デフォルトの名無しさん

2006/10/10(火) 23:46:16

ビット演算ができれば、僕にも彼女ができたりしますか？

0039デフォルトの名無しさん

2006/10/10(火) 23:49:48

当たり前。

0040デフォルトの名無しさん

2006/10/10(火) 23:51:57

or and not があれば全ての演算ができる？

0041デフォルトの名無しさん

2006/10/10(火) 23:57:28

NANDがあれば、何でもできる。

0042デフォルトの名無しさん

2006/10/10(火) 23:58:38

NORでもいいぞ

0043デフォルトの名無しさん

2006/10/11(水) 00:21:23

わかってないな

0044デフォルトの名無しさん

2006/10/11(水) 01:00:10

元気ががあれば、何でもできる。

0045デフォルトの名無しさん

2006/10/11(水) 01:01:30

行けば分かるさ

0046デフォルトの名無しさん

2006/10/11(水) 02:06:14

やっぱ、NANDとNORのハイブリットが良い？

0047デフォルトの名無しさん

2006/10/11(水) 06:57:09

Trががあれば、何でもできる。

0048デフォルトの名無しさん

2006/10/11(水) 13:16:09

Magic Algorithm
http://aggregate.org/MAGIC/

0049デフォルトの名無しさん

2006/10/11(水) 16:56:33

>>48
ひょっとしてradiumあたりで見た輩か？
>>1のサイトでとりあげられてる。
せめて>>1のサイトくらいみればよいのに・・・

0050デフォルトの名無しさん

2006/10/11(水) 23:15:53

C++やJavaだとどちらかというと保守性重視だから
性能改善要求出る前にビット演算使うと白い目で見られる。

0051デフォルトの名無しさん

2006/10/11(水) 23:18:57

>>50
例え処理が１行だけであっても、関数（インラインで良い）にしとけば文句でないはず。

0052デフォルトの名無しさん

2006/10/11(水) 23:26:39

>>51
勿論明瞭なコメント付きでな。

0053デフォルトの名無しさん

2006/10/11(水) 23:36:36

>>51
ついでに代替コードを書いておくとなお良い。

0054デフォルトの名無しさん

2006/10/13(金) 04:27:35

ゴリゴリのチューニングが求めらるような場面でもなければ、たいていはコンパイラの最適化だけで事足りるわけだが。

0055デフォルトの名無しさん

2006/10/13(金) 05:31:51

スクリプトでマスかいてろ

0056デフォルトの名無しさん

2006/10/13(金) 09:38:47

>>54
確かにそれで文句が出ないどころかメンテしやすければ褒められるべきところではあるが
多少の遊び心があってもそれはそれで許される。
>>51-53のようなことをしてあれば。
（代替コードのテストも必要なことは当然なので、プログラマの負担はアップするが）

0057デフォルトの名無しさん

2006/10/13(金) 13:48:49

ビット演算による最適化が必要で
パフォーマンス的に代替が効かないからこそ
そういうコードを書くわけだから
同等以上の速度が出た上に読みやすいコードを出せなければ
批難する事はできない。

もちろん意味もなくビット演算するアホの話は別として。

0058デフォルトの名無しさん

2006/10/13(金) 16:28:36

でも普通インラインアセンブラ使うよね。そういうビット演算だと。
上で出てるようなCでなんて書かないよ。

0059デフォルトの名無しさん

2006/10/13(金) 16:34:33

いや、俺はループアンローリングだとかプロセッサのスケジューリング管理
なんか考えたくないからC言語で書くけどね。
まぁ、どうしてもビット回転(rotate)が必要ならインラインアセンブラの
使用も検討するが。

0060デフォルトの名無しさん

2006/10/13(金) 16:41:08

インラインアセンブラはアセンブラとは違うよ

0061デフォルトの名無しさん

2006/10/13(金) 18:52:45

>>60
いや、当たり前の事実を主張されてもなぁ。
しかもなぜにこのタイミングで？わけわからん。

0062デフォルトの名無しさん

2006/10/13(金) 21:02:46

>>60
何が違うの？

0063デフォルトの名無しさん

2006/10/13(金) 21:26:25

ものほんのアセンブラならそもそも命令セットの数が違うみたいな？

0064デフォルトの名無しさん

2006/10/13(金) 23:34:07

なんつー理屈だ。

寧ろインラインアセンブラだとCコード部とのI/Fが簡単に書けるメリットはあるね。

0065デフォルトの名無しさん

2006/10/14(土) 00:47:40

ネイティブアセンブラ
　C言語との連携は関数呼び出しの形でのみによって実現される。
　殆どのメモリアクセスはシンボルではなくオフセット値での指定となるからめんどい。
　最適化の善し悪しはすべて自分の腕にかかっている。

インラインアセンブラ
　Cのソースに埋め込むことが出来るので、必要な箇所を個別に関数化する必要がない。
　関数内の局所変数にシンボリックにアクセスできる。
　一部のコンパイラはインラインアセンブラで書いた箇所も勝手に最適化してくれやがる。

0066デフォルトの名無しさん

2006/10/14(土) 00:56:32

スレ違いだ。他所でやれ。

0067デフォルトの名無しさん

2006/10/17(火) 13:52:46

論理演算部分をインラインアセンブラ化するのに、
どうして「プロセッサのスケジューリング管理」なんて話が出てくるのか誰か教えて！

0068デフォルトの名無しさん

2006/10/17(火) 16:26:53

「プロセッサのスケジューリング管理」の意味はわかっているか？

0069デフォルトの名無しさん

2006/10/17(火) 17:04:37

大方タイムスライスと勘違いしているんだろうけど。

0070デフォルトの名無しさん

2006/10/17(火) 17:27:16

>>67
パイプラインでな、処理を円滑に進めるためには、命令の実行順序を適切に
並び替える必要があるんだ。命令実行順序の決定をスケジューリングという。
命令実行スケジューリングはふつうコンパイラが最適化の一環として施すが
インラインアセンブラで記述した部分はそのままの順序で出力されて最適化
されないことが多い。

0071デフォルトの名無しさん

2006/10/26(木) 23:04:23

！

0072デフォルトの名無しさん

2006/10/30(月) 22:09:37

あげ

0073デフォルトの名無しさん

2006/10/30(月) 22:39:25

テンプレにある
＞ハッカーのたのしみ
は、アマゾンで評価が高いみたいですが
本当に読んで面白い本なんですか？

0074デフォルトの名無しさん

2006/10/30(月) 22:47:16

>>73
それはお前がビット演算を楽しめるかどうかによる。

0075デフォルトの名無しさん

2006/10/31(火) 03:09:00

>>73
もしもあなたが書き溜めたソースコードを持っているのなら…

0076デフォルトの名無しさん

2006/11/15(水) 19:13:21

ビット演算で絶対値を求めることってできますかね？
条件分岐をしないで絶対値を求めたいのですが…

0077デフォルトの名無しさん

2006/11/15(水) 20:26:02

>>76
このへん見てみたら？
http://www.thescripts.com/forum/thread212935.html

0078デフォルトの名無しさん

2006/11/15(水) 21:53:55

int y=x>>31;
return (x^y)-y;
か。
今ならcmovのほうが速いだろうけど

0079デフォルトの名無しさん

2006/11/15(水) 22:56:58

ふーむ…
とりあえずリンク先を参考に試してみようと思います
ありがとうございました

0080デフォルトの名無しさん

2006/11/26(日) 15:29:11

age

0081デフォルトの名無しさん

2006/12/02(土) 22:52:42

age

0082デフォルトの名無しさん

2006/12/03(日) 07:55:42

とにかく徹底的にｉｆ文使いたくないんだけど、
根本的に排除する方法ってないんですか？
こういう場合はできるよってのがあったらそれも知りたいです。
もうビット演算のこと以外考えたくないんです。

0083デフォルトの名無しさん

2006/12/03(日) 08:40:06

>>82
論理回路にｉｆ演算器はない。

0084デフォルトの名無しさん

2006/12/03(日) 08:40:31

if(a){
　x;
} else {
　y;
}

⇒

switch(a){
default:
　x;
　break;
case 0:
　y;
}

0085デフォルトの名無しさん

2006/12/03(日) 08:50:26

じゃあ僕は条件分岐と一生付き合わなきゃいけないんですか？
一生、縁が切れないんですか？？
もう勘弁しいてほしいんです。
ソース読みにくいのってみんなｉｆ文の所為じゃないですか。
この絶望のまま生きていたくない。

並列計算がうまくいかないのだってきっと条件分岐のせいですよ。
諸悪の根源と思っていますよ、もう。

ところで、論理シフトとかってあれは論理演算が関係してるんですか？

0086デフォルトの名無しさん

2006/12/03(日) 09:38:32

if(a>b){
　x=c;
} else {
　x=d;
}

x=(a>b)*c;
x+=!(a>b)*d;

こんな感じかな？
ビット演算じゃ無いけど

0087デフォルトの名無しさん

2006/12/03(日) 10:20:41

if(a){
　x;
} else {
　y;
}

⇒

n_if(a){
　x && a || y && !a;
}

0088デフォルトの名無しさん

2006/12/04(月) 17:34:01

平凡にジャンプテーブル
void f();
void g();
int hoge;

  before:
if (hoge != 0)
  f();
else
  g();

  after:
typedef (*func_t)();
func_t table[] = {f, g};
table[hoge != 0]();

0089・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6

2006/12/04(月) 22:59:51

関数コールのペナルティ＞＞＞分岐予測ミスのペナルティ

d = a ? b : c;

とかでも使えば？組み込みのCMOV命令に展開してくれたりするし
SIMD系の命令セットは比較命令はマスク生成のことが多い

0090デフォルトの名無しさん

2006/12/04(月) 23:03:57

P4だと、テーブル参照方式はペナルティが信じられんほど凄い。
命令20ぐらいをズラスラ書いたのより、テーブル参照1つの方が遅かったりする。

0091デフォルトの名無しさん

2006/12/07(木) 00:04:36

最近それ経験した。
switchで振り分けた方が遥かに速かったわ。恐るべし分岐予測。

0092・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6

2006/12/07(木) 00:39:10

>>82はPS3かなんかの開発やらされてるゲームプログラマなんじゃね？

009382

2006/12/11(月) 04:57:32

もうジャンプするのも嫌になりました。
ｉｆ文なしのジャンプなしで何とかならないでしょうか？？

0094デフォルトの名無しさん

2006/12/11(月) 18:38:36

てきとーに制限つけてその条件内で考えさせたいだけでしょ。

0095デフォルトの名無しさん

2006/12/18(月) 22:14:18

age

0096デフォルトの名無しさん

2006/12/25(月) 20:04:45

sub a, b
adc pc, a

0097デフォルトの名無しさん

2006/12/30(土) 23:15:58

あげ

0098 【大吉】

2007/01/01(月) 00:23:58

あけまして、おめでとうごｚぁいます

0099デフォルトの名無しさん

2007/01/01(月) 13:31:16

要は皆さんパズル好きだと

0100デフォルトの名無しさん

2007/01/03(水) 13:42:06

プログラミング自体が、言語変わってもパーツの組合せのパズルに過ぎない訳で。

0101デフォルトの名無しさん

2007/01/03(水) 19:31:35

>>82
>根本的に排除する方法ってないんですか？
>こういう場合はできるよってのがあったらそれも知りたいです。

ビット演算以外の仕事は「引き受けない」

0102デフォルトの名無しさん

2007/01/03(水) 23:21:49

>82
まずプロセッサから設計した方がいいんじゃないか

0103デフォルトの名無しさん

2007/01/04(木) 00:46:05

>>93
cmp+jeの組み合わせがいやならsub+jneでどうだろうか。

0104デフォルトの名無しさん

2007/01/06(土) 15:01:25

Cです
int i;として
iが0以外なら1を、iが0なら0を返すビット演算は
i!=0以上にコンパクトにできるのでしょうか？
n = i!=0;と括弧つけてもやや読みづらいので。
(bool)iならば可読的なので喜んで使いたいのですが、Cなので残念ながら…

0105デフォルトの名無しさん

2007/01/06(土) 15:03:57

!!i
なんてどう？

0106デフォルトの名無しさん

2007/01/06(土) 21:00:27

typedef enum{false, true} bool;

(bool)i

0107デフォルトの名無しさん

2007/01/06(土) 22:58:09

問題は、Cではenum型にキャストした値がenum値に制限されるかどうかだね。

0108・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6

2007/01/06(土) 23:02:40

めんどくさい
#define TO_BOOL(x) ((x) != 0)

0109デフォルトの名無しさん

2007/01/06(土) 23:04:45

阿呆なマクロを使うくらいなら>105でいいじゃん。

0110デフォルトの名無しさん

2007/01/06(土) 23:07:38

>>108
C、C++の最適化について語るスレ
http://pc10.2ch.net/test/read.cgi/tech/1084676298/

団子ちゃん、↑こっちのスレの結果はどうなったの？
やっぱり、団子ちゃんが適当なこと吹いてただけなの？

0111デフォルトの名無しさん

2007/01/07(日) 07:00:18

っつーかどうしても1にしたい状況ってそんなないだろ
0/!0で充分だから

0112デフォルトの名無しさん

2007/01/07(日) 22:11:55

ビット演算でも高速化でもないな。

0113デフォルトの名無しさん

2007/01/14(日) 00:16:55

#define BITTOENNZANN(dayo) ((dayo)!=0)

これでビット演算だお^ω^

0114デフォルトの名無しさん

2007/01/18(木) 00:08:57

>>33
加算器ってこんな感じじゃない？(ちょっと冗長かも)

int ADD(int x, int y, int c) {
return (x | y | c) ?
(((x & 1) ^ (y & 1) ^ (c & 1))
| (ADD(x >> 1, y >> 1,
(( !(x & 1) & (y & 1) & (c & 1))
| ( (x & 1) & !(y & 1) & (c & 1))
| ( (x & 1) & (y & 1) & !(c & 1))
| ( (x & 1) & (y & 1) & (c & 1)))) << 1)) : 0;
}

誰か減算器↓

0115デフォルトの名無しさん

2007/01/18(木) 00:48:41

int ADD_(int x,int y){return x?ADD_((x&y)<<1,x^y):y;}
int ADD(int x,int y,int c){return ADD_((x&y)<<1|c,x^y);}
int SUB(int x,int y,int c){return ADD(x,~y,c^1);}

0116デフォルトの名無しさん

2007/01/18(木) 16:58:05

>>109
! がオーバーロードされてたら、二回も呼ばれることになるぜ。

0117デフォルトの名無しさん

2007/01/19(金) 01:20:26

オーバーロードまで考慮したら ! 二回より != の方が遅いことも
十分ありえるけどな。

0118デフォルトの名無しさん

2007/01/19(金) 14:36:23

64bitのビットを数えるのは外出？

0119デフォルトの名無しさん

2007/01/19(金) 18:41:42

>>118
ビットを数えるってのがよくあるpop関数のことなら死ぬほど既出。

0120デフォルトの名無しさん

2007/01/23(火) 07:38:25

あげ

0121デフォルトの名無しさん

2007/01/23(火) 10:19:53

レス４は絶対ここの住民だろ笑
http://pc10.2ch.net/test/read.cgi/tech/1169104637/l50

0122デフォルトの名無しさん

2007/01/26(金) 23:52:21

>>121
こいつのせいでビット操作のスレになってるじゃないか

0123デフォルトの名無しさん

2007/01/29(月) 12:22:02

ビット演算でbranch freeなmagic incrementは可能かね？

0124デフォルトの名無しさん

2007/02/12(月) 18:20:58

Bit Twiddling Hacks
ttp://graphics.stanford.edu/~seander/bithacks.html
こんなサイトが（英語だけど）
テンプレに入れる？

0125デフォルトの名無しさん

2007/02/12(月) 21:33:10

入れるのはいいけど、それまで続くんか?

0126デフォルトの名無しさん

2007/02/12(月) 22:46:32

コンパイル時には>>124をテンプレとしてオーバーライドします。

0127デフォルトの名無しさん

2007/02/13(火) 07:43:07

もうこのスレも息切れみたいだね。

0128デフォルトの名無しさん

2007/02/13(火) 23:14:23

だいたいビット演算ごときでときめいちゃうのは厨房までだろw
煽りぬきで

0129デフォルトの名無しさん

2007/02/13(火) 23:51:38

ていうか、パズルみたいなもんだろ。

さすがに、ネタ切れにて閉店でいいと思うよ。

0130デフォルトの名無しさん

2007/02/15(木) 15:02:08

よほど要求速度や省メモリがシビアな環境でない限りは妙な小細工はたいして必要ないもんね

0131デフォルトの名無しさん

2007/02/15(木) 15:47:08

int i = 20070215;

で、この i からそれぞれ 2007, 2, 15 って数字が欲しいんだけど
誰かカッコ良くビット演算使ってやってください。

0132デフォルトの名無しさん

2007/02/15(木) 15:50:34

>>131
実質的には除数固定で割り算を行うのと同じだから
割り算の話になるな。

0133デフォルトの名無しさん

2007/02/15(木) 16:48:06

0x20070215

0134デフォルトの名無しさん

2007/02/15(木) 16:53:01

>>131-133
それすごくもったいなくないか

たしか
日：1-31 (5bit)
月：1-12 (4bit)
年：00-99 (7bit)

で 16bit っつー表記があったな
FDとかHDのタイムスタンプとか

今なら年だけ
0000-9999 (14bit)
でも 23bit で余裕な訳だが

0135デフォルトの名無しさん

2007/02/15(木) 17:03:23

>>134
そんなところでビットをケチったってしょうがねぇべさ。
そのフォーマット(MS-DOSのFATだな)はタイムスタンプが2秒単位でしか記録できないしね。
#hour:5, minute:6, second:5

0136デフォルトの名無しさん

2007/02/16(金) 03:33:47

ねえ偉い人
１０進数を３進数に変換するコードはJAVAでどう書きますか？

0137デフォルトの名無しさん

2007/02/16(金) 03:46:47

↑バカ

0138デフォルトの名無しさん

2007/02/16(金) 14:24:00

イマイチビット演算はよくわからん

0139デフォルトの名無しさん

2007/02/16(金) 15:18:45

ビット演算してると脳汁が出る

大抵は無意味だけど
オナニーとしてはﾅｶﾅｶそそる

0140デフォルトの名無しさん

2007/02/16(金) 15:28:21

ビット演算って1や0にするだけじゃん。

0141デフォルトの名無しさん

2007/02/16(金) 15:35:59

だが、それがいい。

0142デフォルトの名無しさん

2007/02/16(金) 15:55:53

3|17 2
3| 5 2
　 1

10進数:17 -> 3進数:122

10進数から3進数への変換て、これであってる？

0143デフォルトの名無しさん

2007/02/16(金) 15:59:57

なんかboost::randomの使い方が良く分からないので
extern boost::mt19937 brand;
inline const float&n_rand(){
static float x;
*((unsigned int*)&x)=(brand()&0x7FFFFF)|0x3F000000;
return x;
}
とかやってる俺はkusobaka

0144デフォルトの名無しさん

2007/02/16(金) 20:57:54

うわっバカだ

staticいらないだろ。

0145デフォルトの名無しさん

2007/02/16(金) 23:56:47

bitマスクとかメンドクサイから言語レベルでbitの配列みたいに扱える
演算子があれば良いんだけどな。
STLやboostを使っても型変換が必要だし。

0146デフォルトの名無しさん

2007/02/16(金) 23:58:08

ビットフィールド？

0147デフォルトの名無しさん

2007/02/17(土) 00:00:30

static を除去するなら、戻り値は const float & ではなく float にすべきでもある。
ところで、乱数の範囲はそれでいいのか？
２進表現で0x3f800000 から 0x3fffffff にして、そこから 1.0f を引くと [0..1) になって使いやすいと思うが。

0148デフォルトの名無しさん

2007/02/17(土) 01:31:32

floatの表現がIEEEに合致するってのは保証されてるんだっけ？

0149デフォルトの名無しさん

2007/02/17(土) 01:54:26

うんにゃ、されてない

0150デフォルトの名無しさん

2007/02/17(土) 08:36:23

だが、それがいい

0151デフォルトの名無しさん

2007/02/18(日) 21:02:06

32bitのエンディアンの変換てどうすればいい？

0152150

2007/02/18(日) 21:13:28

ごめん、よく考えたら大したことなかった。
これでOKだ。
x = ( ( x >> 8 ) & 0x00ff00ff ) | ( ( x << 8 ) & 0xff00ff00 );
x = ( ( x >> 16 ) & 0x0000ffff ) | ( ( x << 16 ) & 0xffff0000 );

0153デフォルトの名無しさん

2007/02/19(月) 09:11:59

単に
x = (x & 0x000000ff) << 24 | (x & 0x0000ff00) << 8
| (x & 0x00ff0000) >> 8 | (x & 0xff000000) >> 24;
と書いては何かまずいの？

152の方法だと1行目で算出したxを2行目で使っているので
1行目の処理と2行目の処理の並列性が無いし、マスク用の
定数が4バイトの2つ、3バイトの1つ、2バイトの1つで、
どのCPUを想定しているのかは知らないけど、普通は
上の方法のマスク定数より長いコードになるのでは。

24回のshiftが16回のshiftより時間がかかる状況なら
上の方法は好ましくないし、エンディアン変換のビット長が
64bitなら152の方法のほうが良いように思うが。

0154デフォルトの名無しさん

2007/02/19(月) 18:34:24

普通に共用体でやった方がエレガントで早いと思いますが。。

0155デフォルトの名無しさん

2007/02/19(月) 21:49:23

正直これでいいや。
ttp://msdn2.microsoft.com/ja-jp/library/a3140177(VS.80).aspx

0156デフォルトの名無しさん

2007/02/20(火) 21:52:40

>>155
?

0157デフォルトの名無しさん

2007/03/01(木) 22:52:20

あげ

0158デフォルトの名無しさん

2007/03/21(水) 06:17:18

任意のビット数のシフトやローテートてなんで１クロックで実行できねーの？
連続した場合ね。

0159デフォルトの名無しさん

2007/03/22(木) 00:34:10

1024bitとか？

0160デフォルトの名無しさん

2007/03/22(木) 08:22:35

そもそも1クロックで実行っていつの時代のどのCPUの話だよ
30年前の8bit時代から頭の中進歩してないオジサマ丸出しだねw

しかも昔の8bitマイコンだって命令サイクルと実クロックは別物だしね

0161デフォルトの名無しさん

2007/03/22(木) 21:47:22

なんか言いたいんだろうけど、何を言いたいのかさっぱりわからん。

知ったか厨の典型だな。(w

0162デフォルトの名無しさん

2007/04/07(土) 02:22:12

あげ

0163デフォルトの名無しさん

2007/04/29(日) 08:20:14

0164デフォルトの名無しさん

2007/04/29(日) 10:38:15

1Bit CPUの可能性について語れないのは素人。

0165デフォルトの名無しさん

2007/04/29(日) 10:44:47

cmos 4000 シリーズの事か？

0166デフォルトの名無しさん

2007/04/29(日) 10:52:16

MC14500　か

0167デフォルトの名無しさん

2007/04/29(日) 12:29:58

コネクションマシンか？

0168デフォルトの名無しさん

2007/04/29(日) 18:46:24

バイトの縛りがうざいんだよ

0169デフォルトの名無しさん

2007/04/30(月) 02:15:38

22時以降はダメとか?

0170デフォルトの名無しさん

2007/04/30(月) 07:39:02

ざぶんとん

0171デフォルトの名無しさん

2007/05/03(木) 20:17:24

>どっちかのbitが立ってることを確認するために
>if(hoge & 0x000000C0)
>みたいな書き方出来ると思うのですが
>両方のbitが立ってることを確認したければ
>if(hoge & 0x000000C0 == 0x000000C0)
>って書くしか方法ないですか？

以下から正しいものを選べ

1) if(hoge & 0x000000C0 & 0x000000C0)
2) if((hoge & 0x000000C0) & 0x000000C0)
3) if(!((hoge & 0x000000C0) ^ 0x000000C0))
4) if((hoge & 0x00000080) && (hoge & 0x00000040))
5) if(~(hoge | ~0x000000C0))
6) if(~(~hoge | ~0x000000C0))

0172デフォルトの名無しさん

2007/05/03(木) 20:20:41

(hoge & 0x000000C0) == 0x000000C0 が一番速いだろう。

0173デフォルトの名無しさん

2007/05/03(木) 20:30:47

#include <stdio.h>

#define MASK 0x0000C0C0

int bittesta(int hoge)
{
if((hoge & MASK) == MASK){
return 1;
}else{
return 0;
}
}

int bittestb(int hoge)
{
if(!((hoge & MASK) ^ MASK)){
return 1;
}else{
return 0;
}
}

int main(int ac, char **av)
{
int hoge = 1234;
bittesta(hoge);
bittestb(hoge);
return 0;
}

0174デフォルトの名無しさん

2007/05/03(木) 20:31:55

_bittesta:
pushl %ebp
movl %esp, %ebp
subl $4, %esp
movl 8(%ebp), %eax
andl $49344, %eax
cmpl $49344, %eax
jne L10
movl $1, -4(%ebp)
jmp L9
L10:
movl $0, -4(%ebp)
L9:
movl -4(%ebp), %eax
leave
ret
_bittestb:
pushl %ebp
movl %esp, %ebp
subl $4, %esp
movl 8(%ebp), %eax
andl $49344, %eax
cmpl $49344, %eax
jne L13
movl $1, -4(%ebp)
jmp L12
L13:
movl $0, -4(%ebp)
L12:
movl -4(%ebp), %eax
leave
ret

0175デフォルトの名無しさん

2007/05/03(木) 20:34:17

>>172 が正解なんだけど
いまどきのコンパイラは
>>171 (3) で書いても
最適化されて >>172 になってるんだね

0176デフォルトの名無しさん

2007/05/03(木) 22:06:56

ど素人です。質問があります。

例えば1か0が格納される変数(Aと仮定)のスイッチ切り替えの場合

【例①】
if(A == 1)
{
A = 0;
}
else
{
A = 1;
}

【例②】
A = A ^ (0 + 1);

この場合早いのはやはり例②なのでしょうか？

0177デフォルトの名無しさん

2007/05/03(木) 22:13:48

A ^= 1;

が速い。まあ、例２と同じだあな。

0178デフォルトの名無しさん

2007/05/03(木) 22:18:35

>>177
有難うございました。

0179デフォルトの名無しさん

2007/05/03(木) 22:24:42

SUBR #n 　　　Acc = n-Acc を持ってるCPUだと
A　=　1-A　

のが速かったりするぞ

0180デフォルトの名無しさん

2007/05/04(金) 00:48:43

>>177,179
いや、今回は1と0で設定されてるけどほんとは3と5かもしれないだろ
そういう場合ってやっぱA ^= 1;とかA = 1-Aより

A ^= (3 + 5);のほうが正解なんじゃないか？

1と0ならA = 1-Aとかでもいいんだけどな

0181・∀・）っ-○◎●

2007/05/04(金) 00:52:14

A ^= 8;
？？？？？？？？？？？？？？？？？？？？？？？？？？？？

Aには1か0が格納されるって最初の条件で確定してるんだが

0182180

2007/05/04(金) 00:53:56

>>181
汎用性を高めるって意味だよ

0183・∀・）っ-○◎●

2007/05/04(金) 00:55:14

いや8はおかしいだろ常識的に考えて

0184180

2007/05/04(金) 00:55:36

A変数に1か0だけの設定なら

A ^= 1;でいいと思うが

A変数に3か5が入ってる設定だと

A ^= 5;じゃダメだろ？

だったらどちらにでも応用できる

A ^= (1 + 0);
A ^= (5 + 3);

がいいんじゃないかって話をしたかっただけだ。

0185・∀・）っ-○◎●

2007/05/04(金) 00:56:41

8じゃ最下位ビットはトグルできません＞＜

0186180

2007/05/04(金) 00:59:14

じゃあ7だこの野郎

0187・∀・）っ-○◎●

2007/05/04(金) 00:59:43

ちなみに俺の回答は
A = ~A;

0188デフォルトの名無しさん

2007/05/04(金) 01:01:02

工ｴｴｪｪ(´д`)ｪｪｴｴ工

0189180

2007/05/04(金) 01:01:45

俺は今赤面しながら画面に張り付いてるｗｗｗｗｗｗｗｗｗｗ
確かに8じゃ無理だったｗｗｗｗｗｗｗｗｗ

0190・∀・）っ-○◎●

2007/05/04(金) 01:24:45

>>187だと「1」にならないね。
仮に全ビット使う場合の話。
信号制御用の1ビットレジスタをこれで操作してたような。

0か1かならこっちのほうが素直か
A = !A;

0191デフォルトの名無しさん

2007/05/04(金) 01:59:07

3 と 5 のトグルなら A ^= 6; だな。
要するに A ^= (3 ^ 5);

0192デフォルトの名無しさん

2007/05/04(金) 08:32:25

拡張して　0,1,2 のトグル a=(a+1) % 3 とか 0～9 での循環a=(a+1) % 10とかになると途端に難しくなるな

0193デフォルトの名無しさん

2007/05/04(金) 08:50:20

WORD wに0x0001が含まれていて0x0010が含まれてない、の結果をBOOL bに納める式は
どう書くと一番短いですか？

0194デフォルトの名無しさん

2007/05/04(金) 08:52:03

b = (w & 0x0011) == 0x0001;

0195デフォルトの名無しさん

2007/05/04(金) 08:59:54

if ((w && 0x0001) == 0x0001)
{
if ((w && 0x0010) != 0x0010)
{
b = TRUE;
}
else
{
b = FALSE;
}
}

0196デフォルトの名無しさん

2007/05/04(金) 09:05:23

>>194
ありがとん

0197デフォルトの名無しさん

2007/05/04(金) 09:17:53

a:= a +1;
a:= (a+ (a shr 2) ) and 3;

これだと 1,2,3の循環になるな

0198デフォルトの名無しさん

2007/05/04(金) 12:09:44

A ^= (3 ^ 5);

0199デフォルトの名無しさん

2007/05/04(金) 12:19:48

1001
1000
0000
0001
0011
0010
0110
0100
0101
0111

0200デフォルトの名無しさん

2007/05/04(金) 12:21:58

　　　　　　　ヾ　 /　　　　＜仮面ﾗｲﾀﾞｰ555が＞
　　　　　　,. -ﾔ'''ｶｰ､　　　/Y⌒Y⌒Y⌒Y⌒Yヾ
ー―ｧ　　/r⌒|:::|⌒ヾ
　 _ノ　オ{（　　|0|　　）} オｵｵォォｫｫ！！！！！
　　　　__,ヽ,ヾ,_|V|,_ノ､/ ,r-,,=
　　　,゛＝=ゝ_ＶiＶ_ノ~i/　〃 `ー―-､
　　 / 　/⌒`//´⌒c/＾＾＾ )））)))))））
,,―ｲ　 {ｰ''"~{ {~゛`ー`/'`'~/ー--―'
））　　,./ゝ＿/∧ゝ＿ノ　　ﾉ
ー''"　　｜ﾛ　　ﾛ　　　　｜
人,_,人,_,人,_,人,_,人,_,
＜適当な番号をゲット!!＞

0201デフォルトの名無しさん

2007/05/04(金) 15:08:21

あまり適当な番号には見えない件について

0202デフォルトの名無しさん

2007/05/04(金) 16:12:03

0xC8

0203デフォルトの名無しさん

2007/05/04(金) 16:43:42

丁度256円になります。

0204デフォルトの名無しさん

2007/05/04(金) 16:47:10

ポイントはお付きしますか？

0205デフォルトの名無しさん

2007/05/04(金) 16:50:33

いいえ、彼はペンです。

0206デフォルトの名無しさん

2007/05/05(土) 02:12:41

char v;
if(v){ ..... }

vのビット列が [10000000] と [00000001]
ではやっぱり前者の方が早いんだろうか

0207デフォルトの名無しさん

2007/05/05(土) 02:21:08

最適化や前後のループや分岐予測によるだろ…常識的に考えて…

0208デフォルトの名無しさん

2007/05/05(土) 02:37:55

嫌な答え方だな

0209デフォルトの名無しさん

2007/05/05(土) 03:18:03

感じないわ。

0210デフォルトの名無しさん

2007/05/05(土) 03:39:36

痛くないわ。

0211デフォルトの名無しさん

2007/05/05(土) 11:01:09

五寸釘はイヤだろ・・・・常考

0212デフォルトの名無しさん

2007/05/05(土) 11:21:15

ごっすんごっすん五寸釘ー

0213デフォルトの名無しさん

2007/05/05(土) 12:16:52

そっちかよクソ

0214デフォルトの名無しさん

2007/05/06(日) 17:55:55

あいーん

0215デフォルトの名無しさん

2007/05/14(月) 21:23:54

効率的では無いけど少々トリッキーなJavaのコード。数列の解説は面倒なので略。

float[] p = {
0.000f, 0.000f, 1.000f, 5.373f, 0.000f, 0.998f, 4.989f, 0.000f, 1.075f, 5.000f, 0.000f, 0.000f,
0.000f, 5.373f, 0.998f, 4.865f, 4.865f, 0.951f, 4.970f, 2.370f, 1.160f, 5.000f, 1.326f, 0.000f,
0.000f, 4.989f, 1.075f, 2.370f, 4.970f, 1.160f, 3.700f, 3.700f, 0.179f, 4.473f, 2.598f, 0.000f,
0.000f, 5.000f, 0.000f, 1.326f, 5.000f, 0.000f, 2.598f, 4.473f, 0.000f, 3.536f, 3.536f, 0.000f,
};
float[] q = new float[384];
int i,j,k;
for(i=0;i<8;i++) {
k = (((i>>>2)^(i>>>1)^i)&1)*12;
for(j=0;j<16;j++) {
q[i*48+j*3+0] = ((i&1)==0)?p[(j^k)*3+0]:-p[(j^k)*3+0];
q[i*48+j*3+1] = ((i&2)==0)?p[(j^k)*3+1]:-p[(j^k)*3+1];
q[i*48+j*3+2] = ((i&4)==0)?p[(j^k)*3+2]:-p[(j^k)*3+2];
}}
for(i=0;i<32;i++) {
for(j=0;j<12;j++) { System.out.printf("%+6.3ff,",q[i*12+j]); }
System.out.print("\n");
}

0216215の出力結果(1/2)

2007/05/14(月) 21:26:12

+0.000f,+0.000f,+1.000f,+5.373f,+0.000f,+0.998f,+4.989f,+0.000f,+1.075f,+5.000f,+0.000f,+0.000f,
+0.000f,+5.373f,+0.998f,+4.865f,+4.865f,+0.951f,+4.970f,+2.370f,+1.160f,+5.000f,+1.326f,+0.000f,
+0.000f,+4.989f,+1.075f,+2.370f,+4.970f,+1.160f,+3.700f,+3.700f,+0.179f,+4.473f,+2.598f,+0.000f,
+0.000f,+5.000f,+0.000f,+1.326f,+5.000f,+0.000f,+2.598f,+4.473f,+0.000f,+3.536f,+3.536f,+0.000f,
-0.000f,+5.000f,+0.000f,-1.326f,+5.000f,+0.000f,-2.598f,+4.473f,+0.000f,-3.536f,+3.536f,+0.000f,
-0.000f,+4.989f,+1.075f,-2.370f,+4.970f,+1.160f,-3.700f,+3.700f,+0.179f,-4.473f,+2.598f,+0.000f,
-0.000f,+5.373f,+0.998f,-4.865f,+4.865f,+0.951f,-4.970f,+2.370f,+1.160f,-5.000f,+1.326f,+0.000f,
-0.000f,+0.000f,+1.000f,-5.373f,+0.000f,+0.998f,-4.989f,+0.000f,+1.075f,-5.000f,+0.000f,+0.000f,
+0.000f,-5.000f,+0.000f,+1.326f,-5.000f,+0.000f,+2.598f,-4.473f,+0.000f,+3.536f,-3.536f,+0.000f,
+0.000f,-4.989f,+1.075f,+2.370f,-4.970f,+1.160f,+3.700f,-3.700f,+0.179f,+4.473f,-2.598f,+0.000f,
+0.000f,-5.373f,+0.998f,+4.865f,-4.865f,+0.951f,+4.970f,-2.370f,+1.160f,+5.000f,-1.326f,+0.000f,
+0.000f,-0.000f,+1.000f,+5.373f,-0.000f,+0.998f,+4.989f,-0.000f,+1.075f,+5.000f,-0.000f,+0.000f,
-0.000f,-0.000f,+1.000f,-5.373f,-0.000f,+0.998f,-4.989f,-0.000f,+1.075f,-5.000f,-0.000f,+0.000f,
-0.000f,-5.373f,+0.998f,-4.865f,-4.865f,+0.951f,-4.970f,-2.370f,+1.160f,-5.000f,-1.326f,+0.000f,
-0.000f,-4.989f,+1.075f,-2.370f,-4.970f,+1.160f,-3.700f,-3.700f,+0.179f,-4.473f,-2.598f,+0.000f,
-0.000f,-5.000f,+0.000f,-1.326f,-5.000f,+0.000f,-2.598f,-4.473f,+0.000f,-3.536f,-3.536f,+0.000f,

0217215の出力結果(2/2)

2007/05/14(月) 21:27:16

+0.000f,+5.000f,-0.000f,+1.326f,+5.000f,-0.000f,+2.598f,+4.473f,-0.000f,+3.536f,+3.536f,-0.000f,
+0.000f,+4.989f,-1.075f,+2.370f,+4.970f,-1.160f,+3.700f,+3.700f,-0.179f,+4.473f,+2.598f,-0.000f,
+0.000f,+5.373f,-0.998f,+4.865f,+4.865f,-0.951f,+4.970f,+2.370f,-1.160f,+5.000f,+1.326f,-0.000f,
+0.000f,+0.000f,-1.000f,+5.373f,+0.000f,-0.998f,+4.989f,+0.000f,-1.075f,+5.000f,+0.000f,-0.000f,
-0.000f,+0.000f,-1.000f,-5.373f,+0.000f,-0.998f,-4.989f,+0.000f,-1.075f,-5.000f,+0.000f,-0.000f,
-0.000f,+5.373f,-0.998f,-4.865f,+4.865f,-0.951f,-4.970f,+2.370f,-1.160f,-5.000f,+1.326f,-0.000f,
-0.000f,+4.989f,-1.075f,-2.370f,+4.970f,-1.160f,-3.700f,+3.700f,-0.179f,-4.473f,+2.598f,-0.000f,
-0.000f,+5.000f,-0.000f,-1.326f,+5.000f,-0.000f,-2.598f,+4.473f,-0.000f,-3.536f,+3.536f,-0.000f,
+0.000f,-0.000f,-1.000f,+5.373f,-0.000f,-0.998f,+4.989f,-0.000f,-1.075f,+5.000f,-0.000f,-0.000f,
+0.000f,-5.373f,-0.998f,+4.865f,-4.865f,-0.951f,+4.970f,-2.370f,-1.160f,+5.000f,-1.326f,-0.000f,
+0.000f,-4.989f,-1.075f,+2.370f,-4.970f,-1.160f,+3.700f,-3.700f,-0.179f,+4.473f,-2.598f,-0.000f,
+0.000f,-5.000f,-0.000f,+1.326f,-5.000f,-0.000f,+2.598f,-4.473f,-0.000f,+3.536f,-3.536f,-0.000f,
-0.000f,-5.000f,-0.000f,-1.326f,-5.000f,-0.000f,-2.598f,-4.473f,-0.000f,-3.536f,-3.536f,-0.000f,
-0.000f,-4.989f,-1.075f,-2.370f,-4.970f,-1.160f,-3.700f,-3.700f,-0.179f,-4.473f,-2.598f,-0.000f,
-0.000f,-5.373f,-0.998f,-4.865f,-4.865f,-0.951f,-4.970f,-2.370f,-1.160f,-5.000f,-1.326f,-0.000f,
-0.000f,-0.000f,-1.000f,-5.373f,-0.000f,-0.998f,-4.989f,-0.000f,-1.075f,-5.000f,-0.000f,-0.000f,

0218デフォルトの名無しさん

2007/05/14(月) 21:53:43

誰かエスパーしてくれ

0219デフォルトの名無しさん

2007/05/14(月) 23:11:47

新手の荒らしだろ、スルーよろ。

0220デフォルトの名無しさん

2007/05/15(火) 00:22:46

k = (((i>>>2)^(i>>>1)^i)&1)*12;
は
k = ((i>>>2)&4)*12;
と等価じゃない？

0221デフォルトの名無しさん

2007/05/15(火) 00:24:00

k = (((i>>>2)^(i>>>1)^i)&1)*12;
は
k = ((i>>>2)&1)*12;
と等価

0222デフォルトの名無しさん

2007/05/15(火) 00:25:45

おいおい、不等号3つって……

0223デフォルトの名無しさん

2007/05/15(火) 00:56:43

System.out.printfって何だよ
オブジェクト指向すげえよ

0224デフォルトの名無しさん

2007/05/15(火) 02:01:14

>>>220-221
^は排他的論理和、>>>は符号無し右シフト、&は論理積なので、
k=(((i>>>2)^(i>>>1)^i)&1)*12はi=1,2,4,7の時にk=12、i=0,3,5,6の時にk=0となる。
全然等価じゃねーぞ。

0225215

2007/05/15(火) 03:58:02

エスパー困難なコードですが、一番意図の分かりにくい部分だけ解説。

k = (((i>>>2)^(i>>>1)^i)&1)*12;
上の文は、iのパリティがevenであればk=0、oddであればk=12とする処理を行う部分ですが
iの値域が0～7に限られるため、パリティの計算は下3bitに対してのみ行っています。
k = (Integer.bitCount(i)&1)*12; とする手もありますが、今回は先のように書きました。

p[0]～p[15]を4x4の行列と見た場合に、q[]にその値をコピーする
for(j=0;j<16;j++) { q[j] = p[j^k]; }
の処理はkの値によって以下のような振る舞いの変化をします。
k=0：そのまま、k=3：列を逆順に入れ替え、k=12：行を逆順、k=15：行・列ともに逆順

0226デフォルトの名無しさん

2007/05/15(火) 04:07:12

そこまで式が込み入ってたら、テーブルの方が速くないかな。
まあ、環境によるとは思うが。

0227デフォルトの名無しさん

2007/05/20(日) 08:13:37

あげ

0228デフォルトの名無しさん

2007/05/22(火) 07:41:36

ある変数の中でビットが必ず一つだけ立っているとき
そのビットの位置（左右どちらからでもよい）を求めたいのですが
↓のNTZやNLZを求めるアルゴリズムを使うのよりも高速にできませんか？
http://www.nminoru.jp/~nminoru/programming/bitcount.html
立っているビットの数が一つという条件があるので
何か工夫できないか考えたんですけど思いつきません。

0229デフォルトの名無しさん

2007/05/22(火) 08:06:11

どっかで聞いたような質問だな・・・

0230デフォルトの名無しさん

2007/05/22(火) 08:07:19

memcpyよりも高速にコピーできる高速memcpyを作りたいのですが
何か参考になる方法ってありますか？

0231デフォルトの名無しさん

2007/05/22(火) 08:18:56

>>230
memcpyより高速な手法が存在するとしたら、世の中のmemcpyはその高速
な手法を使うんじゃない？

0232デフォルトの名無しさん

2007/05/22(火) 08:24:56

>>230
ビット単位で転送するという話でもない限り、スレ違い。

0233デフォルトの名無しさん

2007/05/22(火) 08:26:58

>>231
いいえ。

0234デフォルトの名無しさん

2007/05/22(火) 08:31:37

前スレのログってどこかにある？

0235デフォルトの名無しさん

2007/05/22(火) 08:35:42

あ、あったあった。
http://p2.chbox.jp/read.php?host=pc8.2ch.net&bbs=tech&key=1123918075&ls=all
ここの377に似たような質問があるね。

0236デフォルトの名無しさん

2007/05/22(火) 08:39:30

>>228
ビット位置を持って回ることを検討したか?

>>230
つ [ゼロコピー]

0237デフォルトの名無しさん

2007/05/22(火) 09:05:14

ビット位置を持って回るのは難しいと思いました。
ビットはこんな風に複数のビットが立ってる変数から取り出してます。
UInt32 bits;
...
while(bits)
{
UInt32 bit = bits&(-bits);
UInt32 bit_position = get_bit_position(bit);
...
}
で、このget_bit_position()の部分を作りたいのですが・・

0238デフォルトの名無しさん

2007/05/22(火) 09:12:52

ちょっと>>235を読んできます

0239デフォルトの名無しさん

2007/05/22(火) 10:16:01

とりあえず>>235の430でやってみます。
みなさんありがとうございました。

0240デフォルトの名無しさん

2007/05/23(水) 15:19:02

24xx32～24xx512 までのシリアルEE-PROMというのは
pageというのを持っていてページサイズ内なら一度に書き込みが出来ます
ページサイズは8～256まで２のべき乗で、ROMタイプによって異なります。
今、EE_write(adr , size, dt[] ) という関数があって、この関数はページサイズを認識しません。
そこでこのラッパを作りたいのです
pagesize, ADR, SIZE , *p

if( (ADR ^ (ADR + SIZE -1)) & (0xFFFFu-(pagesize-1) ) ){　一度に書ける }

分割しなければいけない場合
ADR ～ (ADR | (pagesize-1) ) が最初に書く領域　

というふうに考えたのだけど、ループが格好良く書けないの。

0241デフォルトの名無しさん

2007/05/23(水) 16:43:01

自己レス
結局こうやった

while(( (ADR ^ (ADR+SIZE-1)) & (0xFFFFU-(pagesize-1)) ) ){
　ct = (ADR | (pagesize-1))+1 -ADR;
　EE_write(ADR, ct , p);
　p　　+= ct;
　ADR　+= ct;
　SIZE -= ct;
}
EE_write(ADR, SIZE , p );

0242デフォルトの名無しさん

2007/05/24(木) 05:19:07

格好良いかどうかは主観だという良い例。

0243デフォルトの名無しさん

2007/05/25(金) 17:20:07

>>241
普通に書くとこんな感じ？

    unsigned tail = adr + size;
    unsigned ct = pagesize - adr % pagesize;

    while (adr + ct < tail) {
        EE_write(adr, ct, dt);
        dt += ct;
        adr += ct;
        ct = pagesize
    }
    if ((ct = tail - adr) != 0)
        EE_write(adr, ct, dt);

>>241って、SIZEに 0 を指定されると大変なことになりそうだな。

0244デフォルトの名無しさん

2007/05/27(日) 15:33:15

汚いJavaコードコンテストの会場はこちらですか？

0245デフォルトの名無しさん

2007/05/27(日) 15:35:13

いいえ、ここはJavaを知らない244が居るスレです。

0246デフォルトの名無しさん

2007/05/27(日) 22:25:32

面白くない　失せろ

0247デフォルトの名無しさん

2007/05/27(日) 23:15:48

エンディアンの変換を共用体でやるのってどうやるんですか？

0248デフォルトの名無しさん

2007/05/27(日) 23:26:39

バイトオーダーは詳しくないが
int, int って並びなら、
1, 2, 3, 4, 5, 6, 7, 8 が
4, 3, 2, 1, 8, 7, 6, 5 ってなるだけで
8, 7, 6, 5, 4, 3, 2, 1 にはならないのでは？

0249・∀・）っ-○◎●

2007/05/27(日) 23:31:17

こうですかわかりません＞＜

typedef union {
　　uint32_t wd;
　　uint8_t bt[4];
} HogeType;

HogeType a, b;
a.wd = src;
b.bt[0] = a.bt[3];
b.bt[1] = a.bt[2];
b.bt[2] = a.bt[1];
b.bt[3] = a.bt[0];
dest = b.wd;

0250デフォルトの名無しさん

2007/05/28(月) 00:21:29

ヤツはダンゴさんじゃない

0251デフォルトの名無しさん

2007/05/28(月) 00:52:56

共用体って、本当はそういう風に使っちゃダメなんだよな。
規格違反。
まあ、そう使えないコンパイラはないと思うけど。

0252デフォルトの名無しさん

2007/05/28(月) 08:09:58

おいおい共用体をそういう風に使わずにほかにどんな用途があるって言うんだアホかw

0253デフォルトの名無しさん

2007/05/28(月) 10:29:21

使ってはいけない理由があるからそう決められているんだろ。
その理由が皆目検討つかないが。

0254240

2007/05/28(月) 10:38:09

>>243
ありがとう。参考になった。
でも、そのままだと最後の書き込みサイズが正しくなかったよ。

0255デフォルトの名無しさん

2007/05/28(月) 15:48:22

>>252,>>253
共用体のメンバのうち T 型の a というメンバに値が格納されているときは
U(!= T) 型の b というメンバの値は T 型の a に依存し、U 型の値としては
不正と見なされるため b を通してのアクセスは未定義の動作となる。

ではなぜ共用体が存在するのかというと、おそらく原始的なポリモーフィズムの
実現の為。

ある変数が複数通りの型（ここでは T と U とする）の値を受け入れる可能性が
あるとき、構造体のような、型の異なる複数の変数を用意するのは非効率のため
単一の変数で複数の型を扱える共用体を使う。

もっとも、C++では T 型と U 型の基本クラス V 型を定義して、V 型の参照として
T 型にも U 型にも（もちろん V 型にも）正規にアクセスできるので、共用体は
不要になってしまった（のだろう、たぶん）。

0256デフォルトの名無しさん

2007/05/28(月) 17:15:17

共用体はこういうことのためにある。

enum Variant_Type {
VARIANT_INT,
VARIANT_DOUBLE,
VARIANT_CHAR,
VARIANT_STRING
};
struct Variant {
union {
int i;
double d;
char c;
char *s;
} value;
enum Variant_Type type;
};

/* var->type で分岐して、その内容を表示する関数 */
void Variant_show(const struct Variant *var) { ... }

int main(void) {
Variant var;

var.type = VARIANT_INT;
var.value.i = 4;
Variant_show(&var);

var.type = VARIANT_STRING;
var.value.s = "hoge";
Variant_show(&var);
}

0257デフォルトの名無しさん

2007/05/28(月) 22:18:41

>>255
> もっとも、C++では T 型と U 型の基本クラス V 型を定義して、V 型の参照として
> T 型にも U 型にも（もちろん V 型にも）正規にアクセスできるので、共用体は
> 不要になってしまった（のだろう、たぶん）。

不要になってないだろ。

基本クラス云々で各種のデータを扱う処理は正規にできるようになったけど、
複数の型を同一の領域に割り付けるのは union でないとできない。

まあ、そんな機会はめったとないが。

0258デフォルトの名無しさん

2007/05/28(月) 22:22:43

普通わざわざそんな面倒なことしないと思いますけどねw
それで何の御利益があると思って書いてるんだろうか？
不思議な発想だとしか言いようがない

っていうか、それ多態じゃなくて多重定義でしょ？w

0259デフォルトの名無しさん

2007/05/28(月) 22:29:27

？

0260デフォルトの名無しさん

2007/05/28(月) 22:31:52

258は>>255-256宛てね

0261デフォルトの名無しさん

2007/05/28(月) 22:35:30

型がクラスだったりする可能性を考えると
共用体よりplacement newのほうが良いと思う。

0262デフォルトの名無しさん

2007/05/28(月) 22:36:54

バリアント型とか知らないのかな。
そして、それが内部的にどうなってるかとか、
そこでのコスト意識とかに至っては、全く考えた事ないんだろうね。

0263デフォルトの名無しさん

2007/05/28(月) 22:38:44

>>261
共用体に入れられるのはそもそも POD 型だけだが、
ポインタで保持しておくことなら可能だな。

0264デフォルトの名無しさん

2007/05/28(月) 22:54:29

>>262
> バリアント型とか知らないのかな。

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

0265デフォルトの名無しさん

2007/05/28(月) 22:59:44

いや、煽り抜きでそういう発想はちょっとないよね。

0266デフォルトの名無しさん

2007/05/28(月) 23:06:16

Cだとバリアント型はにっくきCOMの象徴のひとつだからトラウマが・・・ｗ

0267デフォルトの名無しさん

2007/05/28(月) 23:11:53

皆がどのレスについてレスしてるのか分からなくなってきた。
つーかビット演算スレでなぜ共用体…。

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

0268webmaster@気まぐれアナスイ

2007/05/28(月) 23:11:54

　　 { >>>>>>>>985 }
　　　 ζ
　　　　!(+Φ＿Φ)つ√ζ
　　 +⊂.　+ 〆∂ 　 {Ж}
　　 "〆∂∂
　　〆〆
　 .:"

0269デフォルトの名無しさん

2007/05/28(月) 23:15:15

コピペ君って馬鹿だな、まで読んだ。

0270デフォルトの名無しさん

2007/05/28(月) 23:38:38

>>256
でも共用体って記述した順番にメモリに保存されるかについて
仕様では未定義ですよね

0271デフォルトの名無しさん

2007/05/28(月) 23:40:46

>>270
当たり前だろ。

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

0272デフォルトの名無しさん

2007/05/28(月) 23:43:42

>>270
これはひどい

0273デフォルトの名無しさん

2007/05/28(月) 23:45:43

コンパイラコンパイラ触ってるなら、
このくらい常識だろ？

0274デフォルトの名無しさん

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];

みたいなのが希望って事か？

0275デフォルトの名無しさん

2007/05/28(月) 23:49:33

それは二重に規格違反してて、
おかしくなるコンパイラもあるらしいよ。
俺はそういうの見た事無いけど。

0276デフォルトの名無しさん

2007/05/29(火) 00:13:33

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

0277デフォルトの名無しさん

2007/05/29(火) 00:20:53

参考までに>>274の規格違反している点を簡単に指摘してください

0278デフォルトの名無しさん

2007/05/29(火) 00:32:45

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

0279デフォルトの名無しさん

2007/05/29(火) 00:44:32

>>277
共用体の pW メンバに代入した場合、
pW の値しか正当性が保証されない。
そのため、pW に代入したすぐ後に pB を参照したとき、
規格ではその動作を保証しない。

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

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

0280デフォルトの名無しさん

2007/05/29(火) 01:08:03

ハッカーのたしなみに一致する日本語のページ約 104 件
ハッカーのたのしみに一致する日本語のページ約 26,800 件

0281デフォルトの名無しさん

2007/05/29(火) 01:15:26

すまんよ。まちがえた。

0282デフォルトの名無しさん

2007/05/29(火) 10:36:39

そもそもCの言語仕様で「未定義」な理由は、最初のバイトが最上位か最下位かはエンディアン依存だから。
逆にいうとハードに強く依存する標準仕様はあってはならない。

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

0283デフォルトの名無しさん

2007/05/29(火) 10:52:02

構造体のアラインメントはC仕様では未定義だが、アラインメント不整合だと例外を起こすアーキもある。
データレイアウトを実装者で取り決める独自仕様が認められないなら、Cは危険な言語だな逆にいえば。

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

0284デフォルトの名無しさん

2007/05/29(火) 11:17:39

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

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

0285デフォルトの名無しさん

2007/05/29(火) 11:25:40

実は未定義ではなく実装依存という罠

0286デフォルトの名無しさん

2007/05/29(火) 11:38:48

エンディアンの変換はほぼ間違いなくできるがリトルからビッグかビッグからリトルかはエンディアン依存ってことだろ。

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

0287デフォルトの名無しさん

2007/05/29(火) 11:43:14

共用体で　ビットフィールド　を使えば、マシになるかい？

0288デフォルトの名無しさん

2007/05/29(火) 12:21:19

>>286
>>276
そして話題はループする。

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

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

0289デフォルトの名無しさん

2007/05/29(火) 12:27:18

規格にないものを扱うのに規格内のルールを持ち出す馬鹿。
windows.hを使うのも規格違反だとか言い出しそうだな

0290デフォルトの名無しさん

2007/05/29(火) 12:34:19

厳密にはそうだな。ハンドルをポインタ型とかメチャクチャしたMSは糞。
ちなみに、規格にないものを付け加えるのではなく、規格に抜けているを補うのがABI。
本来は規格に矛盾しないABIを定めなければならない。

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

0291デフォルトの名無しさん

2007/05/29(火) 12:56:10

ミドルエンディアンのこともたまには思い出してやってください

0292デフォルトの名無しさん

2007/05/29(火) 13:13:17

GUIがなくてstdioで画面入出力するようなアプリのほうが品質低いと見なすがなうちの顧客は。

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

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

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

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

0293デフォルトの名無しさん

2007/05/29(火) 13:37:27

きもちわるいなあ

0294デフォルトの名無しさん

2007/05/29(火) 14:40:40

エチケット袋持ってきましょうか？

0295デフォルトの名無しさん

2007/05/29(火) 15:10:33

いえ結構。そのまま吐きます

0296デフォルトの名無しさん

2007/05/29(火) 15:14:49

キッシュを食うのとエチケット袋を使うのはガキ。

0297デフォルトの名無しさん

2007/05/29(火) 17:55:34

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

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

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

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

0298デフォルトの名無しさん

2007/05/29(火) 18:53:41

話は逸れるが、ハンドルも全てがアドレス値（ポインタ）でないとは限らない。
ドラッグ＆ドロップの処理などでGlobalAllocでメモリ確保したものを
HDROP型へキャストしてやるという事例がある。

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

0299デフォルトの名無しさん

2007/05/29(火) 18:56:05

それをいうなら、そもそもポインタ（というより左辺値）だってアドレス値とは限らないでしょ？

0300デフォルトの名無しさん

2007/05/29(火) 19:02:00

プログラムごとに論理的なアドレス空間を持ってるんじゃないの？
昔、物理的なアドレスを使えば一意だろうと思って使ったら、見事に失敗した。

0301デフォルトの名無しさん

2007/05/29(火) 19:09:48

＞ハンドルの値は別にアドレスではないのに
＃ハンドルの値は別にアドレスとは限らないのに

とするか。

0302デフォルトの名無しさん

2007/05/29(火) 19:13:49

まあ、メンバ関数ポインタなんかは
確かにメモリアドレス以上の情報を持ってることもあるけど、
C++ における「アドレス」ってのは、
そういう情報も含むんじゃないのかな。多分。

0303デフォルトの名無しさん

2007/05/29(火) 20:07:37

きょうび、１つのCPUでも「アドレス」が3種類くらいあって当たり前だしなぁ

0304デフォルトの名無しさん

2007/05/29(火) 20:27:53

Cはアドレスの概念を抽象化したから、Cにはアドレスという概念はないと。
どっかで見た。

0305デフォルトの名無しさん

2007/05/29(火) 20:36:02

ところがどっこい&演算子の読み方は・・・

0306デフォルトの名無しさん

2007/05/29(火) 21:00:16

アドレス演算子だな。

0307デフォルトの名無しさん

2007/05/29(火) 21:24:50

えっ？reference operatorじゃないの？
とか思ったけどそれはC++の話でしたねすいません

0308デフォルトの名無しさん

2007/05/29(火) 21:53:21

ANSI C: address operator
別名: reference operator

0309・∀・）っ-○◎●

2007/05/30(水) 01:32:06

よーしだんごやさんが燃料投下するぞー
「共用体を使った型変換は、保証されないとむしろ違反」

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

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

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

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

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

0310・∀・）っ-○◎●

2007/05/30(水) 01:35:52

RubyはCで書かれてるけどオブジェクトは共用体を巧みに使うことでで実装されてるね。
それでもさまざまなプラットフォームに移植されてるけどｗｗｗｗ

0311デフォルトの名無しさん

2007/05/30(水) 01:47:03

最適化でどうなるかとかちゃんと考えてるか？

0312・∀・）っ-○◎●

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で十分な気もしてきた」とか思うのもまた一興。

0313デフォルトの名無しさん

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;
}

0314・∀・）っ-○◎●

2007/05/30(水) 02:11:59

x86のeaxレジスタは下位半分はaxレジスタであり、ahとalでもある
レジスタそのものが共用体なんですよ。

0315デフォルトの名無しさん

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
ついでに言うと、これをどう最適化するかがコンパイラの腕の見せ所。

0316・∀・）っ-○◎●

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

0317デフォルトの名無しさん

2007/05/30(水) 02:33:39

>>309
混同も何も、そもそも「規格外」とか「規格違反」とかいう用語は規格にあるのか？

0318デフォルトの名無しさん

2007/05/30(水) 02:35:52

%0X って意味ねー。
%08X っしょ。

0319・∀・）っ-○◎●

2007/05/30(水) 03:08:16

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

0320デフォルトの名無しさん

2007/05/30(水) 08:24:42

気色の悪いHN付ける奴の行動パターンやそこから透けて見えるパーソナリティっていうのは、
どいつもこいつもどうしてこう画一的・類型的で凡庸なんだろうなw

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

0321デフォルトの名無しさん

2007/05/30(水) 08:41:04

凡庸乙

0322デフォルトの名無しさん

2007/05/30(水) 08:48:32

>>320
あなたのその発言もまた　画一的・類型的で凡庸　な事に気付いてての発言だとすれば　あなたは勇気がある。
気付いてないなら・・・・・

0323デフォルトの名無しさん

2007/05/30(水) 08:56:16

人間なんてみんな一緒だろ。
ハッキリいってイルカよりもマグロの方が頭いいです。
人類の知能は一億年遅れてる。

0324デフォルトの名無しさん

2007/05/30(水) 14:10:27

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

0325デフォルトの名無しさん

2007/05/30(水) 20:38:32

俺のアナルも高速化されそうです

0326デフォルトの名無しさん

2007/05/31(木) 01:08:47

俺様の射精は低速化されましたが何か?

0327デフォルトの名無しさん

2007/05/31(木) 01:34:42

さらに角度までorz....

0328デフォルトの名無しさん

2007/05/31(木) 04:34:03

自分の精液を味わって飲んでみましたクセになりそうです

0329デフォルトの名無しさん

2007/05/31(木) 09:31:52

【下ネタ化】ビッチ猥談

0330デフォルトの名無しさん

2007/06/01(金) 01:04:55

>>328
なんか体調によって味とか変わってくるらしいね。調子がいいときはどんな味がするん？

0331デフォルトの名無しさん

2007/06/01(金) 01:06:15

ごめん、sage 忘れた。

0332デフォルトの名無しさん

2007/06/01(金) 14:45:44

ごめん、ぬるぽ忘れた。

0333デフォルトの名無しさん

2007/06/01(金) 15:11:37

ぬるぽの話題は参照の話題について直接的ないし間接的に関係のあるスレッドでしか出す事は許さん。

0334デフォルトの名無しさん

2007/06/01(金) 15:23:11

>>329
それを言うなら「低俗化」では?

0335デフォルトの名無しさん

2007/06/01(金) 17:57:17

風俗化

0336デフォルトの名無しさん

2007/06/01(金) 18:11:47

Jデッ化

0337デフォルトの名無しさん

2007/06/01(金) 18:35:50

つーかおまいらこんなことしてていいの化

0338デフォルトの名無しさん

2007/06/01(金) 23:16:16

ばか

0339デフォルトの名無しさん

2007/06/02(土) 12:18:51

珍しく最近妙にスレが伸びてると思ったら、こう言う内容だったの化

0340デフォルトの名無しさん

2007/06/03(日) 02:25:37

なんじゃゴラァ、おまいらバカ化

0341デフォルトの名無しさん

2007/06/03(日) 04:24:42

あ？

0342デフォルトの名無しさん

2007/06/19(火) 21:59:45

0000 0001 0011 0010 0110 0111 0101 0100
1100 1101 1111 1110 1010 1011 1001 1000

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

0343デフォルトの名無しさん

2007/06/19(火) 22:04:20

パイオニアだかボイジャーだかのレコード盤に記録されてる奴？

0344デフォルトの名無しさん

2007/06/19(火) 22:17:46

Gray Codeだな

0345デフォルトの名無しさん

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;

0346デフォルトの名無しさん

2007/06/19(火) 23:15:55

ううまま　うままう　うまう　うままう

0347デフォルトの名無しさん

2007/06/20(水) 12:26:09

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

0348デフォルトの名無しさん

2007/06/20(水) 14:21:11

要するに>>342は
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
って意味

0349デフォルトの名無しさん

2007/06/20(水) 18:58:03

>>347-348が理解できない

0350デフォルトの名無しさん

2007/06/20(水) 19:07:00

ばっかー

0351デフォルトの名無しさん

2007/06/20(水) 19:09:51

2ビットのグレイコードは、2相エンコーダと呼ばれてる。　機械式のマウスなんかで使われている。
　00 01 11 10　この順番で動けば順方向　逆方向なら　00 10 11 01 と動くので区別出来る

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

0352デフォルトの名無しさん

2007/06/21(木) 00:53:52

ハミング距離でぐぐるといいよ

0353デフォルトの名無しさん

2007/06/21(木) 01:35:52

上位ビットから順に加算して途中でやめても、下位ビットの影響がそれより上に及ばない、っていう利点もある。

0354デフォルトの名無しさん

2007/06/21(木) 01:46:36

>>353
それ、具体的に教えて。

0355デフォルトの名無しさん

2007/06/21(木) 23:48:28

56の余りを求めるビットマスクはどのように書けばいいのでしょうか？

0356デフォルトの名無しさん

2007/06/21(木) 23:55:04

商か剰余を求めるビット演算を生成する CGI か何かを昔見かけたような気が・・・。
どこだっけかな・・・。

0357デフォルトの名無しさん

2007/06/22(金) 01:08:45

56の余りってなにさ?

0358デフォルトの名無しさん

2007/06/22(金) 01:17:06

x % 56でも計算したいんじゃね？

0359デフォルトの名無しさん

2007/06/22(金) 07:26:57

x % 56だと　２のベキ乗じゃないからビット演算1発では出来ないな
ttp://www.tensyo.com/urame/date/dayTips.shm
ここの後ろの方にビットマスクと繰り返し演算で剰余を求める方法がある

0360デフォルトの名無しさん

2007/06/22(金) 07:35:52

定数での除算って、こんなに繰り返し必要だったっけ？
３、４回の演算で書けたような気が・・・って、俺の記憶違いか？

0361デフォルトの名無しさん

2007/06/22(金) 07:37:37

それ、もしかしたら、２のべき乗での除算？

0362デフォルトの名無しさん

2007/06/22(金) 07:40:38

いや、それなら１回でいけるし。

あれ？乗算だっけ？

0363デフォルトの名無しさん

2007/06/22(金) 07:42:31

ああ、何か乗算だった気もしてきた。スマン。

0364デフォルトの名無しさん

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回ちょっとのループか

0365デフォルトの名無しさん

2007/06/22(金) 08:00:17

56*73 =4088 で 2^12-8 だから
a = ( (a>>12)<<3 ) + a & 4095; を　前段でやれば改善するんじゃないかな　

0366デフォルトの名無しさん

2007/06/22(金) 09:49:41

最近のコンパイラは定数の割り算は掛け算に置き換えるね。
56で割るロジックをコンパイルしたら、-1840700269を掛けた後に
ビットシフトと足し算をしていた。それ以上追っかけるのはパス。

0367デフォルトの名無しさん

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の場合は、もう少し複雑。

0368デフォルトの名無しさん

2007/06/22(金) 10:11:46

なるほど、>366の数値が0x92492493だからシフト量が違う同じビットパターンなのか。

0369デフォルトの名無しさん

2007/06/22(金) 10:17:29

でもまあPCのCPUみたいに掛算が高速だったらって前提だな。
1チップとかだと　掛算はビットサイズに応じたサイクル数かかるし
掛け算持ってないＣＰＵもあるし

0370デフォルトの名無しさん

2007/06/22(金) 10:21:39

大丈夫、そういうCPUは割り算も遅い。

0371デフォルトの名無しさん

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;

これならどうだろ？

0372デフォルトの名無しさん

2007/06/22(金) 10:34:31

演算子の数が20を超えてるな。
素直にdiv使った方が速いかもしれない。

0373デフォルトの名無しさん

2007/06/22(金) 10:45:50

もうちょっとバランスをうまく取れば、1行減らせるかもな

0374デフォルトの名無しさん

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ビットづつしか落とせない。　無理

0375デフォルトの名無しさん

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回のループでいいか

0376デフォルトの名無しさん

2007/06/22(金) 11:26:49

>>372
div 命令は、持っていてもbit数のサイクルかかるのが殆どだよ。　だから >>366-367 のような最適化がされるんだし

0377デフォルトの名無しさん

2007/06/22(金) 11:33:21

ただ PC の場合はレイテンシがかかるだけだから、divを使った方が速いかもしれないな。

0378デフォルトの名無しさん

2007/06/22(金) 11:37:09

>>367
ここまでしても idiv より速いのか・・・。

0379デフォルトの名無しさん

2007/06/22(金) 11:48:18

Pentium II およびPentium III プロセッサの実行ユニット

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

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

0380デフォルトの名無しさん

2007/06/22(金) 11:50:39

浮動小数点ユニットで行われるのか？！

0381デフォルトの名無しさん

2007/06/22(金) 11:58:11

だって　整数乗算ユニットってのはブロック図にあるが、　整数除算ユニットってのはどこにも無いだろ？

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

0382デフォルトの名無しさん

2007/06/22(金) 12:14:11

そうだったのか・・・。
そら遅いわな。

0383デフォルトの名無しさん

2007/06/22(金) 12:27:02

>>381
これ以上はスレ違いになるがつっこませてくれ。
浮動小数点ユニットがIEEE754（だったっけ）で処理する場合、単精度で23ビット、倍精度で52ビットの精度だろ。
被序数が32ビット整数ならともかく、64ビット整数の除算は精度の問題上アウトだぞ。

0384デフォルトの名無しさん

2007/06/22(金) 12:34:23

>>383
Intel 系の浮動小数点ユニットは
拡張倍精度（80ビット/仮数部64ビット）で行われてるから大丈夫。

0385デフォルトの名無しさん

2007/06/22(金) 12:44:20

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

0386デフォルトの名無しさん

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

0387デフォルトの名無しさん

2007/06/22(金) 13:07:24

しかし、1/7って面白いなぁ。10進だけでなく16進でも綺麗な循環小数になるんだな。

0388デフォルトの名無しさん

2007/06/22(金) 13:08:10

もしかして >>375 のような事しても idiv 使うより速いって事はありえるのか？

0389デフォルトの名無しさん

2007/06/22(金) 16:51:54

>>388
実際に速度を比較してみれば？

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

0390デフォルトの名無しさん

2007/06/22(金) 17:06:59

そうだね。

0391デフォルトの名無しさん

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 命令より速い

0392デフォルトの名無しさん

2007/06/22(金) 18:06:18

そうだね。

0393デフォルトの名無しさん

2007/06/22(金) 18:09:15

上の and 7 は　 and -8 の間違いだった

0394デフォルトの名無しさん

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

0395デフォルトの名無しさん

2007/06/22(金) 18:40:43

　結局 idiv : ビット演算 : 掛算の　重さは　およそ　5 : 2 : 1 だった。

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

0396デフォルトの名無しさん

2007/06/22(金) 19:24:47

これを高級言語で書いたら他の人に白い目で見られるだけならまだいいんだけど
ひどい場合は書き直しすら命じられまする(´・ω・`)

0397デフォルトの名無しさん

2007/06/22(金) 19:44:35

そうだね。

0398デフォルトの名無しさん

2007/06/22(金) 20:36:07

>>396
高級言語の目的の一つが可読性の向上だからね。
コメントで解説いれても却下される場合すらあると思うよ。

0399デフォルトの名無しさん

2007/06/22(金) 20:48:20

除算命令がないCPUなら有効だろうけど
x % 60 が欲しい時とか、いちいち変換が大変だよな

0400デフォルトの名無しさん

2007/06/22(金) 21:47:03

導出は機械的なプロセスだから、スクリプトみたいなのでサクッと求めるといいと思う。
可能なら、最適化の一環としてコンパイラに組み込むのがベストだが。

0401デフォルトの名無しさん

2007/06/22(金) 23:23:02

だから、掛け算化はgccでもやってるって。

0402デフォルトの名無しさん

2007/06/23(土) 00:18:01

>>401
ほんとにやってる？やらない場合も多いけど
絶対さぼってる

0403デフォルトの名無しさん

2007/06/23(土) 01:26:20

昔のx86みたいにALUしかないCPUはそういう風にやってたのかぁ、勉強になりました。

0404デフォルトの名無しさん

2007/06/23(土) 01:29:46

>>403
定数割り算の掛け算化が行われない例があれば、逆に教えて欲しい。
まさか、最適化オプションを指定しないとしてくれないなんて言わないよね。

0405デフォルトの名無しさん

2007/06/23(土) 01:31:50

>>404
深く考えず単純に引き算かと
今考えると空恐ろしいやり方だｗ

0406デフォルトの名無しさん

2007/06/25(月) 10:58:28

>404は>402宛てなんだろうなぁ。それはいいけど、>405は何を言いたいのだろう……

0407デフォルトの名無しさん

2007/06/25(月) 19:13:34

きっと8086には除算命令が無いと思ってるんだろう。

0408デフォルトの名無しさん

2007/06/25(月) 19:57:27

Pen3では除算を浮動小数点ユニットでされるというのを見て、
浮動小数点ユニットが無い時には除算も無かったと思ったのかな

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

0409405

2007/06/26(火) 07:50:34

>>406
あ、ほんとだね
>>407,408
んにゃ、引き算の連続で商余求めてたのかなと

0410デフォルトの名無しさん

2007/06/26(火) 08:23:37

これは固定での剰余だから高速化出来るのであって
変数での剰余になると、結局コードで書いても加え戻し法(復元法)とかになるので
除算命令使った方がやっぱり速い。

0411デフォルトの名無しさん

2007/06/28(木) 00:42:51

DSP(やCell)では逆数をニュートン法で求めるのが定番

0412デフォルトの名無しさん

2007/07/08(日) 16:40:57

8086で除算命令使うとCPUの方で乗算とシフト命令に解釈しなおす訳？
ということは除算命令自体はマクロになるのかな

0413デフォルトの名無しさん

2007/07/08(日) 18:16:20

は？

0414デフォルトの名無しさん

2007/07/08(日) 19:57:33

除算命令に出くわして、せっせとメモリ中のコードを書き換える、けなげな86の姿を想像した・・・

0415デフォルトの名無しさん

2007/07/11(水) 22:50:58

言う事聞かない奴隷なんかいらない

0416デフォルトの名無しさん

2007/07/21(土) 07:45:05

>>412
マイクロプログラムで処理してるんだろ
＞8086のマイクロコードは、命令長が21ビットで、プログラムサイズは504ステップであった

0417デフォルトの名無しさん

2007/07/21(土) 10:07:54

そろそろダンゴさんに〆てもらうか。

0418デフォルトの名無しさん

2007/07/21(土) 21:50:22

うむ

0419デフォルトの名無しさん

2007/08/03(金) 07:04:32

あ

0420デフォルトの名無しさん

2007/08/03(金) 11:40:01

ダゴンを深淵から呼びだしては駄目だ

0421だんごの輪島

2007/08/03(金) 12:15:43

ん?

0422デフォルトの名無しさん

2007/08/03(金) 21:06:03

は？

0423デフォルトの名無しさん

2007/08/12(日) 09:53:59

は

0424デフォルトの名無しさん

2007/08/12(日) 10:01:53

ビッチ演算

0425デフォルトの名無しさん

2007/08/12(日) 14:27:31

ビット大佐

0426デフォルトの名無しさん

2007/08/14(火) 10:07:39

age

0427デフォルトの名無しさん

2007/08/14(火) 11:48:05

あ

0428デフォルトの名無しさん

2007/08/16(木) 20:39:50

〆

0429デフォルトの名無しさん

2007/08/18(土) 23:05:50

あｇｗ

0430デフォルトの名無しさん

2007/08/18(土) 23:09:42

ぬるぽ

0431デフォルトの名無しさん

2007/08/20(月) 01:29:30

ちょっとスレの趣旨と違うと思うんだけど、適当なところが無かったので、
アドバイス頼む。

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

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

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

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

0432デフォルトの名無しさん

2007/08/20(月) 01:38:30

>>431
Linux界隈じゃ unsigned long へのキャストが一般的とされてるが
個人的には嫌い

0433デフォルトの名無しさん

2007/08/20(月) 01:40:50

intptr_t / uintptr_t を使えばいいんじゃない？

0434デフォルトの名無しさん

2007/08/20(月) 08:48:31

下位ビットだけ入ればいいので、charでもいい

0435デフォルトの名無しさん

2007/08/20(月) 23:58:10

さすがにそれはありえないだろ?

0436デフォルトの名無しさん

2007/08/21(火) 00:11:51

なぜそう思うの？

0437デフォルトの名無しさん

2007/08/21(火) 00:33:14

バイトオーダー

0438デフォルトの名無しさん

2007/08/21(火) 00:37:00

バイトオーダーは関係ないかと

0439・∀・）っ-○◎●

2007/08/21(火) 00:52:14

WindowsならUINT_PTRにキャスト

0440デフォルトの名無しさん

2007/08/21(火) 01:00:01

ダンゴさんがピシっと〆めたな。

0441・∀・）っ-○◎●

2007/08/21(火) 01:19:06

うんこうんこうんｋ

0442デフォルトの名無しさん

2007/09/09(日) 23:01:40

う

0443デフォルトの名無しさん

2007/09/09(日) 23:35:23

ん

0444デフォルトの名無しさん

2007/09/09(日) 23:37:25

ち

0445デフォルトの名無しさん

2007/09/09(日) 23:45:20

ゃ

0446デフォルトの名無しさん

2007/09/16(日) 06:34:05

あ

0447デフォルトの名無しさん

2007/09/19(水) 12:28:31

は

0448デフォルトの名無しさん

2007/09/19(水) 12:32:11

た

0449デフォルトの名無しさん

2007/09/19(水) 13:50:16

ぼ

0450デフォルトの名無しさん

2007/09/19(水) 23:03:56

ぬ

0451デフォルトの名無しさん

2007/09/19(水) 23:56:29

る

0452デフォルトの名無しさん

2007/09/20(木) 00:04:43

ぽ

0453デフォルトの名無しさん

2007/09/20(木) 18:42:49

>>450-452
ｶﾞ

0454デフォルトの名無しさん

2007/09/22(土) 00:43:27

http://pc11.2ch.net/test/read.cgi/tech/1142467359/555
これもっと簡単にならないかな？

0455デフォルトの名無しさん

2007/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;
}
--------------------

0456デフォルトの名無しさん

2007/09/27(木) 20:24:00

age

0457デフォルトの名無しさん

2007/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を返す。

0458デフォルトの名無しさん

2007/09/29(土) 23:17:24

return ++a%9;

0459デフォルトの名無しさん

2007/09/29(土) 23:39:43

% はビット演算じゃないだろう

0460デフォルトの名無しさん

2007/09/29(土) 23:58:36

int rotate_0_9(int a){return a<9?a+1:0;}

0461デフォルトの名無しさん

2007/09/30(日) 00:06:34

DAA

0462デフォルトの名無しさん

2007/09/30(日) 00:15:35

>>457
>>458
>>460
どれが速い？

0463デフォルトの名無しさん

2007/09/30(日) 00:20:18

実測あるのみ

0464デフォルトの名無しさん

2007/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が圧倒的だった(俺もそう思ってた)

ソースに続く

0465デフォルトの名無しさん

2007/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;
}
----------------------------

0466デフォルトの名無しさん

2007/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)

0467デフォルトの名無しさん

2007/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];
}
表引き。
これもやってみてくれ。

0468デフォルトの名無しさん

2007/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
無茶苦茶だった。

0469デフォルトの名無しさん

2007/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

0470デフォルトの名無しさん

2007/09/30(日) 00:57:00

あと>>458は0～8の繰り返しで条件が違うんで
int rotate_0_9_458(int a){return ++a%10;}
に修正してる

0471デフォルトの名無しさん

2007/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
見るからに遅そうな

0472デフォルトの名無しさん

2007/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以上だったら脂肪

0473デフォルトの名無しさん

2007/09/30(日) 01:27:47

まあ表引きはキャッシュから外れた時にペナルティがあるから
平均的には>460がいいんだろうな。

0474デフォルトの名無しさん

2007/09/30(日) 02:05:05

>>473
確かに、別の環境だと逆転してたり。

#Celeron [email protected] 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 [email protected] 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)

0475デフォルトの名無しさん

2007/09/30(日) 04:40:29

％は割り算があるから遅いってことか。0～9ではなく0～2^n-1の場合にかぎり使えばいいかな。
でも実際の仕事では0～99のローテートでも％で書いたりするなあ。

0476デフォルトの名無しさん

2007/09/30(日) 08:29:40

剰余は定数除算よりも更に遅い。

0477デフォルトの名無しさん

2007/09/30(日) 09:14:40

その剰余をビット演算でなんとか．．．

0478デフォルトの名無しさん

2007/09/30(日) 10:11:46

このスレの355から、剰余をビット演算でする方法が書かれているよ。

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

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

0479457

2007/09/30(日) 23:43:50

ふぬぅ、やっぱ分岐しない上にテーブルも使わない奴は遅いな。

0480デフォルトの名無しさん

2007/09/30(日) 23:45:02

逆に考えて、分岐する上にテーブルも使う奴は・・・

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

0481デフォルトの名無しさん

2007/10/01(月) 16:44:48

modも内部的には分岐してるだろ。RISCならよくわかる。

0482デフォルトの名無しさん

2007/10/01(月) 17:41:59

え～(*o*) それは２のｎ乗の場合とそうでないので分けてるとか？

0483ヽ・´∀｀・,,）っ━━━━━━┓

2007/10/04(木) 02:56:19

剰余　＝　披除数－ (除数＊商)

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

0484デフォルトの名無しさん

2007/10/21(日) 17:07:33

age

0485デフォルトの名無しさん

2007/10/21(日) 18:36:55

剰余のビット演算への変換ならこのページにあるよ。
http://www.tensyo.com/urame/date/dayTips.htm#MOD

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

0486デフォルトの名無しさん

2007/10/23(火) 00:23:05

ある変数の値が

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

0487デフォルトの名無しさん

2007/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;
}

0488デフォルトの名無しさん

2007/10/23(火) 01:56:04

テストしてないけど。
bool check(int value) {
const int mask = ~1;
if (((abs(value - 3034) + 1) & mask) == 1016) return true;
return false;
}

0489デフォルトの名無しさん

2007/10/23(火) 09:11:06

AND も加算も比較＝減算も、演算量は同じ、ってこと考えたら、どっちも減ってない。
比較４回に比べてリーダビリティは下がってる。

0490デフォルトの名無しさん

2007/10/23(火) 09:53:31

switch (value) {
case 2018: case 2019: case 4049: case 4050:
　　doit();
}

0491デフォルトの名無しさん

2007/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

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

0492デフォルトの名無しさん

2007/10/23(火) 11:25:06

４回比較より下の２つのが短いのが不思議ですね。
入力が多数回で、４つの値が均等にバラつくという条件にしたら、最後まで演算しない４回比較
がイイかと思えますが。

0493デフォルトの名無しさん

2007/10/23(火) 11:26:33

>>489
可読性も考慮するの？このスレで？

0494デフォルトの名無しさん

2007/10/23(火) 11:29:15

ちなみに最後の一個はswitchバージョンのアセンブル出力をCに直したもの

0495デフォルトの名無しさん

2007/10/23(火) 12:45:37

iccで試してみた。
# icc -xP -O3 -ip
# icc 10.0
上から、0.3, 0.23, 0.33, 0.3, 0.22[sec/(10000 * 10000call)]だった。
どうやらswitchで書いても一番上と同じような出力になるようだ。
gccでも試してみた。
# gcc -O3 -funroll-loops
# gcc 3.4.6
こちらは、0.16, 0.22, 0.27, 0.17, 0.22[sec/(10000 * 10000call)]だった。
なんでこんなに速いんだ?w

0496デフォルトの名無しさん

2007/10/23(火) 21:35:27

>>495
アセンブリコードで比較してみると分かるんじゃね？

0497デフォルトの名無しさん

2007/10/23(火) 23:12:05

俺には>>486が
if(v==2018||v==2019){
}else if(v==4049||v==4050){
}else{
}
って条件に読めるんだが

0498デフォルトの名無しさん

2007/10/23(火) 23:17:57

俺も俺も

0499デフォルトの名無しさん

2007/10/24(水) 00:23:34

>>486
日本語でおｋ

やっと言う側に回れたか

0500デフォルトの名無しさん

2007/10/24(水) 01:05:28

>>497
いや、今日きちんとみかか村に出撃して
糞仕様について問い詰めてきたけど

case 2018: case 2019: case 4049: case 4050:

で正しい

どうもみんなありがとう

0501デフォルトの名無しさん

2007/11/02(金) 19:56:43

>491
>if (((abs (v - 3034) + 1) & mask) == 1016) return 1;
ここら辺の数値の導き方教えてください
どいった関係で3034とか出すの？ど素人ですんません

0502デフォルトの名無しさん

2007/11/02(金) 20:15:08

>>501
2018+4050=2019+4049=3034+3034

v = [2018 or 2019 or 4049 or 4050] の時
abs(v - 3034) = [1015 or 1016]
abs (v - 3034) + 1 = [1016 or 1017]
mask=0xfffffffeより奇数はそれを超えない偶数に変換される。
(abs (v - 3034) + 1) & mask = 1016

0503デフォルトの名無しさん

2007/11/02(金) 21:44:43

>502
ものっそい感動しました
久しぶりに成長した気がする
この括り方すげー

0504デフォルトの名無しさん

2007/11/03(土) 20:48:03

もはや逆方向にソースから動作仕様を求めることはほぼ不可能だな

0505デフォルトの名無しさん

2007/11/04(日) 06:35:34

かっこいい BIN→BCD は？

0506デフォルトの名無しさん

2007/11/04(日) 08:47:47

速さなら、00h,01h,02h・・・を表に持ち、binで表引き。 <99のチェックは必要。
サイズなら、((bin/16)<<4) | (bin%16) ・・・バイト版。　<99のチェックは必要。
ワードは、／100の商と余りに分けて、上のを呼び、合成。
自分で書いたのはこんな当たり前の奴だなあ・・・

0507デフォルトの名無しさん

2007/11/10(土) 16:03:38

しばらく前はメモリアクセスがからむテーブル参照の方が重いって話だったけど、
また状況変った？

0508デフォルトの名無しさん

2007/11/10(土) 16:47:46

キャッシュの容量
メモリアクセス速度とキャッシュアクセス速度の比率
によって変わるからなあ
細かくいいだすとキャッシュ方式も絡むし
結局「場合による」んじゃねえの

0509デフォルトの名無しさん

2007/11/10(土) 17:28:19

一般論としては、キャッシュに載っている(=頻繁に呼ばれる)ならテーブルの方が速いんじゃないかね。
ただ、この場合の「一般」というのは、分岐が含まれる(=分岐ミスの可能性がある)という前提。

例えば上の((bin/16)<<4) | (bin%16) の場合だと
依存関係が2箇所あって、その部分は同時実行は出来ないけど
キャッシュアクセスに要する数クロック程度の時間と比べてどちらが速いかはわからんね。

テーブルジャンプ(ほぼ同じ値が続く場合以外)は糞だけど。

0510デフォルトの名無しさん

2007/11/10(土) 17:37:19

掛けたり割ったりすることにものすごい抵抗感がある

0511デフォルトの名無しさん

2007/11/10(土) 18:06:01

いや、この場合に限れば、まず間違いなく最適化でシフトやアンドになるよ。

0512506

2007/11/11(日) 02:32:03

今のチップで乗除算持ってないほうが珍しいよね。俺が書いたのは3MHzの8085だったから、
キャッシュ云々の話はなし。／100だけは除算ルーチン使わないとだめだった。

0513デフォルトの名無しさん

2007/11/11(日) 13:44:02

ARMは現役のチップだけど除算命令なかったような

0514デフォルトの名無しさん

2007/11/14(水) 11:40:49

x/100　は　掛け算があるなら
655*( x + x/2048 + x/16384)/ 65536

0515デフォルトの名無しさん

2007/11/14(水) 14:14:26

その掛け算とｼﾌﾄの計算量なら、100=64hだから、分母の<<2と<<5と<<6を引いたほうが・・・

0516デフォルトの名無しさん

2007/11/14(水) 15:57:51

y = (655*x)>>16 で概算して

while ( x-y*100>=100 ) y++;

ならせいぜいループ１回だろ

0517デフォルトの名無しさん

2007/11/14(水) 18:05:59

最低でもx<6557202(≒(1<<32)/655)が言えなければ。

0518デフォルトの名無しさん

2007/11/14(水) 18:34:29

>>512

(42949672*x+65536)>>32

0519デフォルトの名無しさん

2007/11/15(木) 07:36:11

シフト演算子がアンカーになってしまう（ｗ
>>514-516 は、たぶん数学的には同等なような気がする。

>>518 それ、どういう原理なの？ 32シフトしたら全部なくなっちゃうような気が・・・

0520デフォルトの名無しさん

2007/11/15(木) 08:53:19

32bitレジスタ持ってるような16bit以上のCPUを想定してるんだろ

x386なら32x32bit掛け算の結果が２つのレジスタに判られるから 32bitシフトは上位のレジスタを採用するだけになる。

0521デフォルトの名無しさん

2007/11/15(木) 11:57:03

>>32
>>32

0522デフォルトの名無しさん

2007/11/15(木) 12:18:01

>>512
>>‍32

0523デフォルトの名無しさん

2007/11/15(木) 12:22:04

>>521
>>522
何が言いたいのか意味不明だ。

0524デフォルトの名無しさん

2007/11/15(木) 12:29:42

>>523

0525デフォルトの名無しさん

2007/11/15(木) 12:42:20

これでどうだ

x >> 32

0526デフォルトの名無しさん

2007/11/15(木) 12:44:23

俺他人だけど　>>‍523 色が違うだろって言いたいんじゃないのかな？

0527デフォルトの名無しさん

2007/11/15(木) 13:11:18

>>523
こうすればいいのよ（たぶん）

0528527

2007/11/15(木) 13:12:44

>>‍527
吊ってくるorz

0529518

2007/11/15(木) 16:36:17

>>520
あたり。
あと、>>518のxは0～65535の範囲である必要がある。

0530デフォルトの名無しさん

2007/11/15(木) 16:54:12

多少ステップ数がかかるように見えても、まだハードウエア除算は普通の命令２０個分以上に重いからな
1/100 は1/10のルーチンを２度呼んでたな。

1/10は1/2/5 だから１ビットシフトしてから５で割る
65536/5=13107.2 だから13107を係数に使うと誤差は16bitの範囲で１
だけど１ビットシフトしてるから、15bitの範囲になってるから最大誤差は0.5なんでOK
という事で、最大誤差の0.5を足して

x = x / 2
x = (13107*x+ 6553) / 2^16

を２度繰り返す

0531デフォルトの名無しさん

2007/11/16(金) 01:35:07

>>518 や、>>530 は余りも一緒に求まるの？

0532デフォルトの名無しさん

2007/11/16(金) 08:46:49

この話は掛け算が高速ならという話だから
余りは後から　y=x/N を求めた後 x-N*y で求めればいい

余りだけが必要なら355付近から話題が出てる

0533デフォルトの名無しさん

2007/11/16(金) 09:53:08

実測で、ハードウェアまたはCの除算を上回るルーチン作れるの？うｐして
動かしてみる辛さ

0534デフォルトの名無しさん

2007/11/16(金) 10:26:25

どっかのスレでやってたでしょ。
パソコンの除算命令はレイテンシが大きいから連続して実行させるととても重くなる。
ただ整数ユニットでは実行されないから、その間に他の命令を入れられるならＯＫ

あ、このスレか、>>367-379

0535デフォルトの名無しさん

2007/11/16(金) 10:59:28

int型の除算で標準のものより速いものは作れるのか作れないのか？

0536デフォルトの名無しさん

2007/11/16(金) 11:03:08

分母が固定なら可能。　変数なら無理。　

0537デフォルトの名無しさん

2007/11/16(金) 11:04:47

まてよ。分子が固定な場合、ニュートン法である程度いけるかな・・・・まあ無理か

0538デフォルトの名無しさん

2007/11/16(金) 11:23:21

分母が固定ならif文などで分岐すれば、総合的には速度が上げられるのか?
作ってくれ

0539デフォルトの名無しさん

2007/11/16(金) 11:26:26

経験上、演算や比較文より代入に時間がかかる気がする
たぶんレジスタ動作　+　演算より、メモリ動作は遅いんだろう

0540518

2007/11/16(金) 11:39:24

>>535
ループの中で定数(変数でも変わらなければＯＫ)で除算するのは、
置き換えた方が高速化できるし、それを実際に使っている。

ピクセル操作のような回数の多いループでは劇的な効果がある。

>>539
それは毎回キャッシュから外れた場合の話。
オンキャッシュなら少しでもＣＰＵを止めない方がいい。

0541デフォルトの名無しさん

2007/11/16(金) 11:45:08

>>538
で、分母はいくらなの？　100の場合はいろいろ出てるよね。

0542デフォルトの名無しさん

2007/11/16(金) 11:46:27

汎用の除算は出来ないか?
例えば2～500まで定数だけ作って分岐させて使う
そのとき高速になるのか?

0543デフォルトの名無しさん

2007/11/16(金) 11:48:53

その分岐の為に時間を使ってしまうから無理だろうね
たとえば関数テーブルで分岐したとしても、キャッシュミスを起こすだろう。

0544518

2007/11/16(金) 11:50:14

>>542
できる。
それぐらいなら除数の逆数のテーブルを使って可能。分岐はさせないほうがいい。
ただ、16bit全域とかになると、テーブルの方が不利になるCPUが多い。

0545デフォルトの名無しさん

2007/11/16(金) 11:54:52

逆数で気づいたけど、浮動小数点の掛け算で計算すると鈍いの？

0546デフォルトの名無しさん

2007/11/16(金) 11:57:24

逆数の2進展開を持っていたらビット演算できそうだけど・・・どうだろ　速いのか？

0547デフォルトの名無しさん

2007/11/16(金) 12:00:46

たびたび連投すまんが、計算でループを使うなら、はじめに分岐させてもコストは同じようなものだな
2～1024までなら10回の分岐で決定する　10回程度のループを使うなら分岐させた方が良い

0548デフォルトの名無しさん

2007/11/16(金) 12:01:09

>>544
(A*x+B)のＡ，Ｂをテーブルにするの？

でも、たとえば　65535÷３はどうするの？A=21845にしたら、これでは無理だよね

0549デフォルトの名無しさん

2007/11/16(金) 12:10:41

x / n = (Ax + B ) >> C ってどうやって求めるの？

0550518

2007/11/16(金) 12:12:05

>>548
そうそう。Bは固定でいい。

16ビット範囲の X / Dなら、R = 4294967295 / D として、

X / D の値は (R * X + 65536) >> 32となる。

Dが複数あるなら、D→Rのテーブルを作ればＯＫ

0551デフォルトの名無しさん

2007/11/16(金) 12:14:16

>>550
BCC5.5だけど、上のやつ計算できなかったよ

0552518

2007/11/16(金) 12:19:40

>>551

__asm{
mov eax, R
mul X
add eax, 010000h
adc edx, 0
mov eax, edx
}

0553デフォルトの名無しさん

2007/11/16(金) 13:04:33

>>550

Rが切り捨てなら汎用になるように
(R * X + R - 1 ) >> 32
でいいんじゃないの？

0554518

2007/11/16(金) 13:09:18

>>553
65536より、R - 1のがいい理由は何？

0555デフォルトの名無しさん

2007/11/16(金) 13:24:06

理由は、Xが16bitの範囲を超えて入力された時の誤差が多少でも減る事だな

0556518

2007/11/16(金) 13:36:17

>>555
誤差が許される場合はいいかもね。
そうでない場合は、素直に３２ビットに拡張した方が良くないか？

0557デフォルトの名無しさん

2007/11/16(金) 14:03:01

ようするに
(A * x + A-1 ) >> B
として AのMSBが1になるように B を調整するって事だよね？

Ｂは常に32以上だから、実際には上位ワードだけを>>(B-32) するのだろうけど

0558518

2007/11/16(金) 17:10:53

>>557
いや、そうじゃなくて、余計なA - 1 という演算を使うのではなく、
550の式を32ビットに拡張すればいいってこと。

32ビット範囲の X / Dなら、R = ((1 << 64) - 1) / D として、
X / D の値は (R * X + (1 << 32)) >> 64となる。

0559デフォルトの名無しさん

2007/11/17(土) 04:25:26

>>530
ルネサスのマニュアルによるとシフト演算と割り算に迷ったら割り算の方が大抵速いみたいなことが書いてあったけど

0560デフォルトの名無しさん

2007/11/17(土) 07:26:50

>>558 さすがに64bit掛算はまだ普及してないだろ

0561デフォルトの名無しさん

2007/11/17(土) 07:28:20

>>559 SHが特殊で固定シフト命令が1,2,4,8みたいな飛び飛びのシフトしか１命令で出来なかったりするからじゃないの？

0562デフォルトの名無しさん

2007/11/17(土) 12:16:14

でも、仕事で使用するとしたら、普通に割り算したほうがソースとして見やすいよね。
2で割るのを1ビットシフトするぐらいはいいけど、あえて複雑な演算にするほど処理能力を求められないでしょ？普通の開発は。

でも、このような議論って技術者としては面白いし、ある意味大切だよね。

0563デフォルトの名無しさん

2007/11/17(土) 12:40:03

>>560
アルゴリズム上の話で、実際に64bit乗算をするわけではないと思う。

元ネタはこれじゃね？
ttp://www.emit.jp/prog/prog_div.html

0564デフォルトの名無しさん

2007/11/17(土) 13:51:33

>>560
コンパイラがやってくれることもしばしば。
まぁ尤も、コンパイラのアセンブリ出力を見たときに「割り算がない」って悩まないためにも
知識はあったほうがいいのだけれどね。

0565デフォルトの名無しさん

2007/11/17(土) 13:57:31

Y = (R * X ) >> 64 って事は、R = 2^64 / D って事だろ？
Dが16bitの範囲なら Rは　48bitって事になるぞ。　64bitモードに以降しないと効率悪いぞ

0566デフォルトの名無しさん

2007/11/17(土) 14:00:28

もともと
D=100の場合

1　: ( x * 4294967200 + 65536) >> 32
2　: ( x * 4294967200 + 4294967199 >> 32
のどっちが大きな x までまともに計算出来るかって問題でしょ？

0567デフォルトの名無しさん

2007/11/17(土) 14:01:49

違うか
1　: ( x * 42949672 + 65536 ) >> 32
2　: ( x * 42949672 + 42949671 ) >> 32

0568デフォルトの名無しさん

2007/11/17(土) 15:24:56

BCCで出来ないんだけど・・・CPUのせいかもしれない
内部で32+24ビット程度しか保持していない気がする

0569デフォルトの名無しさん

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;
}

0570デフォルトの名無しさん

2007/11/17(土) 15:43:45

これっていくつになりますか?
1になるはずですよね?

cout << (unsigned int) ( ((1<<64)-2) >> 63 );

0571デフォルトの名無しさん

2007/11/17(土) 17:43:47

>>570
-1を unsigned にキャストしてるんだからUINT_MAXになると思う。

0572デフォルトの名無しさん

2007/11/17(土) 18:06:10

符号付整数の右シフトが論理シフトになるか算術シフトになるかは処理系定義

0573ヽ・´∀｀・,,）っ━━━━━━┓

2007/11/17(土) 19:18:14

>>569
unsigned __int64かunsigned long longでおｋ

0574ヽ・´∀｀・,,）っ━━━━━━┓

2007/11/17(土) 19:20:40

>>570
なんで普通のコンピュータで使えるビット数越えたシフト使うんだ。
1 << 64なんてオーバーフローで0になること確定じゃないか。

0575デフォルトの名無しさん

2007/11/17(土) 20:42:48

~0ULLでおｋ

0576デフォルトの名無しさん

2007/11/17(土) 23:58:43

>>569

>>563のコードと同じだからそっちでやってみればいいんじゃないか。

0577デフォルトの名無しさん

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の値が変わるのはなぜ?

0578デフォルトの名無しさん

2007/11/18(日) 08:34:36

>>577
サイズを超えるシフトは未定義。

0579デフォルトの名無しさん

2007/11/18(日) 22:48:23

ARMは割り算使うと糞遅いから困るな。

0580デフォルトの名無しさん

2007/12/03(月) 22:55:09

age

0581デフォルトの名無しさん

2007/12/03(月) 23:13:14

32bitパソコンだと、16*16しか値は保証されないよね
a + b * 65536　などと表示して、32bit以上を表現したら
ハードウェア搭載の除算よりビット演算のほうが速い?
除算が現れたらintを16bit数に変換して計算する

0582デフォルトの名無しさん

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除法を高速化出来るか?

0583582

2007/12/04(火) 05:12:33

32bit内で処理しようとすると大変だ　普通にCPUに任せた方が楽そう

0584デフォルトの名無しさん

2007/12/16(日) 20:25:38

BOOL bResultの値が 0 か -1
if (bResult == 0 || bResult == -1)

じゃなくて、一発で調べる方法はないですか？

0585デフォルトの名無しさん

2007/12/16(日) 20:42:35

BOOLなのに何故数値と比較してるんだ？

0586デフォルトの名無しさん

2007/12/16(日) 21:10:40

GetMessageじゃね？

0587デフォルトの名無しさん

2007/12/16(日) 21:30:22

BOOLは偽==0、真==0以外じゃなかったか？
定義を調べた方が良さそう。

0588デフォルトの名無しさん

2007/12/16(日) 22:05:41

世の中には変な使い方する椰子がいるのよ。MSとかw

ttp://msdn.microsoft.com/library/ja/default.asp?url=/library/ja/jpwinui/html/_win32_getmessage.asp

0589デフォルトの名無しさん

2007/12/16(日) 22:08:46

if(bResult^0==-1)

0590デフォルトの名無しさん

2007/12/16(日) 22:37:38

x^0=x

0591デフォルトの名無しさん

2007/12/16(日) 22:42:19

if (((((uint32_t)bResult) + 1) >> 1) == 0)

同じ3演算だけど-1をロードしないだけ早いかも？
uint32_tがいいかどうかはよくわからない。

0592デフォルトの名無しさん

2007/12/17(月) 00:16:01

-1か0、限定なんだからそのまま書いたほうが分かりやすいような。

0593デフォルトの名無しさん

2007/12/17(月) 00:26:58

>>588
( ･д⊂ヽ゛

0594デフォルトの名無しさん

2007/12/17(月) 00:29:32

>>588
>警告 GetMessage 関数は、0 以外の値、0、-1 のいずれかを返します。したがって、次のようなコードは避けてください。

そもそも…

0595デフォルトの名無しさん

2007/12/17(月) 00:30:54

まー継ぎ接ぎだからな

0596デフォルトの名無しさん

2007/12/17(月) 00:39:34

>>591
右シフト・条件分岐より、比較・条件分岐の方が速くない？

if (((uint32_t)bResult + 1) <= 1)

0597デフォルトの名無しさん

2007/12/17(月) 00:50:04

>>596
マシン語レベルでは結局0比較に変換されるから同じ程度じゃないかな。
でもCレベルではそっちの方が短くていいと思う。

0598デフォルトの名無しさん

2007/12/17(月) 01:17:11

>>597
ちょっと前まで主流だった某CPUではシフトは加減算の
8倍遅かったし、それ以外のCPUでも演算器の関係で
シフトの方が並列化されにくいかも、とかそういう話。

0599デフォルトの名無しさん

2007/12/17(月) 01:19:21

で、何億回呼ぶのよ

0600デフォルトの名無しさん

2007/12/17(月) 02:05:25

シフトのほうが速いと思ってたのに・・・

0601デフォルトの名無しさん

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系を数種類しか触った事ないから、他にはあるのかも知れないが。

0602デフォルトの名無しさん

2007/12/17(月) 04:47:19

ハードウェアの構造上加減算よりシフトの方が圧倒的に単純なんだよ
小さい加算器を作ったことがあればわかるはず
クロック数が一緒ってことはあるかもしれんが、
シフトの方が遅いってことはまずないだろう

0603ヽ・´∀｀・,,）っ━━━━━━┓

2007/12/17(月) 05:39:05

ARMだと全命令にプレディケーション使えるからCレベルの単純な分岐は直列化できるよ
分岐は極端に遅いなんていうのはCellプログラマだけにしてください。

0604デフォルトの名無しさん

2007/12/17(月) 07:41:05

>>602
このケースは1bitだからその通りだけど
x86の8086-286までは、2bit以上のシフトは遅かったんだよ。
最初は直接bit数指定のインストラクションすらなかったし。

0605デフォルトの名無しさん

2007/12/17(月) 13:11:19

ttp://answers.google.com/answers/threadview?id=388350

0606デフォルトの名無しさん

2007/12/17(月) 13:13:10

>>603
単純な分岐なら、if文使ってコンパイラに任せた方が速いね。
絶対値求める時とか、NULLならreturnするとか、分岐コストかからなくていい。

0607デフォルトの名無しさん

2007/12/17(月) 14:37:02

むしろif文にbool型しかとらないJava/C#が異端なんじゃねーの？
俺もbool型オンリーの方が好きだが、スクリプト言語してるとそうじゃない方が多い気がする。

0608デフォルトの名無しさん

2007/12/17(月) 18:27:51

ifの選択肢にTrueとFalse以外なんてあり得るの？

0609デフォルトの名無しさん

2007/12/17(月) 18:33:36

if(666){//実行されます。}

0610デフォルトの名無しさん

2007/12/17(月) 19:02:56

コメントに括弧閉じ書いて意味あんの

0611デフォルトの名無しさん

2007/12/17(月) 21:34:17

if (GetMessage(...) <= 0)

で充分でね?

0612デフォルトの名無しさん

2007/12/17(月) 21:49:47

>>602
シフタってのはデータセレクタの塊だから多ビットのシフトは
シリコンの面積を喰うのよ

0613デフォルトの名無しさん

2007/12/17(月) 23:54:21

>>611
-1以外の負の値が未定義

0614デフォルトの名無しさん

2007/12/17(月) 23:54:34

シフタのないプロセッサには出会ったことが無いけどね。

0615デフォルトの名無しさん

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のプリディケーションいまいちだと思うけど。

0616ヽ・´∀｀・,,）っ━━━━━━┓

2007/12/18(火) 00:11:17

知ってるが

Cellのスカラ性能が
気に食わない

0617ヽ・´∀｀・,,）っ━━━━━━┓

2007/12/18(火) 00:45:11

分岐ヒントもBranchの15クロックくらい前くらいに入れないと駄目じゃなかったっけ
しかも二重に使うとハングする致命的なバグ持ちだから始末に困る

0618デフォルトの名無しさん

2007/12/18(火) 00:47:47

if (bResult == 0 || bResult == -1) こんなん対して食わないだろ゜

0619ヽ・´∀｀・,,）っ━━━━━━┓

2007/12/18(火) 00:52:15

SSE4.1のXMMに対する比較命令が加わったから4条件同時判定とかも便利そうだね

0620デフォルトの名無しさん

2007/12/18(火) 08:10:08

ダンゴさんが連投するとスレが引き締まるな

0621デフォルトの名無しさん

2007/12/18(火) 11:30:40

ダンゴage

0622デフォルトの名無しさん

2007/12/18(火) 20:46:31

test

0623デフォルトの名無しさん

2007/12/21(金) 07:08:36

test

0624デフォルトの名無しさん

2007/12/21(金) 07:18:07

http://www.nicovideo.jp/watch/sm1779811

0625デフォルトの名無しさん

2007/12/30(日) 10:37:00

年末あげ

0626デフォルトの名無しさん

2008/01/03(木) 18:36:52

ttp://itl.jisakuita.net/core2_mossari/1162381694.html

ダンゴさんすげえな

0627デフォルトの名無しさん

2008/01/09(水) 19:20:08

sge

0628デフォルトの名無しさん

2008/01/14(月) 22:47:23

V(･∀･)V

0629デフォルトの名無しさん

2008/01/21(月) 23:54:19

あげ

0630デフォルトの名無しさん

2008/01/22(火) 00:09:06

以下の2つの値があったとします。
x1 = 0xFF842144
x2 = 0x5400FF33

ユーザからの入力u1、u2が入力された場合
考えられるケースは以下の4つになると思います。
・u1=x1、u2=x2一致
・u1=x1一致
・u2=x2一致
・どちらとも一致しない

最低3回比較しないとどのケースか判断できないって
思い込んでるのですが
何かいいアイディアくれる人いませんか？

0631デフォルトの名無しさん

2008/01/22(火) 00:46:32

愚問だと思いますが。。

しかし、そんあ80年代前半のBASICの論理式みたいなアナクロな発想をするって
今日日奇特な人だね。

0632デフォルトの名無しさん

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不一致
がある

つまり４通り
比較は最大２回

0633デフォルトの名無しさん

2008/01/22(火) 01:21:29

その比較を10^12回通りくらい計算するつもりなら最適化もあり

0634デフォルトの名無しさん

2008/01/22(火) 01:30:35

あらかじめ
p = x1 XOR x2
の値を取得しておく
q1 = p XOR u1
q2 = p XOR u2
を得る

0635ヽ・´∀｀・,,）っ━━━━━━┓

2008/01/22(火) 01:30:56

SSE4のptest使えば一回で済む

0636デフォルトの名無しさん

2008/01/22(火) 01:54:14

>>634
得た後はどうすればいいのw？
q1とq2をどうやって使うの？

0637デフォルトの名無しさん

2008/01/22(火) 02:56:20

>>632
＞・u1=x1一致、u2=x2一致
あんた馬鹿?

0638デフォルトの名無しさん

2008/01/22(火) 11:10:15

>>635
無理だろ，あれは and と andnot だから．pcmpeqd の方が良さげ

0639デフォルトの名無しさん

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
}
}

どこも間違ってるように思えないんだが。

0640デフォルトの名無しさん

2008/01/22(火) 12:34:57

しかし、BY（文脈読めない）な奴が多いな。

ここがどういうスレかを考えれば、>>630が何を聞きたいか
多少説明不足でもだいたい分かるだろ普通w

0641デフォルトの名無しさん

2008/01/22(火) 13:13:10

ほうほう。それでそれで?

0642デフォルトの名無しさん

2008/01/22(火) 18:32:50

int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
b1 = (u1 == x1)
b2 = (u2 == x2)
return a[(b1 << 1) | b2];

0643642

2008/01/22(火) 18:33:45

× int a[] = {両方一致, 片方一致, 片方一致, 一致しない};
○ int a[] = {一致しない, 片方一致, 片方一致, 両方一致};

0644デフォルトの名無しさん

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;

結局、そのあたり何が効率的かはアセンブラで見ないといけないけど
アセンブラで出来る高速化は、リニアにしか効かないから、そんなに意味ないんだよね

0645デフォルトの名無しさん

2008/01/23(水) 20:55:34

全面的に同意．ただ２倍位速くなることもあるから最後の手としては有効．まぁ今は可能 intrinsic 使うけど．

0646デフォルトの名無しさん

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");
}}

0647646

2008/01/24(木) 15:42:18

64bit機か、内部で64bitまで計算結果を保持しているなら
32bitの割り算も出来るけど646は16bit同士です

0648デフォルトの名無しさん

2008/01/24(木) 15:52:26

GCC の中見りゃあるんじゃね？

0649デフォルトの名無しさん

2008/01/24(木) 17:46:02

>>648
gcc のカオス・スパゲッティ状態を知らぬようだな。

勧めるならせめて Small-C くらいにしとけ。
このルーチンなら工学社から出ていた
Small-C ハンドブックにもちゃんと説明されていたんだし。

0650デフォルトの名無しさん

2008/02/04(月) 20:42:37

ハッカーの楽しみ買ってきました～
これから読みますﾉｼ

0651デフォルトの名無しさん

2008/02/05(火) 23:53:51

Hacker's Delight やっと届いた

0652ヽ・´∀｀・,,）っ━━━━━━┓

2008/02/06(水) 01:12:31

俺もアレ訳本出る前ネットショップで買ったわ

0653デフォルトの名無しさん

2008/02/22(金) 06:50:56

0654デフォルトの名無しさん

2008/02/28(木) 07:49:51

0655デフォルトの名無しさん

2008/03/01(土) 13:50:55

a << 1

0656デフォルトの名無しさん

2008/03/05(水) 07:05:43

0657デフォルトの名無しさん

2008/03/11(火) 07:43:25

あげ

0658デフォルトの名無しさん

2008/03/24(月) 22:44:22

あげ

0659デフォルトの名無しさん

2008/03/30(日) 21:00:53

あげ

0660デフォルトの名無しさん

2008/03/30(日) 21:42:47

なにこのスレきもい。
でも懐かしい。

0661デフォルトの名無しさん

2008/04/06(日) 18:17:38

　　　　|
　　　　|
　　　／￣￣￣￣￣￣
　＜⌒／ヽ-、_＿_
／＜_/＿＿＿＿／

0662デフォルトの名無しさん

2008/04/06(日) 18:41:01

ダンゴさんを称えるスレというわけではありませんが、まあ、KY。

0663デフォルトの名無しさん

2008/04/06(日) 19:46:30

GCAの作者のページにビット演算が載ってたけど今いちわからん

0664デフォルトの名無しさん

2008/04/07(月) 17:04:46

ViViの作者のページにもビット演算が載ってたけどだいたい理解した
http://vivi.dyndns.org/W/254

0665デフォルトの名無しさん

2008/04/07(月) 19:44:18

>配列による状態表現よりも処理が高速になる場合が多い
この表現は凶悪だな。何故なら、高速にならなかった場合にはかなり遅くなる可能性があるからだ。

0666デフォルトの名無しさん

2008/04/17(木) 06:42:52

age

0667デフォルトの名無しさん

2008/05/01(木) 06:01:45

age

0668デフォルトの名無しさん

2008/05/01(木) 08:02:29

燃料がないな

0669デフォルトの名無しさん

2008/05/01(木) 08:50:52

16bitカラーで　5：5：5 とか 5：6：5 とか　の時代なら色々やったけどな

0670ヽ・´∀｀・,,）っ━━━━━━┓

2008/05/01(木) 18:55:25

AltiVecにも16bitカラー用の演算があったな

0671デフォルトの名無しさん

2008/05/09(金) 19:08:22

こちらのスレから誘導されて参りました。よろしくお願いします。

スレ立てるまでもない質問はここで第91刷
http://pc11.2ch.net/test/read.cgi/tech/1209716212/171

以下の条件で、32bit値のハミングウェイトが素数か否かを判定する
出来るだけ高速な方法を探しています

・入力はランダム
・（最悪ではなく）平均速度が速いことが望ましい
・0、1は素数ではない（偽になって欲しい）
・ハミングウェイトそのものの値は必要ない
・64bit拡張などは必要ない。32bit決め打ちで良い
・外部メモリはあまり使いたくない

皆様のお知恵を貸していただけませんでしょうか

0672デフォルトの名無しさん

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;
}

0673デフォルトの名無しさん

2008/05/09(金) 21:56:14

1 << 32 の結果って決まってたっけ

0674デフォルトの名無しさん

2008/05/12(月) 10:32:41

処理系定義かな。0ビットシフトになる場合と32ビットシフトになる場合が一般的だと思う。

0675デフォルトの名無しさん

2008/05/12(月) 18:51:02

まぁ 8bit, 16bit, 32bit が int の場合と、
64bit が int の場合では結果は明らかに異なるよな

0676デフォルトの名無しさん

2008/05/12(月) 20:19:59

8bitがintになることってありえるっけ

0677デフォルトの名無しさん

2008/05/12(月) 20:51:31

規格は一応-32767～32767だからないんじゃね？

0678ヽ・´∀｀・,,）っ━━━━━━┓

2008/05/12(月) 21:34:45

1ビットマシンとか4ビットマシンとかってCでプログラミング可能なの？

0679デフォルトの名無しさん

2008/05/12(月) 21:44:21

CHAR_BIT >= 8 だけど、
別に変数１つをレジスタ１つで扱えないといけないわけじゃないし
問題ないんじゃね？

0680デフォルトの名無しさん

2008/05/12(月) 21:47:55

ダンゴさんのカキコでスレが加熱したな

0681ヽ・´∀｀・,,）っ━━━━━━┓

2008/05/12(月) 21:59:19

レス番飛んでるな

0682デフォルトの名無しさん

2008/05/13(火) 11:50:54

ダとかンとかゴとか入ると飛ぶんだよな。

0683デフォルトの名無しさん

2008/05/13(火) 11:56:23

実は見えてる

0684デフォルトの名無しさん

2008/05/13(火) 12:39:16

ダンゴって名前を嫌がるのは、
体型が肉団子だからだよな。

0685ヽ・´∀｀・,,）っ-○◎●

2008/05/13(火) 12:47:46

だんごはこれだろ

━━━━━━┓がどうみたらだんごに見えるねん

あたまわるいんとちゃうか

0686ヽ・´∀｀・,,）っ鹵～＜巛巛巛

2008/05/13(火) 12:50:40

虫除けのようなものだよ

0687デフォルトの名無しさん

2008/05/13(火) 14:33:31

ダンゴさんってどんな仕事してるの?

0688デフォルトの名無しさん

2008/05/13(火) 16:51:03

名無しさんの書き込みでスレがヒートアップしたな。

0689デフォルトの名無しさん

2008/05/13(火) 18:15:31

他愛もない雑談だけどな。
と、だけ書くのもなんだから、ちょこっとマジレス。

ANSI C での int の定義は処理系依存で、CPUのレジスタ幅によるらしい。
なので、Z80 なら 8bit の筈だけど、
大体のZ80 C処理系では char=8bit, int=16bit と扱う。
なんで int は 16bit より大きいという誤解があるんだろうなぁ。
その昔は char=7bit なんで処理系もあったというので、
油断は出来ないように思うんだよ。

0690デフォルトの名無しさん

2008/05/13(火) 18:38:03

INT_MINは-32767以下、INT_MAXは+32767以上じゃないといけないと決まってる
昔の話は知らん

0691ヽ・´∀｀・,,）っ━━━━━━┓

2008/05/13(火) 19:01:17

1ビットCPUは実際にあった
http://www.d1.dion.ne.jp/~ytera/1bitcpu.htm

0692デフォルトの名無しさん

2008/05/13(火) 21:12:11

昔はやりたい放題だったかも知れないが、
今は規格に準拠した処理系であれば int >= 16 bits なのは真理。
あと、int のサイズの定義は CPU のレジスタ幅にして欲しそうな定義ではあるけど、
そう断言している訳じゃない。
実際最近でも 64-bit マシンで int = 32-bit のことがある。

0693 ◆0uxK91AxII

2008/05/14(水) 01:14:15

>>689
＞その昔は char=7bit なんで処理系もあったというので、
無い。

0694 ◆0uxK91AxII

2008/05/14(水) 01:21:20

ごめん、間違い。

0695デフォルトの名無しさん

2008/05/14(水) 03:04:09

uartと間違えたんだな

0696デフォルトの名無しさん

2008/05/14(水) 23:42:41

ハネウェルの昔のマシンとかは 6bit 単位のマシンとかがあったから、
それとの勘違いだろ。(7bit があったかどうかは知らん。)

まあ単位が 6bit なのは uart と同じ理由だが。

0697デフォルトの名無しさん

2008/05/15(木) 02:07:52

>>691
それはCPUと言うよりリレーの置き換えみたいなもの
Connection Machineのはまともな1bit CPUだけどbit sliceだから何bitにでも
化ける

0698デフォルトの名無しさん

2008/05/28(水) 00:29:01

あげ

0699デフォルトの名無しさん

2008/05/30(金) 00:17:23

11100111

こんなビットがあったとき、0が4と5ビット目に
存在するってどうやって調べるのが効率いいのかな？

個数はわかるけど位置はどうすりゃいいんだろう

0700デフォルトの名無しさん

2008/05/30(金) 00:34:24

Hacker's Delight 嫁

0701デフォルトの名無しさん

2008/05/30(金) 02:40:11

>>699
11100111 and 00011000

0702デフォルトの名無しさん

2008/05/30(金) 02:41:22

8bitなら256個のﾃｰﾌﾞﾙ持てば最速じゃね？　16bit以上なら、シフトして端のbitの0/1と
シフト回数で判別。

0703デフォルトの名無しさん

2008/05/30(金) 02:50:48

>>699
ループ

0704デフォルトの名無しさん

2008/05/30(金) 09:37:40

>>703
>>701

aビット目とbビット目が動的に変わるなら、マスク作ってandとった方が良いかもしれない。

0705デフォルトの名無しさん

2008/05/30(金) 09:47:01

>>699
問題文は正確に

0706デフォルトの名無しさん

2008/05/30(金) 11:48:47

>>699
４、５ビット目というのは変わりうるのよね？
あと個数が２個というのも変わりうるのよね？

0707デフォルトの名無しさん

2008/05/30(金) 11:51:01

>>699
ああ、あと、いつもがそんな風に左右対称とは限らないのよね？

0708デフォルトの名無しさん

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 になるまで繰り返せばいい

0709デフォルトの名無しさん

2008/06/11(水) 00:25:23

>>708
それって並列にできないですかね
無理ですよね.....

0710デフォルトの名無しさん

2008/06/11(水) 00:30:28

bit演算で128、64、32bitを扱う場合
みんなどんなふうに宣言しますか？
C/C++でのバターな方法が解りません

0711デフォルトの名無しさん

2008/06/11(水) 00:34:46

まずトラを数匹用意します。

0712デフォルトの名無しさん

2008/06/11(水) 00:41:57

あるプログラムで実際にあったコード。
普通ループではカウンタを＋＋していくと思うけど、
（iを1,2,3・・・と加算）
一回処理するごとに左に1ビットシフトしていた。
（iを1,2,4,8・・・とシフト）

普通こういうコード書きます？仕事で。

0713デフォルトの名無しさん

2008/06/11(水) 00:49:43

>>712
1989年ぐらいに見た記憶があるｗ

0714デフォルトの名無しさん

2008/06/11(水) 01:15:51

グレイコードを扱うような貧弱なCPUに対するコードなら在り得る。

0715デフォルトの名無しさん

2008/06/11(水) 01:26:18

１ビットずつスキャンしていく場合には使う。

0716デフォルトの名無しさん

2008/06/11(水) 01:27:14

>>712
普通にあるし、速度面だけでなく、その方が可読性があるものもある。

0717デフォルトの名無しさん

2008/06/11(水) 01:28:54

終了条件でいつも悩むんだけどね。

0718デフォルトの名無しさん

2008/06/11(水) 07:07:30

for( bit=1 ; bit ; bit<<=1 ) cnt += ( ( data & bit) >0 );

こういうの？

0719デフォルトの名無しさん

2008/06/12(木) 22:51:52

アセンブラで１～８回のループをシフト+キャリーでやることはあったな。

0720デフォルトの名無しさん

2008/06/12(木) 23:56:44

もしかしたらループ回数が３２かいを超えたら・・・
どうするの？

0721デフォルトの名無しさん

2008/06/13(金) 08:21:14

>>720
普通にカウントしろよｗ

0722デフォルトの名無しさん

2008/06/13(金) 11:54:06

正直別にどうでもいい
泣くしかない

0723デフォルトの名無しさん

2008/06/25(水) 13:20:16

0xC89664
の１バイト目・２バイト目の値を求める方法をお願いします。

0724デフォルトの名無しさん

2008/06/25(水) 13:24:45

>>723
貴方の小人は頭から食べるのですか？　お尻から食べるのですか？
http://www.aozora.gr.jp/cards/000912/files/4673_9768.html

0725デフォルトの名無しさん

2008/06/25(水) 19:29:14

囲碁（9路盤）のbitboardを作ろうとしています。
9x9なのでSSE2使えば128ビットレジスタ一個に収まるのでかなりの高速化が出来ると思っています。

囲碁のルールに上下左右を全て囲まれた石の塊は盤から取り除かれるというのがありますが、
これを高速に行うにはどうしたらよいでしょうか。

問題はSSE2は128ビットを一塊としたシフトが行えないことで、これのせいでどうしたらよいかわからなくなっています。
よろしくお願いします。

0726デフォルトの名無しさん

2008/06/25(水) 19:48:23

モンテカルロ木の実験ですか?

0727デフォルトの名無しさん

2008/06/25(水) 20:02:15

>>726
そうです。
モンテカルロはスピード命らしいので、SSEを使えないかと思っています。

0728デフォルトの名無しさん

2008/06/25(水) 21:11:08

左シフトなら paddq である程度代用出来るだろ

0729デフォルトの名無しさん

2008/06/25(水) 21:49:09

paddqって64ビットの境目で切れ目が出来てしまいませんか。

0730デフォルトの名無しさん

2008/06/25(水) 21:53:24

128ビット丸々だとバイト単位の命令しかないからねぇ。
x64環境を使っていいのならビット単位をやめてバイト単位にして
16本のXMMレジスタを9本使って9x9にした方がいいんじゃないかな？

0731デフォルトの名無しさん

2008/06/25(水) 22:23:24

それならビット単位でshort[9]でもよさそうですが、
バイト単位にしたほうが有利なんですか？

0732デフォルトの名無しさん

2008/06/25(水) 23:18:33

ビット単位で操作できないから困ってたんじゃなかったの？

0733デフォルトの名無しさん

2008/06/26(木) 06:48:29

レジスタを9本も使うなら32ビットのレジスタでも9x9の盤は収まってしまいます。
その場合、ビット単位の操作は可能です。

x64でレジスタが16本あったとしても通常のレジスタを9本も占めるというのは考えにくいですが、
ＸＭＭレジスタなら9本使っても支障ないということでしょうか？

0734デフォルトの名無しさん

2008/06/26(木) 09:01:44

>>729
最大9bitしかシフトしないでしょ？　なら　境界にデータを置かなければいいでしょ

あるいは16bitを１列にしてレジスタ２つにしたらどう？

0735デフォルトの名無しさん

2008/06/26(木) 10:08:36

>>733
x64で汎用レジスタが増えたとはいえ9本も使えばループや分岐に支障が出ると思うよ。
その点XMMレジスタなら浮動小数点演算しなければ基本的に空いてる。

0736725

2008/06/26(木) 19:15:01

725です。

すいません。
皆さんにレスしていただいておいて申し訳ないのですが、
高速化について調べていたらGPGPUというのが見つかりました。

グラボに計算をさせるというものなのですが、上手くツボにはまれば
CPUの何十倍もの速度がでるそうです。

囲碁がはたしてグラボに計算させるのに向いてるのかどうかわかりませんが、
SSEは一旦忘れて、GPGPUについて調べてみようと思います。
グラボも３～４万だせば結構いいのが買えるみたいです。

とりあえずGPGPUスレとCUDAスレにいって雰囲気つかんできます。

皆さんのレスには感謝しています。
失礼しました。

0737デフォルトの名無しさん

2008/06/26(木) 19:47:50

そっち行ってもいいならFPGAっていうテもあるかもしれん。

0738デフォルトの名無しさん

2008/06/26(木) 21:47:07

5年ほど前にFPGAでオセロの石を返す部分を作ったが
普通にCPUで計算するより遅かった

0739デフォルトの名無しさん

2008/06/26(木) 22:43:05

>>736
CUDAするなら前もって、GPUに計算させたい部分
設計しておけ
わしは今日から3日でモンテカルロをCUDAで解けるように
勉強する

0740725

2008/06/27(金) 00:03:02

>>739
どもです。

ところで最新ハイエンドGPUはピーク性能1TFLOPS超えるらしいですね。
ＨＤＤもテラバイトの物が出てるし、時代はもうテラなんですねぇ。

0741デフォルトの名無しさん

2008/06/27(金) 00:18:19

>>740
Radeon HD3870とGeforce9800GTXもってるけど
両方とも労せず2000スレッド以上生成して並列に計算できるよ

0742デフォルトの名無しさん

2008/06/27(金) 00:32:16

>>725
一命令ではできないが，シフトしたいビット数を n として n/8 と n%8
とに分けてシフト命令使って後で合成すれば可能

0743デフォルトの名無しさん

2008/06/27(金) 04:00:39

>>738
enumの様に贅沢にintを丸々一つ石に配分した方が良かったかもしれないね。

0744デフォルトの名無しさん

2008/06/27(金) 07:18:19

ベクトル演算を利用するなら　閉曲線の内側か外側の判定で巻付判定法を応用するといいように思うな

ビット演算じゃないけど

0745デフォルトの名無しさん

2008/07/11(金) 01:01:51

あげ

0746デフォルトの名無しさん

2008/07/20(日) 15:56:27

う

0747デフォルトの名無しさん

2008/07/20(日) 20:41:05

今どきビット演算で高速化とかｗ

0748デフォルトの名無しさん

2008/07/20(日) 23:07:22

プログラミングマニュアル1・基本仕様ガイド
の
・式

ってとこに詳しく書いてるだろ...読みもしないで不思議とか言うな

0749デフォルトの名無しさん

2008/07/20(日) 23:07:59

誤爆すいません

0750デフォルトの名無しさん

2008/07/22(火) 10:17:23

こやつめ!

0751デフォルトの名無しさん

2008/08/01(金) 03:07:44

2^a　を渡されたときaを求める方法で何かいい物はありませんか？
なるべくループやlogを使わない物がいいです

0752750

2008/08/01(金) 03:26:58

>>751
追記、1≦a≦9

0753デフォルトの名無しさん

2008/08/01(金) 03:27:44

>>752
自分の名前間違えた>>750じゃなくて>>751

0754デフォルトの名無しさん

2008/08/01(金) 04:04:46

５１３個の配列持って、その中に１～９を入れておく。[1]=なし、[2]=1、[3]=なし、[4]=2、・・・
[512]=9　演算はこれが最速。

0755デフォルトの名無しさん

2008/08/01(金) 04:06:47

サイズが問題なら、
if( n & 0x200 ) return 9;
if( n & 0x100 ) return 8;
・・・
if( n & 0x002 ) return 1;

0756デフォルトの名無しさん

2008/08/01(金) 04:15:16

x86ならBSF

0757デフォルトの名無しさん

2008/08/01(金) 04:39:50

char bit[256] = {1,2,0,3,0,0,0,4, 略 };

bsf(int n) {
int r;
if ((r = bit[n&255])) return r;
n >>= 8;
if ((r = bit[n&255])) return r + 8;
n >>= 8;
if ((r = bit[n&255])) return r + 16;
n >>= 8;
if ((r = bit[n&255])) return r + 24;
return 0; //解なし
}

0758デフォルトの名無しさん

2008/08/01(金) 04:41:33

こんなのどうよ?
bsf(bits){
bits-=1;
int num;
num = (bits >> 1) & 03333333333;
num = bits - num - ((num >> 1) & 03333333333);
num = ((num + (num >> 3)) & 0707070707) % 077;
return num;
}

0759デフォルトの名無しさん

2008/08/01(金) 04:52:26

>>754-758
ありがとうございます。みんなカッコイイ

0760デフォルトの名無しさん

2008/08/01(金) 05:52:52

>>757は
char bit[256] = { 0,1,2,0,3,0,0,0, 4,0,0,0,0,0,0,0, 略 };
の間違いだった。
んで結果を-1すれば合うんじゃないかな。

0761デフォルトの名無しさん

2008/08/01(金) 06:23:57

こんなんでどよ
int f(unsigned n){
int a=1;
unsigned b;
n>>=2;
b = n>>4;if(b)a+=4,n=b;
b = n>>2;if(b)a+=2,n=b;
return a+n;
}

0762デフォルトの名無しさん

2008/08/01(金) 10:45:43

"_\0\5\1\10\6\2__\4\7_\3"[n*0xCA030FF>>28];

0763デフォルトの名無しさん

2008/08/01(金) 14:50:59

お前頭いいなー、でも
"_\1\6\2\011\7\3__\5\010_\4"
じゃないか

もう少し小さいハッシュもあった
"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];

0764762

2008/08/01(金) 16:32:34

あー間違えてたーthx
そしてそっちのハッシュのほうが優れているね。

0765デフォルトの名無しさん

2008/08/01(金) 16:55:45

なるほど、ハッシュってそういう使い方するんだ。

0766デフォルトの名無しさん

2008/08/01(金) 17:47:48

>>762-763
異次元過ぎてついて行けないのだが解説頼む

0767デフォルトの名無しさん

2008/08/01(金) 21:25:31

俺もわかってないが
gperfとかで完全ハッシュ関数を作るのと同じように
(文字列ではなく)特定の数字から対応する特定の数値への完全ハッシュ関数を作っているんだと思う。
どうやって導いたかなんて知らん。

0768デフォルトの名無しさん

2008/08/02(土) 01:40:13

へええ
左シフトしたときに
あるビット範囲（この例だと28ビット目から31ビット目）が
シフト回数ごとにバラけるようにしているのか

シフト回数　　(n*0x5300000)のbit28～31の値
　　1　　　　　　　　0
　　2　　　　　　　　1
　　3　　　　　　　　2
　　4　　　　　　　　5
　　5　　　　　　　　10
　　6　　　　　　　　4
　　7　　　　　　　　9
　　8　　　　　　　　3
　　9　　　　　　　　6

んで配列テーブルをlookupすると。

完全ハッシュ関数って、元が異なれば必ず先が異なる関数のことだっけ。
じゃないとこれ使えないよな。

小さいというのは先の範囲、つまり今回は28～31の４ビットのことか。
確かに小さいほうがメモリとキャッシュに優しいですな。

という感じであってますか。

>どうやって導いたかなんて知らん。

俺も知りたい。

0769デフォルトの名無しさん

2008/08/02(土) 01:52:05

頭良すぎる

0770デフォルトの名無しさん

2008/08/02(土) 01:56:27

2chってすげーな

0771デフォルトの名無しさん

2008/08/02(土) 10:03:58

ビット演算ってたしかにすごいけど、
ソースに組み込むときは、その演算の意味とメリットなど
ビット演算を導入した経緯や思想も書いてほしい・・・

ソース理解に時間がかかったり、修正が大変・・・
まあ、俺がお馬鹿なのかもしれないけど。

あと、763って751からの流れなんですか？
それとも別の流れ？

0772デフォルトの名無しさん

2008/08/02(土) 10:14:13

最後の2行から見ても明らかに

>まあ、俺がお馬鹿なのかもしれないけど。

が正解。

0773デフォルトの名無しさん

2008/08/02(土) 10:17:05

このスレって頭のいい奴もいるけど、
771みたいなバカもいる。
バカはROMっていろ！死ね771！！

0774それは俺か (w

2008/08/02(土) 10:59:13

まあ、バカにレスする奴はもっとバカだけどな。

0775デフォルトの名無しさん

2008/08/02(土) 11:02:09

1、2、4、8、16、32、64、128、256、512の完全最小ハッシュ値を作る。
ttp://www.ic-net.or.jp/home/takaken/nt/slide/hash.html
これか？
>>762は本当に頭がいい。>>763の書き込みがなかったら
意味も解らずスルーするところだった。

0776デフォルトの名無しさん

2008/08/02(土) 12:58:48

512の完全ハッシュを作ってそれを1～9のテーブルに掛けるって事？
分かった気がする。

0777デフォルトの名無しさん

2008/08/02(土) 13:59:12

>>775
でも、保守する奴が >>762 みたいに頭いいとは限らんから、
仕事のプログラムなら >>754-755 あたりのほうがいいと思う。

0778デフォルトの名無しさん

2008/08/02(土) 14:04:14

当たり前。こんなのは所詮パズル。商用コードでこんなの書けない。
>>762みたいなのが許されるのは趣味のプログラミングだけだよ。

0779デフォルトの名無しさん

2008/08/02(土) 16:19:14

後は極端に処理速度がネックになってるところとか、
ビックリするほど容量が無いプラットフォームとか、
コンパイラが準備されてなくてアセンブラで書かなきゃいけないような場合、
更にRISCみたいに見た目と実行順が違うような環境だと
読む量が少ない短いコードが逆に役に立つ。
自慢を理由に書くと間違いなく死を招く。

0780デフォルトの名無しさん

2008/08/02(土) 16:20:19

コメントで書いておけば十分じゃないかな。
今でもまだまだ、速度やサイズ重視の分野はあるし。だいぶ少なくはなっているけど。

0781デフォルトの名無しさん

2008/08/02(土) 16:32:12

現状、用途として大きそうなのはシェーダー周りか。

0782デフォルトの名無しさん

2008/08/02(土) 16:36:45

画像処理ならいくらでも速度欲しいけどな

0783デフォルトの名無しさん

2008/08/02(土) 16:49:03

昔、VUアセンブラの実装をしたが、ライブラリの増加により俺の約700byteのプログラムが
入らなくなり削りに削って「400byteだけ下さい！」と上司に嘆願したのは懐かしい思い出。

0784デフォルトの名無しさん

2008/08/02(土) 18:57:37

>>777
それは同意だけど、 >>762 のエッセンスを抜き出して、わかりやすくすれば
いいんじゃないかな

おそらく、2^a を掛けると aビット左シフトする、というのは誰にも自明だけど
１～９の値にマップするマジック定数がややトリッキーかと

なら、見た目にわかりやすいようシフト数を４倍にして、（ついでに右シフトにして）
こんな感じでどうだろうかね(64ビット整数が使えることが前提だけど＾＾）

/* assume that n is 2^a (1<=a<=9) */
　return (0x9876543210LL / ( n * n * n * n )) & 0xf;

0785デフォルトの名無しさん

2008/08/03(日) 02:24:01

一番右の1を探すとき~a&(a-1)でできますよね、じゃあ一番左の1を探すときは何かありませんか?

0786デフォルトの名無しさん

2008/08/03(日) 02:37:33

掛け算が４回・割り算が１回ってのが、演算量的に・・・　俺が8bitに慣れてるからかな？
64bit整数があるにしても、nが32bitならn*nで64bitでしょ。中間結果でbitが失われるんじゃ？

0787デフォルトの名無しさん

2008/08/03(日) 02:40:55

>>785 754とか755じゃダメなの？もっと速い／小さいのってこと？

0788デフォルトの名無しさん

2008/08/03(日) 02:55:56

>>785
関係ないがa&(-a)で右端の一ビットを得られるぞ、左端は無理じゃないか

0789デフォルトの名無しさん

2008/08/03(日) 03:17:47

http://www.nminoru.jp/~nminoru/programming/bitcount.html

0790デフォルトの名無しさん

2008/08/03(日) 03:41:51

>>787-789
どうもです、今見た資料に左端を操作する命令列は存在しないって書いてあったorz

0791デフォルトの名無しさん

2008/08/03(日) 03:56:21

左右反転するビット演算子でもあればね

0792デフォルトの名無しさん

2008/08/03(日) 03:59:50

a = ( ( a >> 16 ) & 0x0000ffff ) | ( ( a << 16 ) & 0xffff0000 );
a = ( ( a >> 8 ) & 0x00ff00ff ) | ( ( a << 8 ) & 0xff00ff00 );
a = ( ( a >> 4 ) & 0x0f0f0f0f ) | ( ( a << 4 ) & 0xf0f0f0f0 );
a = ( ( a >> 2 ) & 0x33333333 ) | ( ( a << 2 ) & 0xCCCCCCCC );
a = ( ( a >> 1 ) & 0x55555555 ) | ( ( a << 1 ) & 0xAAAAAAAA );

0793784

2008/08/03(日) 17:00:12

>>786
もちろん変数n は64ビット長
LP64なら long型だと思ってもらえばいいです

演算量については、いまどきの投機実行するCPUなら
下手に条件判定入るよりは速いと思うけど、・・・まあ状況次第ですね

0794デフォルトの名無しさん

2008/08/03(日) 17:25:07

ｎが64bitでも、n*n*n*n の中間結果はbit失われるでそ。

0795デフォルトの名無しさん

2008/08/03(日) 18:31:31

でも、仕事に使うとなると、
「シンプルにしようや」
で終わってしまうんですよね～
そうすると、754や755に落ち着くのかな・・・

0796デフォルトの名無しさん

2008/08/03(日) 19:39:21

そりゃそうだよ。

よほど特段の理由が無い限り、シンプルが一番。

0797デフォルトの名無しさん

2008/08/03(日) 19:51:28

裸が一番いいのと一緒だ

0798デフォルトの名無しさん

2008/08/03(日) 21:10:39

>>794
2^9まででしょ？

0799デフォルトの名無しさん

2008/08/03(日) 21:12:54

は？

0800デフォルトの名無しさん

2008/08/03(日) 21:51:46

0x1 * 0x1 => 1
0x3 * 0x3 => 9
0x7 * 0x7 => 0x31
0xf * 0xf => 0xe1
0xff * 0xff => 0xfe01
0xfff * 0xfff => 0xffe001
0xffff * 0xffff => 0xfffe0001
0xfffff * 0xfffff => 0xffffe00001

これに規則性みたいなものを感じるんですが、
何か法則があるんでしょうか？

0801デフォルトの名無しさん

2008/08/03(日) 21:54:51

初めの3つはともかく、
9*9=81
99*99=9801
999*999=998001
と同じようなもんだろ

0802デフォルトの名無しさん

2008/08/03(日) 22:06:41

よくわからんが、ビット演算とかって、日本人よりも
インド人のほうが面白い発想しそうだね

0803デフォルトの名無しさん

2008/08/03(日) 22:09:36

>>800-801
２進数に考えれば、最初から綺麗に並ぶよ。

1 * 1 = 1
11 * 11 = 1001
111 * 111 = 11001
1111 * 1111 = 11100001
11111 * 1111 = 1111000001

0804デフォルトの名無しさん

2008/08/03(日) 22:16:49

0xffff * 0x10000 => 0xffff0000
0xffff0000 - 0xffff => 0xfffe0001
特に面白い事実はなさそうだが

0805デフォルトの名無しさん

2008/08/03(日) 22:21:59

99*99=9801
これが国民機ナンバーの正体かー
すると8801は？
93.8136 * 93.8136 = 8800.99
収束しないのか

0806デフォルトの名無しさん

2008/08/03(日) 22:22:36

収束？

0807デフォルトの名無しさん

2008/08/03(日) 22:25:25

ごめん適当言った

0808デフォルトの名無しさん

2008/08/03(日) 22:34:48

無理数ね。

0809デフォルトの名無しさん

2008/08/03(日) 23:10:51

λ... PC-8001, PC8201, PC-6001, &c. ...

0810デフォルトの名無しさん

2008/08/03(日) 23:48:03

獣の数字にまつわる屁理屈と同じようなもんだな
あえて8801に意味を見出すなら99*99-1100とかなんとか

0811デフォルトの名無しさん

2008/08/03(日) 23:49:53

9801-1100 = 8701だな
俺頭大丈夫ｋ

0812デフォルトの名無しさん

2008/08/04(月) 00:08:26

PC9801が長いこと繁栄したのは99*99=9801
こういった力(ちから)を持つ数字が隠されていた影響に違いない。
その証拠に型番が9821に変わろうとしたとたん没落した。
きっと9801のままなら永遠の存在だったんだよ。

0813デフォルトの名無しさん

2008/08/04(月) 00:11:55

>>798 そうか、9bitのハッシュのエレガントな解法だったのね。ごめん。
ハッシュって、必要の都度、bit数見極めて作らなきゃいけないんだな・・・

0814デフォルトの名無しさん

2008/08/04(月) 01:24:27

実際に仕事でも使用可能な、
1.実用性がある
2.比較的わかりやすい
ビット演算のアルゴリズムって何だろうね・・・

0815デフォルトの名無しさん

2008/08/04(月) 01:50:11

名前がつくぐらい有名になればいいんじゃないかな。
例えばコメントに
// 762氏ハッシュ
とか書けるぐらいに。

0816デフォルトの名無しさん

2008/08/04(月) 01:56:23

すみません、
＞"\1\2\3\010\6\4\011__\7\5"[n*0x5300000>>28];
の頭の"\1\2\3\010\6\4\011__\7\5"がいまいち良くわかりません。

0817デフォルトの名無しさん

2008/08/04(月) 02:06:28

ただの文字列リテラルだよ

0818デフォルトの名無しさん

2008/08/04(月) 02:06:59

コメントに、「ハッシュがどうの」なんて書く奴ばっかだからダメなんだよ。
コメントに絶対に書かなきゃいけないのは、>>751-752だよ。
どういう実装をしたかのコメントなんて二の次三の次。

それなのに仕様のコメントを怠ったままで「すげーテクニック使ってるんだぜ」的なコメントを残しても意味なし。
そんなものを残すぐらいなら、(最低限の>>751-752の他に)assertでも使った範囲チェック入れとけ。

もちろん、>>762のやり方に対するコメント(完全ハッシュ関数とテーブル)はあった方が良い。
けど、仕様についてのコメントの方がはるかに重要。

0819デフォルトの名無しさん

2008/08/04(月) 03:06:57

日本語でおｋ

0820デフォルトの名無しさん

2008/08/04(月) 03:45:03

日本人でおｋ

0821デフォルトの名無しさん

2008/08/04(月) 04:32:52

二本イレマスカ？

0822デフォルトの名無しさん

2008/08/04(月) 04:59:25

イマレス

0823デフォルトの名無しさん

2008/08/04(月) 08:02:17

#if 0 // オリジナルのロジック
...;
#else // 速度重視で書き換え
...;
#endif

0824デフォルトの名無しさん

2008/08/04(月) 08:15:04

"..."[...]という書き方をこの流れで始めて知った

何でこのスレにいるかって？
知るために見ているのさ

0825デフォルトの名無しさん

2008/08/04(月) 09:53:07

K&Rの頃のCをやってた人間からすれば常識

0826デフォルトの名無しさん

2008/08/04(月) 12:37:57

>>816 文字リテラル "abc"とかならキャラ型の配列だって判るでしょ。
スペース（0x20）より小さい値のcharは「\８進数」で書く約束になってる。
"\1\2\3・・・"は、char xxx[ ]={ 1, 2, 3, ・・・, 0 };という配列が生成される。

0827デフォルトの名無しさん

2008/08/04(月) 13:33:40

>>826
＞スペース（0x20）より小さい値のcharは「\８進数」で書く約束になってる。
なってない。

0828デフォルトの名無しさん

2008/08/04(月) 17:24:05

\001 \002 \017 とかだよ。　Hexの場合は \xhh と書く約束になってる。
俺のはLSIC85とか adUc51とか、クミコ系ばっかりで、ANSIは知らないけど。

0829デフォルトの名無しさん

2008/08/04(月) 18:13:00

0x20以上の値で使ってはいけないという決まりもないわけで。

0830デフォルトの名無しさん

2008/08/04(月) 22:15:16

最下位8bitについてなら左右を逆転するコードあった筈
こんな感じだったと思うけど、よく覚えてないや

x:src y:dest
s=(x*0x02020202)&0x84422010
t=(x<<3)&0x420
y=(s+t)%1023

0831デフォルトの名無しさん

2008/08/04(月) 22:49:39

>>792で既出だべ。

0832デフォルトの名無しさん

2008/08/04(月) 23:59:20

>>828
\n \t \r とかもあるわけで。

0833デフォルトの名無しさん

2008/08/05(火) 00:45:34

>>832
は？

0834デフォルトの名無しさん

2008/08/05(火) 01:21:35

文字リテラルが配列の名前？？？
どうも「文字リテラル＋[]」が良くわからん。
ビット演算うんぬんではなく・・・
C言語でこれを書いてコンパイルが通るのか？

どうもこのスレに付き合うには、大学などできちんと学ぶか
元々、この手のことが好きじゃないとついていけませんね・・・

社会人になってから、プログラムを覚えたアホアホな俺の
プリンみたいな脳みそでは、だめかorz

0835デフォルトの名無しさん

2008/08/05(火) 01:37:17

なんでワカラン？？？　大学とか関係ないぞ。

char * buf = "01234567";
char a = buf[0];

が判れば、

char a = "01234567"[0];

だって判るだろ。

0836デフォルトの名無しさん

2008/08/05(火) 01:41:46

char a = 0["01234567"];

こんなのもある。これが直感的に納得しづらいというのはワカランでもないけど、

char a = "01234567"[0];

こっちは普通だべ。

0837デフォルトの名無しさん

2008/08/05(火) 09:00:56

>>834
>元々、この手のことが好きじゃないとついていけませんね・・・
当たり前だと思うんだが。

0838デフォルトの名無しさん

2008/08/05(火) 10:50:52

文字列定数がメモリ空間に配置されている状態をイメージできていないんだな。
プロセスメモリエディタかバイナリエディタと睨めっこでもしてみればいいんじゃね。

0839デフォルトの名無しさん

2008/08/05(火) 12:25:02

文字列リテラルは、コンパイラがDATAやTEXTのようなセグメントに配置して
プログラムの中に埋め込まれるちょっと特殊なchar[]にすぎん。
"hoge"とか書いた場合、これはそういう配列を暗黙にどっかに確保しろよと
コンパイラに言っているのと同時に、式の中で評価されるときは、その（無名の）
char配列の名前と同等に扱われる。

要はchar[]なのだから、char*な変数に文字列リテラルを代入したり
printf()のような関数に文字列リテラルを引数として渡したり、ということは
普通に・当然のようにやっているはずだ。
さすがにprintf("hello, world"); というコードを見たことが無いとは言わせない。

ならば、[]演算子を適用できるということも当然分かるはずだな。
多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。

0840デフォルトの名無しさん

2008/08/05(火) 12:32:50

>>834
[]を特殊なものだと思うからいけない。ただの演算子だ。
a[b]とあったら必ず*(a+b)と置き換えが可能だから、ただのポインタ演算とデリファレンスに成り下がるだろ。
デリファレンスするために、aかbのどちらかはポインタでもう一方は整数でないといけないだけだ。

例えばchar a = 0["01234567"]とあったらchar a = *(0 + "01234567")になり、即ちchar a = *("01234567")であり、char a = "01234567"[0]だ。
これでも理解しにくかったら、全部一時変数にしてしまえばいい。
const char * p = "01234567"; int i = 0; として、char a = p[i]; ならわかるだろ。。

0841デフォルトの名無しさん

2008/08/05(火) 13:15:16

おそらくは、
　配列の名前[インデックス]
のように教えてる参考書の類が悪いんだろう。

0842デフォルトの名無しさん

2008/08/05(火) 15:15:59

>>834
このスレ開いただけでも望みはある！

0843デフォルトの名無しさん

2008/08/05(火) 18:04:55

すごいな。叩きが日常の2chで、ｼﾛｰﾄにここまで優しいのは、久しぶりに見た。

0844デフォルトの名無しさん

2008/08/05(火) 19:53:06

>>838
メモリをイメージする訓練も大切だが、
もっと抽象的に捉える訓練も忘れないで欲しいな。

0845デフォルトの名無しさん

2008/08/05(火) 20:05:18

そうだなー、最近そういうトレーニング怠ってるかも…俺。

0846デフォルトの名無しさん

2008/08/05(火) 21:13:44

>>841
真の文法を書いてる本は稀少なのかね。

0847デフォルトの名無しさん

2008/08/05(火) 21:27:48

>>846
真の文法を書いている本でも、いでおしんくらてっぃくなところは
はしょっているか、読み取れないようにしてるのが多いと思う。
実際、俺なんか、
int typedef integer;
なんて構文が許されるなどとはイソターネットで初めて知った。

0848デフォルトの名無しさん

2008/08/05(火) 21:44:04

なるほど、許されない理由がないから許されるんだな。

0849デフォルトの名無しさん

2008/08/05(火) 21:47:55

もしかして：void main(void)

0850デフォルトの名無しさん

2008/08/05(火) 22:11:34

>>846
真の文法をサポートする本とはLinuxのことである。
Linux以外は紛い物である。

0851デフォルトの名無しさん

2008/08/06(水) 00:58:33

>>833
いや、意味が理解できないなら別にいいんだ。

>>839-841
C/C++ に毒されすぎ (w

文字列と文字の配列が互換の言語はあまり多くないから、
"abcd"[0] を >>834 が奇異に感じるのも無理は無いよ。

0852デフォルトの名無しさん

2008/08/06(水) 00:59:35

[]はmonadの一種でしょ

0853デフォルトの名無しさん

2008/08/06(水) 01:15:22

みなさん、あほな俺に丁寧にありがとう。
さすがに理解できました。

＞多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。
そうですね。はじめてみました。

なんかすっきりしました。
皆さんありがとうございました。

なんかビット演算って難しそうですけど、面白そうですね。
私も、最近処理速度を意識したコードを書く機会があるので
色々参考にします。
（クロックが25KHzなので、処理速度を意識しないといけないんですよ）

0854デフォルトの名無しさん

2008/08/06(水) 01:31:44

ずいぶん遅くない？　8ビット機のときもMHzだったが。。。

0855デフォルトの名無しさん

2008/08/06(水) 09:28:35

ケルビン・ヘルツという単位は寡聞にして知らない。

0856デフォルトの名無しさん

2008/08/06(水) 21:19:11

＞ずいぶん遅くない？
そうなんですよ。1サイクル40usなので、ビット操作（ビットクリアやビットセット）で
7サイクル取られるので、7*40=280us=0.28msもかかるんですよね・・・

0857デフォルトの名無しさん

2008/08/06(水) 21:30:37

えー！　そりゃ遅い。なんだろ。FPGAかなんかか。
最近は組み込みの分野でもJAVAだったりするが、まだまだCの出番はあるってことか。

0858デフォルトの名無しさん

2008/08/06(水) 22:00:42

ボタン電池1個で半年動かすようなものなんじゃね？

0859デフォルトの名無しさん

2008/08/06(水) 22:06:20

>>857
> まだまだCの出番はあるってことか。

て言うか、アセンブラの出番だと思うけど。

0860デフォルトの名無しさん

2008/08/06(水) 22:17:37

Cで書く予定です。アセンブラでは保守のことを考えると難しいので。
如何にCで効率の良いコードを書くか。

クロックを遅くしているのは消費電流の低減のためです。
普段は32MHzで動作しますよ。

0861デフォルトの名無しさん

2008/08/09(土) 17:23:46

>>767-768
ちょっと遅くなったが、求め方が解った。
今回は2^1～2^9だからちょっと変則的なんだが、概念としてはM系列の応用みたい。
なるほどねー。
http://slashdot.jp/~Tellur52/journal/448479

0862デフォルトの名無しさん

2008/08/09(土) 17:25:18

>>861
お前ここに糞スラのURL張るの禁止されていること
しらんのか？

0863デフォルトの名無しさん

2008/08/09(土) 17:27:12

スラッシュドット禁止ってどんだけ情報弱者なんだよ。

え？あっちから拒絶してんの？

0864デフォルトの名無しさん

2008/08/09(土) 17:27:38

あれ？　板ルール？
スマンかった。忘れて。

0865861

2008/08/09(土) 17:31:07

>>863
あっちも出入りしているけど、そういうことはないと思う。
ここの板ローカルのルールなのかね？
ここも長年見ているが、あまり聞いたことないけど。

0866デフォルトの名無しさん

2008/08/09(土) 18:01:21

>>862はさすがに釣りだろお前ら釣られ杉

0867デフォルトの名無しさん

2008/08/09(土) 18:40:27

ぐぐってもあまりいいページがないんだが、どこかに解説ない？＞M系列

0868デフォルトの名無しさん

2008/08/10(日) 02:54:03

周期2^p-1ビットの列があって、そこからpビットを切り出すと、オール0以外の全てのパターンが現れる

p=3の場合のM系列は例えばこう。
0011101
↓ (周期2^3-1=7で同じパターンの繰り返し)
001110100111010011101...
上の桁から3ビットを切り出すと、
001 (1)
_011 (3)
__111 (7)
___110 (6)
____101 (5)
_____010 (2)
______100 (4)

1～7まで全部出るだろ。これに000だけ追加すればおｋ。
これだけだと順番がバラバラなので、テーブルと組み合わせる。
↓この文字列リテラルの部分な。
"xxxxxxx"[(ハッシュ計算式)]
すると、>>762-763になりますよ、と。ビット溢れによるマスクなども組み合わせているが。

0869デフォルトの名無しさん

2008/08/10(日) 03:11:08

任意の長さのシフトレジスタで適当なタップを選んでフィードバックすれば
最長系列（Ｍ系列）が得られるんだが，
このタップが整数論の方の原始多項式から求められるというのは覚えてる

0870デフォルトの名無しさん

2008/08/10(日) 16:08:47

Cで保守の事を考えずに書いたときに保守しやすいのかといわれればもちろんNOだろ
素人が下手にCで最速コード書くと後で自分で読めないから、最初からアセンブリでやったほうがいいと思う

マクロが使えれば読みやすくなるのも事実だしな
MASMだと、アセンブリの癖にIFだのELSEだの使える。マクロがなければCでプリアセンブラを書けばいいし

0871870

2008/08/10(日) 16:10:30

安価書き忘れ
>>860

0872デフォルトの名無しさん

2008/08/10(日) 17:38:03

CPU換えたときの心配してるんだったらC

0873デフォルトの名無しさん

2008/08/10(日) 17:55:59

スレタイも読めないバカが多いね。
移植性や保守性を犠牲にしてでも高速化しようってのが趣旨なのに。

0874デフォルトの名無しさん

2008/08/10(日) 18:16:42

書かれてもいない事が見えるバカが居るんだね

0875デフォルトの名無しさん

2008/08/10(日) 18:25:56

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

0876デフォルトの名無しさん

2008/08/10(日) 18:31:54

やばいですやばいです
ちょっと暴走して勃起が止まりません
リセットできないどうしよう

0877デフォルトの名無しさん

2008/08/10(日) 18:35:44

適切な勃起フラグを提げろ。

0878デフォルトの名無しさん

2008/08/10(日) 19:02:20

トシなのでフラグ立ちません！　どうしよう！

0879デフォルトの名無しさん

2008/08/10(日) 19:20:29

(´･ω･`)知らんがな

0880デフォルトの名無しさん

2008/08/10(日) 19:20:34

＞移植性や保守性を犠牲にしてでも

そりゃビット演算すれば多少は移植性が犠牲になるだろうけど、
それだけならぜんぜん問題にはならない。
所詮フラグなんて１本しかないんだからな。
ただまあ、
大きさはいろいろだから互換性がない場合も確かにある。

0881デフォルトの名無しさん

2008/08/26(火) 15:29:02

　＊　　　　+　　　　巛ヽ
　　　　　　　　　　　　〒　!　　　+　　　　。　　　　　+　　　　。　　　　　＊　　　　。
　　　　　+　　　　。　 | 　|
　　　＊　　　　+　　 /　/　　　イヤッッホォォォオオォオウ！
　　　　　　 ∧＿∧ /　/
　　　　　　（´∀｀　/　/　+　　　　。　　　　　+　　　　。　　　＊　　　　。
　　　　　　,-　　　　　ｆ
　　　　　 / ュヘ　　　　| ＊　　　　+　　　　。　　　　　+　　　。　+
　　　　　〈＿｝）　　　|
　　　　　　　 /　　　　! +　　　　。　　　　　+　　　　+　　　　　＊
　　　　　　 ./　　,ヘ　 |　　　　　　このスレッドは８８０を超えました。
　ガタン　||| j　　/　|　 | |||　　　　　　　　次レスも…BITクオリティ！！
――――――――――――　　　　　　　 http://pc8.2ch.net/tech/

ああ暇だ

0882デフォルトの名無しさん

2008/08/27(水) 20:01:38

ちょっとリンク張らせてクレ。
http://science6.2ch.net/test/read.cgi/math/1209732803/
の427に問題を投稿したんで、暇ならチャレンジしておくれ。

0883デフォルトの名無しさん

2008/08/27(水) 20:36:01

算数得意だけど数学は苦手

0884デフォルトの名無しさん

2008/09/04(木) 14:51:58

http://chessprogramming.wikispaces.com/Bitboards
ここまでくると、なにがなにやら

0885デフォルトの名無しさん

2008/09/04(木) 15:15:42

簡単じゃん

0886デフォルトの名無しさん

2008/09/13(土) 20:24:38

(･∀･) ｶﾞｯｰ

0887デフォルトの名無しさん

2008/09/14(日) 13:55:19

発音できません＞＜

0888デフォルトの名無しさん

2008/09/16(火) 23:19:16

ん？ヌルポはどこ？

0889デフォルトの名無しさん

2008/09/17(水) 01:25:58

>>888
888

0890デフォルトの名無しさん

2008/09/17(水) 16:29:38

又ﾉﾚ木ﾟ

0891デフォルトの名無しさん

2008/09/17(水) 16:31:31

ガッ

0892デフォルトの名無しさん

2008/09/17(水) 17:12:10

力ﾞっ

0893デフォルトの名無しさん

2008/09/17(水) 19:24:05

>>890
その表記、キモすぎるｗ

0894デフォルトの名無しさん

2008/09/27(土) 11:01:16

整数間のキャスト演算について教えてください。
例えば、2の補数で表される4bitの値を8bitに変換する場合、

正の値： 0001 -> 0000 0001 # 最上位bitが0なら上位bitに0000を補う
負の値： 1110 -> 1111 1110 # 最上位bitが1なら上位bitに1111を補う

bit8 = (bit4 & 0x8) ? (bit4 | 0xF0) : bit4;

逆の変換は、

正の値： 0000 0001 -> 0001 # 上位4bitを削除
負の値： 1111 1110 -> 1110 # 上位4bitを削除

bit4 = bit8 & 0xF;

という考え方で合ってます？

0895デフォルトの名無しさん

2008/09/27(土) 11:13:01

合ってる。

0896デフォルトの名無しさん

2008/09/27(土) 11:29:26

どうも

0897,,・´∀｀・,,）っ-○◎●

2008/09/27(土) 12:16:50

>>894
ARMならプレディケートに展開されるのでそれで十分速いんだが

欲をいえばこっちのほうが命令数とかレジスタ節約できるかもしれないね。
bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0;

また、比較命令はall 1 か all 0のビットマスクを生成するタイプのCPUなら、
ビットマスクと0xF0との論理積をとるだけで加算する値を取得できる。

しかし、2項選択は多くのＣＰＵ分岐命令に一般的には遅い。
シフトが遅くないならこっちを試してもいい
bit8 = (signed char)bit4 << 4 >> 4;

現実には多くの32ビットCPUはレジスタサイズ未満のビット演算は遅いのでこっちのほうがいいかも
bit8 = (signed char)(((signed int)bit4 << 28) >> 28);

要はネイティブで算術シフト命令のできる最小単位ならなんでもいい。
同じロジックでbit16でもbit32でも展開できる。

0898,,・´∀｀・,,）っ-○◎●

2008/09/27(土) 12:31:00

しかし、2項選択は多くのＣＰＵでは分岐命令に展開されるので一般的には遅い。

日本語しゃべれ俺

0899デフォルトの名無しさん

2008/09/27(土) 13:06:59

> bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0;

バグってるぞ。

0900,,・´∀｀・,,）っ-○◎●

2008/09/27(土) 13:13:06

bit8 = bit4 | ((bit4 & 0x8) ? 0xF0 : 0);

これでいいのか？

0901894

2008/09/27(土) 13:35:56

なるほどsingned型って右シフトで上位ビットを補ってくれるのね。
CPUは普通のPCのIntel x86系です。

0902,,・´∀｀・,,）っ-○◎●

2008/09/27(土) 13:49:08

x86ならシフト使う方法のほうが有効だろうね（Pentium 4はシフト遅いけど）
bit4 = ecx
bit8 = eax

と仮定して

mov eax, ecx
sal eax, 28
sar eax, 28
and eax, 0xFF

たった4命令で済む。bit4を破壊していいなら3命令。

0903デフォルトの名無しさん

2008/09/27(土) 19:47:32

>>895
ちがうだろ
算術シフトか論理シフトかはコンパイラ依存

0904デフォルトの名無しさん

2008/09/27(土) 19:50:09

100レスくらいで終わってもよさそうなのに実によく伸びるなこのスレ。

0905,,・´∀｀・,,）っ-○◎●

2008/09/27(土) 22:02:58

まあメジャーなコンパイラならsignedで算術シフトになるけどね。
//でコメントにならないコンパイラ並みには非互換問題あるのかな？

ローテートくらいまではC/C++標準仕様に入れておいて欲しいものだ

0906デフォルトの名無しさん

2008/09/27(土) 22:19:03

分岐は

0907デフォルトの名無しさん

2008/09/27(土) 22:26:53

>>903
> 算術シフトか論理シフトかはコンパイラ依存

負数の右シフトの動作のことを言ってるのか？

>> 2の補数で表される4bitの値を8bitに変換する場合

という条件下なら >>894 の内容に誤りはないと思うが。
そもそも、>>894 のレスにシフトのコードなんてないし。

# レスアンカーが >>897 なら同意するけど、あまり
# 触らない方がいいと思う。

0908,,・´∀｀・,,）っ-○◎●

2008/09/27(土) 22:33:18

もうこれでええやん
static const signed char table[] = { 0, 1, 2, 3, 4, 5, 6, 7, -8, -7, -6, -5, -4, -3, -2, -1 };

bit8 = table[bit4 & 15];

0909デフォルトの名無しさん

2008/09/27(土) 22:33:41

ダンゴさんの星が落ち着いてきたな

0910デフォルトの名無しさん

2008/09/28(日) 12:15:36

表引きもいいけど、キャッシュ容量とかミスヒットとか気になるし、
算術シフトもちょっと……という場合にはこっちがいいのでは。

bit8 = -(bit4 & 0x8) | bit4

0911デフォルトの名無しさん

2008/09/28(日) 12:29:09

上の動作の流れはこんな感じ。
等幅じゃないと見にくいけど分かってもらえるかな。

src　　　　　temp　　　　dst
????mxyz 00000000 00000000
????mxyz 0000m000 00000000 # temp = src & 0x8
????mxyz 0000m000 mmmmm000 # dst -= temp
????mxyz 0000m000 mmmmmxyz # dst |= src

0912,,・´∀｀・,,）っ-○◎●

2008/09/28(日) 12:34:50

この程度の小さいテーブルなら表引きは割と効果あるよ。
SSSE3のpshufbやAltiVecのvpermで16並列化もできるし。

0913,,・´∀｀・,,）っ-○◎●

2008/10/02(木) 00:50:06

>>910
x86で4命令だな。

mov eax, ecx
and eax, 0x08
neg eax
or eax, ecx

ちなみに>>902の方法はこれなら3命令。

mov al, cl
sal al, 4
sar, al 4

ただ、とてつもなくパーシャルレジスタストールの臭いがするぜ

0914デフォルトの名無しさん

2008/10/11(土) 16:18:31

Cで上手いことローテート命令に割り当てられるような書き方って何かある？
今は、8ビットローテートの場合は

(val << num) | (val >> (8-num) )

って書いてるけど、アセンブラ見てもまんまシフトとORで作られるんだよな
最後の手段でインラインアセンブラ使ってるけど、誰かＣでいい書き方知ってたら教えてくれ

0915デフォルトの名無しさん

2008/10/11(土) 16:23:26

そもそもローテート演算子がないからローテートを出力するコンパイラがないんじゃ

0916デフォルトの名無しさん

2008/10/11(土) 16:30:52

gccなら
unsigned foo(unsigned x, int n) {
return (x << n) | (x >> (32 - n));
}
で↓になったよ
_foo:
movl 4(%esp), %eax
movl 8(%esp), %ecx
roll %cl, %eax
ret
8ビットは無理だた

0917デフォルトの名無しさん

2008/10/11(土) 16:48:33

ダンゴさんならローテートの速度について一言ありそうだな

0918914

2008/10/11(土) 16:51:22

あぁ、コンパイラのオプション弄ったらちゃんとローテートになったわ
ちなみにCPUはARM、コンパイラはARM製のコンパイラです
速度に関しては何ビットローテートしても1クロックで済む、RISC万歳

0919デフォルトの名無しさん

2008/10/11(土) 17:56:35

>>914
インラインアセンブラで書いたものを、インライン展開できるようにしておくのはダメなの？
インラインの関数呼び出しでは不満？
演算子でやりたいなら、演算子をインライン展開できるように定義すればいいだけだと思うが。

0920,,・´∀｀・,,）っ-○◎●

2008/10/12(日) 14:47:04

>><とか <<>とかみたいな演算子を逆輸入してくれれば良いんだがねぇ

0921デフォルトの名無しさん

2008/10/13(月) 21:04:47

無理に演算子にしなくても、
コンパイラが認識する組込関数にすれば十分だよ。

0922デフォルトの名無しさん

2008/10/19(日) 21:43:35

このほうがローテートっぽい
@>
<@

0923デフォルトの名無しさん

2008/10/19(日) 21:49:25

>reg>
<reg<

0924デフォルトの名無しさん

2008/10/19(日) 22:01:01

㊨
㊧

0925デフォルトの名無しさん

2008/10/20(月) 01:05:00

_lrotr
_lrotl

0926デフォルトの名無しさん

2008/10/20(月) 15:43:41

|>
<|

0927デフォルトの名無しさん

2008/10/20(月) 22:06:50

>>925
指輪物語?
>>926
シュレディンガー音頭?

0928デフォルトの名無しさん

2008/10/21(火) 08:56:43

記号の演算子じゃなくて普通に単語使えばいいのに

ばかでしょ

0929デフォルトの名無しさん

2008/10/21(火) 23:59:57

指輪物語はlotrだなｗ

0930デフォルトの名無しさん

2008/10/22(水) 00:38:04

>>929
tlotr

0931デフォルトの名無しさん

2008/10/22(水) 00:46:10

公式はLOTR

0932デフォルトの名無しさん

2008/10/22(水) 00:53:09

なんで指輪物語スレになってんの・・・

0933デフォルトの名無しさん

2008/10/22(水) 00:56:14

>>931
tlotr

ググれば一目瞭然。

0934デフォルトの名無しさん

2008/10/22(水) 04:08:26

The Lord of the Rings だし。

0935デフォルトの名無しさん

2008/10/22(水) 08:55:55

Lordsな。両方複数系。

0936デフォルトの名無しさん

2008/10/22(水) 12:18:22

http://www.lordoftherings.net/
つまり、オフィシャルサイトは間違っていると。

0937デフォルトの名無しさん

2008/10/22(水) 12:34:52

>>935
Lordが正しい。
>>936
「the」がないのは、ドメイン取得の問題じゃないかな。

0938デフォルトの名無しさん

2008/10/22(水) 16:44:03

何時の間にか指輪スレ化している流れを豚切。

man gawk を見ると
lshift, rshift って内部関数が実装されているんだな。

0939デフォルトの名無しさん

2008/10/22(水) 21:50:42

>>925もVC++独自のローテート関数なわけだが。
指輪とはあんまり関係ない。

0940デフォルトの名無しさん

2008/10/22(水) 21:59:17

指輪物語とまで云うならthe fellowship of the ringだろ

0941,,・´∀｀・,,）っ-○◎○

2008/10/23(木) 01:44:47

lotrをロートルと呼ぼうのスレはここですか？

>>940それ第１章の副題

0942デフォルトの名無しさん

2008/10/23(木) 08:38:48

>>941
何…だと……？

0943デフォルトの名無しさん

2008/10/25(土) 00:00:41

>>933
lotr の検索結果約 9,330,000 件中 1 - 10 件目 (0.15 秒)
tlotr の検索結果約 69,400 件中 1 - 10 件目 (0.17 秒)

一体何が一目瞭然なんだか。

>>937
> 「the」がないのは、ドメイン取得の問題じゃないかな。

レスするなら、URL だけじゃなくてちゃんとページ見ろよ。

省略形で定冠詞を省略するのはごく普通。
２個あるうちの片っぽだけというのはちょっと違和感あるけど。

0944デフォルトの名無しさん

2008/10/25(土) 01:12:27

流れぶったぎって次スレ案

【指輪】ビット演算　0x03【物語】

0945デフォルトの名無しさん

2008/10/25(土) 01:13:31

いや、つまんないから

0946デフォルトの名無しさん

2008/10/25(土) 01:17:20

つーかもうスレ自体不要

0947デフォルトの名無しさん

2008/10/25(土) 17:26:25

>>944
これはコラだね、俺は騙されんよ。

0948デフォルトの名無しさん

2008/10/25(土) 18:44:44

>>947
>>945

0949デフォルトの名無しさん

2008/10/25(土) 18:53:14

>>948
>947

0950デフォルトの名無しさん

2008/10/25(土) 21:52:57

>>944-950
>>9

0951デフォルトの名無しさん

2008/10/26(日) 20:50:31

>>943
それは省略形であって正式ではない。
テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。

0952デフォルトの名無しさん

2008/10/26(日) 21:00:55

0を移動していくシフト演算っていい方法ある？

111111011
↓
111110111
↓
111101111
↓
111011111

こう言う感じで

0953デフォルトの名無しさん

2008/10/26(日) 21:02:22

a << 1
a | 1

0954デフォルトの名無しさん

2008/10/26(日) 21:06:31

>>953
速レスサントス

0955,,・´∀｀・,,）っ-●◎○

2008/10/26(日) 21:10:29

逆に考えるんだ
1のほうを立てて

00000100
↓
00001000
↓
00010000
↓
00100000

参照するときに反転すればいいと考えるんだ

0956デフォルトの名無しさん

2008/10/26(日) 23:24:33

ttp://www.amazon.co.jp/gp/product/images/0618002251/

0957デフォルトの名無しさん

2008/10/26(日) 23:41:34

>>951
> それは省略形であって正式ではない。

一体何を言ってるんだ？

> テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。

アホはお前だよ、単語の区切ぐらい見てるだろ。

yaho の検索結果約 2,580,000 件中 1 - 10 件目 (0.06 秒)
yahoo の検索結果約 2,330,000,000 件中 1 - 10 件目 (0.08 秒)

そもそも、どうやって「ググれば一目瞭然」なのか >>933 に聞けよ、クズ。

0958デフォルトの名無しさん

2008/10/26(日) 23:54:28

マジで>>944か>>946でいいような気がしてきた
もうどうでもいいよ

0959デフォルトの名無しさん

2008/10/27(月) 00:08:36

それ省略になってないし

0960デフォルトの名無しさん

2008/10/29(水) 11:21:19

>一体何を言ってるんだ？
あの文章に対してこんな事言ってるようじゃ
やはり>>957が真のアホと言わざるを得ない

0961デフォルトの名無しさん

2008/10/29(水) 12:11:34

何？悔しかったの？ｗ

0962デフォルトの名無しさん

2008/10/29(水) 22:03:47

　　_..,,.,,.
　「r',.　、
　d　´c`/　ちくしょう・・・
　 i　' ∋

ぉち彡　,.-,ﾆユ、
ぉく .三　 { ,.= r、
｜し三 (6' r',ニ7
｜ょ三.　| !| {　{
｜お三. |　ﾐ‐ニ)
! ! ぉミ　!　　　{

0963デフォルトの名無しさん

2008/10/29(水) 22:42:12

>>960
>> テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。

いや～、賢いねぇ。(w

0964デフォルトの名無しさん

2008/11/02(日) 13:18:15

よく>>751-752の課題を見ると、aが整数だとはどこにも書いてなかったな。
だから、>>763の方法で計算できるのは、aに近い整数値でしかない。
それに、渡さされる2^aの値が整数かどうかも記載されていないな。

ビット演算だから常に整数という誤認があったかもしれん。
まあ、小数点以下の計算も整数演算の延長でしかないから問題ないけど。

0965デフォルトの名無しさん

2008/11/05(水) 11:24:39

32bit整数でビットが立ってる最上位のビット以下を全部立たせる処理で
int fill(int n){
　　n |= n>>1;
　　n |= n>>2;
　　n |= n>>4;
　　n |= n>>8
　　n |= n>>16;
　　return n;
}
てのを作ってみたんだが、まだ速くできるかな？てか、この処理に名前ってある？

0966デフォルトの名無しさん

2008/11/05(水) 14:28:15

>>965
アセンブラ使っていいなら２命令で終わり。

0967デフォルトの名無しさん

2008/11/05(水) 18:04:27

それ無しでｗ

0968デフォルトの名無しさん

2008/11/05(水) 18:38:44

gccの拡張使っていいなら
int fill(int n) {
return n ? (~0u >> __builtin_clz(n)) : 0;
}

0969デフォルトの名無しさん

2008/11/05(水) 20:23:00

>>968　それって結局どんなコードになってるんですか？

0970デフォルトの名無しさん

2008/11/05(水) 21:24:26

bsr

0971デフォルトの名無しさん

2008/11/05(水) 21:55:59

n|n-1で行けない？
n=0の時上手くいかないだろうけど。

0972デフォルトの名無しさん

2008/11/05(水) 22:00:56

それでうまくいくのnが２のべき乗のときだけじゃない？

0973デフォルトの名無しさん

2008/11/05(水) 22:04:21

4(or8)毎に処理するとか？

0974デフォルトの名無しさん

2008/11/05(水) 22:26:37

bsrってaddとかと同じレベルの命令？その命令って最近のCPUにはどれでも入ってるって言うのかい？

0975デフォルトの名無しさん

2008/11/05(水) 22:58:48

環境に依存するけど、単にn>>31でも良いのでは？

環境依存しないようにするなら、unsignedをつけて
>>971にandをかませば良いと思う。

unsigned int fill(unsigned int n) {
unsigned int a;
a = n & 0x80000000ul;
return a & (a - (a >> 31))
}

ただし、MSBが1でないときに何を返したいかによってはダメだけど

0976デフォルトの名無しさん

2008/11/05(水) 23:01:15

>>975
違った
return a | (a-(a >> 31));ね

0977デフォルトの名無しさん

2008/11/05(水) 23:32:00

31の人気に嫉妬

0978デフォルトの名無しさん

2008/11/06(木) 00:25:46

>>975-976
顔を洗って出直してこい。

0979デフォルトの名無しさん

2008/11/06(木) 08:48:03

>>977
ほんとにそうだな。
>>976のようにスペースを入れるとよい。

0980デフォルトの名無しさん

2008/11/06(木) 22:03:20

たとえば、0x00008080 を
>>976
で計算すると
0x00008080
に、
>>965
で計算すると
0x0000ffff
になる。

0981デフォルトの名無しさん

2008/11/06(木) 23:12:08

>>978
>>980
理解した。出直す。

レス数が950を超えています。1000を超えると書き込みができなくなります。

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

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