- 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
- 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のエンディアンの変換てどうすればいい？
- 152 名前：150 mailto:sage [2007/02/18(日) 21:13:28 ]
- ごめん、よく考えたら大したことなかった。
これでOKだ。
x = ( ( x >> 8 ) & 0x00ff00ff ) | ( ( x << 8 ) & 0xff00ff00 );
x = ( ( x >> 16 ) & 0x0000ffff ) | ( ( x << 16 ) & 0xffff0000 );
- 153 名前：デフォルトの名無しさん mailto:sage [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の方法のほうが良いように思うが。
- 154 名前：デフォルトの名無しさん mailto:sage [2007/02/19(月) 18:34:24 ]
- 普通に共用体でやった方がエレガントで早いと思いますが。。
- 155 名前：デフォルトの名無しさん mailto:sage [2007/02/19(月) 21:49:23 ]
- 正直これでいいや。
ttp://msdn2.microsoft.com/ja-jp/library/a3140177(VS.80).aspx
- 156 名前：デフォルトの名無しさん mailto:sage [2007/02/20(火) 21:52:40 ]
- >>155
?
- 157 名前：デフォルトの名無しさん [2007/03/01(木) 22:52:20 ]
- あげ
- 158 名前：デフォルトの名無しさん mailto:sage [2007/03/21(水) 06:17:18 ]
- 任意のビット数のシフトやローテートてなんで１クロックで実行できねーの？
連続した場合ね。
- 159 名前：デフォルトの名無しさん mailto:sage [2007/03/22(木) 00:34:10 ]
- 1024bitとか？
- 160 名前：デフォルトの名無しさん mailto:sage [2007/03/22(木) 08:22:35 ]
- そもそも1クロックで実行っていつの時代のどのCPUの話だよ
30年前の8bit時代から頭の中進歩してないオジサマ丸出しだねw
しかも昔の8bitマイコンだって命令サイクルと実クロックは別物だしね
- 161 名前：デフォルトの名無しさん mailto:sage [2007/03/22(木) 21:47:22 ]
- なんか言いたいんだろうけど、何を言いたいのかさっぱりわからん。
知ったか厨の典型だな。(w
- 162 名前：デフォルトの名無しさん [2007/04/07(土) 02:22:12 ]
- あげ
- 163 名前：デフォルトの名無しさん [2007/04/29(日) 08:20:14 ]
- a
- 164 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 10:38:15 ]
- 1Bit CPUの可能性について語れないのは素人。
- 165 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 10:44:47 ]
- cmos 4000 シリーズの事か？
- 166 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 10:52:16 ]
- MC14500 か
- 167 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 12:29:58 ]
- コネクションマシンか？
- 168 名前：デフォルトの名無しさん mailto:sage [2007/04/29(日) 18:46:24 ]
- バイトの縛りがうざいんだよ
- 169 名前：デフォルトの名無しさん mailto:sage [2007/04/30(月) 02:15:38 ]
- 22時以降はダメとか?
- 170 名前：デフォルトの名無しさん mailto:sage [2007/04/30(月) 07:39:02 ]
- ざぶんとん
- 171 名前：デフォルトの名無しさん mailto:sage [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))
- 172 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 20:20:41 ]
- (hoge & 0x000000C0) == 0x000000C0 が一番速いだろう。
- 173 名前：デフォルトの名無しさん mailto:sage [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;
}
- 174 名前：デフォルトの名無しさん mailto:sage [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
- 175 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 20:34:17 ]
- >>172 が正解なんだけど
いまどきのコンパイラは
>>171 (3) で書いても
最適化されて >>172 になってるんだね
- 176 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 22:06:56 ]
- ど素人です。質問があります。
例えば1か0が格納される変数(Aと仮定)のスイッチ切り替えの場合
【例①】
if(A == 1)
{
A = 0;
}
else
{
A = 1;
}
【例②】
A = A ^ (0 + 1);
この場合早いのはやはり例②なのでしょうか？
- 177 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 22:13:48 ]
- A ^= 1;
が速い。まあ、例２と同じだあな。
- 178 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 22:18:35 ]
- >>177
有難うございました。
- 179 名前：デフォルトの名無しさん mailto:sage [2007/05/03(木) 22:24:42 ]
- SUBR #n Acc = n-Acc を持ってるCPUだと
A = 1-A
のが速かったりするぞ
- 180 名前：デフォルトの名無しさん mailto:sage [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とかでもいいんだけどな
- 181 名前：・∀・）っ-○◎● mailto:sage [2007/05/04(金) 00:52:14 ]
-
A ^= 8;
？？？？？？？？？？？？？？？？？？？？？？？？？？？？
Aには1か0が格納されるって最初の条件で確定してるんだが
- 182 名前：180 mailto:sage [2007/05/04(金) 00:53:56 ]
- >>181
汎用性を高めるって意味だよ
|
 |
