- 1 名前：デフォルトの名無しさん [2006/09/16(土) 09:46:26 ]
- 前スレ
ビット演算
pc8.2ch.net/test/read.cgi/tech/1123918075/
関連スレ
アセンブラ… (゜□゜) ↑アッー！↓
pc8.2ch.net/test/read.cgi/tech/1148402614/
関連情報
Hacker's Delight
ttp://www.hackersdelight.org/
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
ttp://www.amazon.co.jp/exec/obidos/ASIN/4434046683
ビットを数える・探すアルゴリズム
ttp://www.nminoru.jp/~nminoru/programming/bitcount.html
Bitboard
ttp://en.wikipedia.org/wiki/Bitboard
- 51 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 23:18:57 ]
- >>50
例え処理が１行だけであっても、関数（インラインで良い）にしとけば文句でないはず。
- 52 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 23:26:39 ]
- >>51
勿論明瞭なコメント付きでな。
- 53 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 23:36:36 ]
- >>51
ついでに代替コードを書いておくとなお良い。
- 54 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 04:27:35 ]
- ゴリゴリのチューニングが求めらるような場面でもなければ、たいていはコンパイラの最適化だけで事足りるわけだが。
- 55 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 05:31:51 ]
- スクリプトでマスかいてろ
- 56 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 09:38:47 ]
- >>54
確かにそれで文句が出ないどころかメンテしやすければ褒められるべきところではあるが
多少の遊び心があってもそれはそれで許される。
>>51-53のようなことをしてあれば。
（代替コードのテストも必要なことは当然なので、プログラマの負担はアップするが）
- 57 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 13:48:49 ]
- ビット演算による最適化が必要で
パフォーマンス的に代替が効かないからこそ
そういうコードを書くわけだから
同等以上の速度が出た上に読みやすいコードを出せなければ
批難する事はできない。
もちろん意味もなくビット演算するアホの話は別として。
- 58 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 16:28:36 ]
- でも普通インラインアセンブラ使うよね。そういうビット演算だと。
上で出てるようなCでなんて書かないよ。
- 59 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 16:34:33 ]
- いや、俺はループアンローリングだとかプロセッサのスケジューリング管理
なんか考えたくないからC言語で書くけどね。
まぁ、どうしてもビット回転(rotate)が必要ならインラインアセンブラの
使用も検討するが。
- 60 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 16:41:08 ]
- インラインアセンブラはアセンブラとは違うよ
- 61 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 18:52:45 ]
- >>60
いや、当たり前の事実を主張されてもなぁ。
しかもなぜにこのタイミングで？わけわからん。
- 62 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 21:02:46 ]
- >>60
何が違うの？
- 63 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 21:26:25 ]
- ものほんのアセンブラならそもそも命令セットの数が違うみたいな？
- 64 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 23:34:07 ]
- なんつー理屈だ。
寧ろインラインアセンブラだとCコード部とのI/Fが簡単に書けるメリットはあるね。
- 65 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 00:47:40 ]
- ネイティブアセンブラ
C言語との連携は関数呼び出しの形でのみによって実現される。
殆どのメモリアクセスはシンボルではなくオフセット値での指定となるからめんどい。
最適化の善し悪しはすべて自分の腕にかかっている。
インラインアセンブラ
Cのソースに埋め込むことが出来るので、必要な箇所を個別に関数化する必要がない。
関数内の局所変数にシンボリックにアクセスできる。
一部のコンパイラはインラインアセンブラで書いた箇所も勝手に最適化してくれやがる。
- 66 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 00:56:32 ]
- スレ違いだ。他所でやれ。
- 67 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 13:52:46 ]
- 論理演算部分をインラインアセンブラ化するのに、
どうして「プロセッサのスケジューリング管理」なんて話が出てくるのか誰か教えて！
- 68 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 16:26:53 ]
- 「プロセッサのスケジューリング管理」の意味はわかっているか？
- 69 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 17:04:37 ]
- 大方タイムスライスと勘違いしているんだろうけど。
- 70 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 17:27:16 ]
- >>67
パイプラインでな、処理を円滑に進めるためには、命令の実行順序を適切に
並び替える必要があるんだ。命令実行順序の決定をスケジューリングという。
命令実行スケジューリングはふつうコンパイラが最適化の一環として施すが
インラインアセンブラで記述した部分はそのままの順序で出力されて最適化
されないことが多い。
- 71 名前：デフォルトの名無しさん [2006/10/26(木) 23:04:23 ]
- ！
- 72 名前：デフォルトの名無しさん [2006/10/30(月) 22:09:37 ]
- あげ
- 73 名前：デフォルトの名無しさん mailto:sage [2006/10/30(月) 22:39:25 ]
- テンプレにある
＞ハッカーのたのしみ
は、アマゾンで評価が高いみたいですが
本当に読んで面白い本なんですか？
- 74 名前：デフォルトの名無しさん mailto:sage [2006/10/30(月) 22:47:16 ]
- >>73
それはお前がビット演算を楽しめるかどうかによる。
- 75 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 03:09:00 ]
- >>73
もしもあなたが書き溜めたソースコードを持っているのなら…
- 76 名前：デフォルトの名無しさん mailto:age [2006/11/15(水) 19:13:21 ]
- ビット演算で絶対値を求めることってできますかね？
条件分岐をしないで絶対値を求めたいのですが…
- 77 名前：デフォルトの名無しさん [2006/11/15(水) 20:26:02 ]
- >>76
このへん見てみたら？
www.thescripts.com/forum/thread212935.html
- 78 名前：デフォルトの名無しさん mailto:sage [2006/11/15(水) 21:53:55 ]
- int y=x>>31;
return (x^y)-y;
か。
今ならcmovのほうが速いだろうけど
- 79 名前：デフォルトの名無しさん mailto:sage [2006/11/15(水) 22:56:58 ]
- ふーむ…
とりあえずリンク先を参考に試してみようと思います
ありがとうございました
- 80 名前：デフォルトの名無しさん [2006/11/26(日) 15:29:11 ]
- age
- 81 名前：デフォルトの名無しさん [2006/12/02(土) 22:52:42 ]
- age
- 82 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 07:55:42 ]
- とにかく徹底的にｉｆ文使いたくないんだけど、
根本的に排除する方法ってないんですか？
こういう場合はできるよってのがあったらそれも知りたいです。
もうビット演算のこと以外考えたくないんです。
- 83 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 08:40:06 ]
- >>82
論理回路にｉｆ演算器はない。
- 84 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 08:40:31 ]
- if(a){
x;
} else {
y;
}
⇒
switch(a){
default:
x;
break;
case 0:
y;
}
- 85 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 08:50:26 ]
- じゃあ僕は条件分岐と一生付き合わなきゃいけないんですか？
一生、縁が切れないんですか？？
もう勘弁しいてほしいんです。
ソース読みにくいのってみんなｉｆ文の所為じゃないですか。
この絶望のまま生きていたくない。
並列計算がうまくいかないのだってきっと条件分岐のせいですよ。
諸悪の根源と思っていますよ、もう。
ところで、論理シフトとかってあれは論理演算が関係してるんですか？
- 86 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 09:38:32 ]
- if(a>b){
x=c;
} else {
x=d;
}
x=(a>b)*c;
x+=!(a>b)*d;
こんな感じかな？
ビット演算じゃ無いけど
- 87 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 10:20:41 ]
- if(a){
x;
} else {
y;
}
⇒
n_if(a){
x && a || y && !a;
}
- 88 名前：デフォルトの名無しさん mailto:sage [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]();
- 89 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 mailto:sage [2006/12/04(月) 22:59:51 ]
- 関数コールのペナルティ＞＞＞分岐予測ミスのペナルティ
d = a ? b : c;
とかでも使えば？組み込みのCMOV命令に展開してくれたりするし
SIMD系の命令セットは比較命令はマスク生成のことが多い
- 90 名前：デフォルトの名無しさん mailto:sage [2006/12/04(月) 23:03:57 ]
- P4だと、テーブル参照方式はペナルティが信じられんほど凄い。
命令20ぐらいをズラスラ書いたのより、テーブル参照1つの方が遅かったりする。
- 91 名前：デフォルトの名無しさん mailto:sage [2006/12/07(木) 00:04:36 ]
- 最近それ経験した。
switchで振り分けた方が遥かに速かったわ。恐るべし分岐予測。
- 92 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 mailto:sage [2006/12/07(木) 00:39:10 ]
- >>82はPS3かなんかの開発やらされてるゲームプログラマなんじゃね？
- 93 名前：82 mailto:sage [2006/12/11(月) 04:57:32 ]
- もうジャンプするのも嫌になりました。
ｉｆ文なしのジャンプなしで何とかならないでしょうか？？
- 94 名前：デフォルトの名無しさん mailto:sage [2006/12/11(月) 18:38:36 ]
- てきとーに制限つけてその条件内で考えさせたいだけでしょ。
- 95 名前：デフォルトの名無しさん [2006/12/18(月) 22:14:18 ]
- age
- 96 名前：デフォルトの名無しさん mailto:sage [2006/12/25(月) 20:04:45 ]
- sub a, b
adc pc, a
- 97 名前：デフォルトの名無しさん [2006/12/30(土) 23:15:58 ]
- あげ
- 98 名前： 【大吉】 [2007/01/01(月) 00:23:58 ]
- あけまして、おめでとうごｚぁいます
- 99 名前：デフォルトの名無しさん mailto:sage [2007/01/01(月) 13:31:16 ]
- 要は皆さんパズル好きだと
- 100 名前：デフォルトの名無しさん mailto:sage [2007/01/03(水) 13:42:06 ]
- プログラミング自体が、言語変わってもパーツの組合せのパズルに過ぎない訳で。
- 101 名前：デフォルトの名無しさん mailto:sage [2007/01/03(水) 19:31:35 ]
- >>82
>根本的に排除する方法ってないんですか？
>こういう場合はできるよってのがあったらそれも知りたいです。
ビット演算以外の仕事は「引き受けない」
- 102 名前：デフォルトの名無しさん mailto:sage [2007/01/03(水) 23:21:49 ]
- >82
まずプロセッサから設計した方がいいんじゃないか
- 103 名前：デフォルトの名無しさん mailto:sage [2007/01/04(木) 00:46:05 ]
- >>93
cmp+jeの組み合わせがいやならsub+jneでどうだろうか。
- 104 名前：デフォルトの名無しさん [2007/01/06(土) 15:01:25 ]
- Cです
int i;として
iが0以外なら1を、iが0なら0を返すビット演算は
i!=0以上にコンパクトにできるのでしょうか？
n = i!=0;と括弧つけてもやや読みづらいので。
(bool)iならば可読的なので喜んで使いたいのですが、Cなので残念ながら…
- 105 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 15:03:57 ]
- !!i
なんてどう？
- 106 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 21:00:27 ]
- typedef enum{false, true} bool;
(bool)i
- 107 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 22:58:09 ]
- 問題は、Cではenum型にキャストした値がenum値に制限されるかどうかだね。
- 108 名前：・∀・）っ-○◎●新世紀ダンゴリオン ◆DanGorION6 mailto:sage [2007/01/06(土) 23:02:40 ]
- めんどくさい
#define TO_BOOL(x) ((x) != 0)
- 109 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 23:04:45 ]
- 阿呆なマクロを使うくらいなら>105でいいじゃん。
- 110 名前：デフォルトの名無しさん mailto:sage [2007/01/06(土) 23:07:38 ]
- >>108
C、C++の最適化について語るスレ
pc10.2ch.net/test/read.cgi/tech/1084676298/
団子ちゃん、↑こっちのスレの結果はどうなったの？
やっぱり、団子ちゃんが適当なこと吹いてただけなの？
- 111 名前：デフォルトの名無しさん mailto:sage [2007/01/07(日) 07:00:18 ]
- っつーかどうしても1にしたい状況ってそんなないだろ
0/!0で充分だから
- 112 名前：デフォルトの名無しさん mailto:sage [2007/01/07(日) 22:11:55 ]
- ビット演算でも高速化でもないな。
- 113 名前：デフォルトの名無しさん mailto:sage [2007/01/14(日) 00:16:55 ]
- #define BITTOENNZANN(dayo) ((dayo)!=0)
これでビット演算だお^ω^
- 114 名前：デフォルトの名無しさん mailto:sage [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;
}
誰か減算器↓
- 115 名前：デフォルトの名無しさん mailto:sage [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);}
- 116 名前：デフォルトの名無しさん mailto:sage [2007/01/18(木) 16:58:05 ]
- >>109
! がオーバーロードされてたら、二回も呼ばれることになるぜ。
- 117 名前：デフォルトの名無しさん mailto:sage [2007/01/19(金) 01:20:26 ]
- オーバーロードまで考慮したら ! 二回より != の方が遅いことも
十分ありえるけどな。
- 118 名前：デフォルトの名無しさん [2007/01/19(金) 14:36:23 ]
- 64bitのビットを数えるのは外出？
- 119 名前：デフォルトの名無しさん mailto:sage [2007/01/19(金) 18:41:42 ]
- >>118
ビットを数えるってのがよくあるpop関数のことなら死ぬほど既出。
- 120 名前：デフォルトの名無しさん [2007/01/23(火) 07:38:25 ]
- あげ
- 121 名前：デフォルトの名無しさん mailto:sage [2007/01/23(火) 10:19:53 ]
- レス４は絶対ここの住民だろ笑
pc10.2ch.net/test/read.cgi/tech/1169104637/l50
- 122 名前：デフォルトの名無しさん mailto:sage [2007/01/26(金) 23:52:21 ]
- >>121
こいつのせいでビット操作のスレになってるじゃないか
- 123 名前：デフォルトの名無しさん mailto:sage [2007/01/29(月) 12:22:02 ]
- ビット演算でbranch freeなmagic incrementは可能かね？
- 124 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 18:20:58 ]
- Bit Twiddling Hacks
ttp://graphics.stanford.edu/~seander/bithacks.html
こんなサイトが（英語だけど）
テンプレに入れる？
- 125 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 21:33:10 ]
- 入れるのはいいけど、それまで続くんか?
- 126 名前：デフォルトの名無しさん mailto:sage [2007/02/12(月) 22:46:32 ]
- コンパイル時には>>124をテンプレとしてオーバーライドします。
- 127 名前：デフォルトの名無しさん [2007/02/13(火) 07:43:07 ]
- もうこのスレも息切れみたいだね。
- 128 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 23:14:23 ]
- だいたいビット演算ごときでときめいちゃうのは厨房までだろw
煽りぬきで
- 129 名前：デフォルトの名無しさん mailto:sage [2007/02/13(火) 23:51:38 ]
- ていうか、パズルみたいなもんだろ。
さすがに、ネタ切れにて閉店でいいと思うよ。
- 130 名前：デフォルトの名無しさん mailto:sage [2007/02/15(木) 15:02:08 ]
- よほど要求速度や省メモリがシビアな環境でない限りは妙な小細工はたいして必要ないもんね
- 131 名前：デフォルトの名無しさん [2007/02/15(木) 15:47:08 ]
- int i = 20070215;
で、この i からそれぞれ 2007, 2, 15 って数字が欲しいんだけど
誰かカッコ良くビット演算使ってやってください。
- 132 名前：デフォルトの名無しさん mailto:sage [2007/02/15(木) 15:50:34 ]
- >>131
実質的には除数固定で割り算を行うのと同じだから
割り算の話になるな。
- 133 名前：デフォルトの名無しさん [2007/02/15(木) 16:48:06 ]
- 0x20070215
- 134 名前：デフォルトの名無しさん mailto:sage [2007/02/15(木) 16:53:01 ]
- >>131-133
それすごくもったいなくないか
たしか
日：1-31 (5bit)
月：1-12 (4bit)
年：00-99 (7bit)
で 16bit っつー表記があったな
FDとかHDのタイムスタンプとか
今なら年だけ
0000-9999 (14bit)
でも 23bit で余裕な訳だが
- 135 名前：デフォルトの名無しさん mailto:sage [2007/02/15(木) 17:03:23 ]
- >>134
そんなところでビットをケチったってしょうがねぇべさ。
そのフォーマット(MS-DOSのFATだな)はタイムスタンプが2秒単位でしか記録できないしね。
#hour:5, minute:6, second:5
- 136 名前：デフォルトの名無しさん [2007/02/16(金) 03:33:47 ]
- ねえ偉い人
１０進数を３進数に変換するコードはJAVAでどう書きますか？
- 137 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 03:46:47 ]
- ↑バカ
- 138 名前：デフォルトの名無しさん [2007/02/16(金) 14:24:00 ]
- イマイチビット演算はよくわからん
- 139 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 15:18:45 ]
- ビット演算してると脳汁が出る
大抵は無意味だけど
オナニーとしてはﾅｶﾅｶそそる
- 140 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 15:28:21 ]
- ビット演算って1や0にするだけじゃん。
- 141 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 15:35:59 ]
- だが、それがいい。
- 142 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 15:55:53 ]
- 3|17 2
3| 5 2
1
10進数:17 -> 3進数:122
10進数から3進数への変換て、これであってる？
- 143 名前：デフォルトの名無しさん [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
- 144 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 20:57:54 ]
- うわっバカだ
staticいらないだろ。
- 145 名前：デフォルトの名無しさん [2007/02/16(金) 23:56:47 ]
- bitマスクとかメンドクサイから言語レベルでbitの配列みたいに扱える
演算子があれば良いんだけどな。
STLやboostを使っても型変換が必要だし。
- 146 名前：デフォルトの名無しさん mailto:sage [2007/02/16(金) 23:58:08 ]
- ビットフィールド？
- 147 名前：デフォルトの名無しさん mailto:sage [2007/02/17(土) 00:00:30 ]
- static を除去するなら、戻り値は const float & ではなく float にすべきでもある。
ところで、乱数の範囲はそれでいいのか？
２進表現で0x3f800000 から 0x3fffffff にして、そこから 1.0f を引くと [0..1) になって使いやすいと思うが。
- 148 名前：デフォルトの名無しさん mailto:sage [2007/02/17(土) 01:31:32 ]
- floatの表現がIEEEに合致するってのは保証されてるんだっけ？
- 149 名前：デフォルトの名無しさん mailto:sage [2007/02/17(土) 01:54:26 ]
- うんにゃ、されてない
- 150 名前：デフォルトの名無しさん mailto:sage [2007/02/17(土) 08:36:23 ]
- だが、それがいい
- 151 名前：デフォルトの名無しさん [2007/02/18(日) 21:02:06 ]
- 32bitのエンディアンの変換てどうすればいい？
|
 |
