- 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
- 895 名前：デフォルトの名無しさん [2008/09/27(土) 11:13:01 ]
- 合ってる。
- 896 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 11:29:26 ]
- どうも
- 897 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [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でも展開できる。
- 898 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 12:31:00 ]
- しかし、2項選択は多くのＣＰＵでは分岐命令に展開されるので一般的には遅い。
日本語しゃべれ俺
- 899 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 13:06:59 ]
- > bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0;
バグってるぞ。
- 900 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 13:13:06 ]
- bit8 = bit4 | ((bit4 & 0x8) ? 0xF0 : 0);
これでいいのか？
- 901 名前：894 mailto:sage [2008/09/27(土) 13:35:56 ]
- なるほどsingned型って右シフトで上位ビットを補ってくれるのね。
CPUは普通のPCのIntel x86系です。
- 902 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [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命令。
- 903 名前：デフォルトの名無しさん [2008/09/27(土) 19:47:32 ]
- >>895
ちがうだろ
算術シフトか論理シフトかはコンパイラ依存
- 904 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 19:50:09 ]
- 100レスくらいで終わってもよさそうなのに実によく伸びるなこのスレ。
- 905 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/27(土) 22:02:58 ]
- まあメジャーなコンパイラならsignedで算術シフトになるけどね。
//でコメントにならないコンパイラ並みには非互換問題あるのかな？
ローテートくらいまではC/C++標準仕様に入れておいて欲しいものだ
- 906 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 22:19:03 ]
- 分岐は
- 907 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 22:26:53 ]
- >>903
> 算術シフトか論理シフトかはコンパイラ依存
負数の右シフトの動作のことを言ってるのか？
>> 2の補数で表される4bitの値を8bitに変換する場合
という条件下なら >>894 の内容に誤りはないと思うが。
そもそも、>>894 のレスにシフトのコードなんてないし。
# レスアンカーが >>897 なら同意するけど、あまり
# 触らない方がいいと思う。
- 908 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [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];
- 909 名前：デフォルトの名無しさん mailto:sage [2008/09/27(土) 22:33:41 ]
- ダンゴさんの星が落ち着いてきたな
- 910 名前：デフォルトの名無しさん mailto:sage [2008/09/28(日) 12:15:36 ]
- 表引きもいいけど、キャッシュ容量とかミスヒットとか気になるし、
算術シフトもちょっと……という場合にはこっちがいいのでは。
bit8 = -(bit4 & 0x8) | bit4
- 911 名前：デフォルトの名無しさん mailto:sage [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
- 912 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/09/28(日) 12:34:50 ]
- この程度の小さいテーブルなら表引きは割と効果あるよ。
SSSE3のpshufbやAltiVecのvpermで16並列化もできるし。
- 913 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [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
ただ、とてつもなくパーシャルレジスタストールの臭いがするぜ
- 914 名前：デフォルトの名無しさん [2008/10/11(土) 16:18:31 ]
- Cで上手いことローテート命令に割り当てられるような書き方って何かある？
今は、8ビットローテートの場合は
(val << num) | (val >> (8-num) )
って書いてるけど、アセンブラ見てもまんまシフトとORで作られるんだよな
最後の手段でインラインアセンブラ使ってるけど、誰かＣでいい書き方知ってたら教えてくれ
- 915 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 16:23:26 ]
- そもそもローテート演算子がないからローテートを出力するコンパイラがないんじゃ
- 916 名前：デフォルトの名無しさん mailto:sage [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ビットは無理だた
- 917 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 16:48:33 ]
- ダンゴさんならローテートの速度について一言ありそうだな
- 918 名前：914 [2008/10/11(土) 16:51:22 ]
- あぁ、コンパイラのオプション弄ったらちゃんとローテートになったわ
ちなみにCPUはARM、コンパイラはARM製のコンパイラです
速度に関しては何ビットローテートしても1クロックで済む、RISC万歳
- 919 名前：デフォルトの名無しさん mailto:sage [2008/10/11(土) 17:56:35 ]
- >>914
インラインアセンブラで書いたものを、インライン展開できるようにしておくのはダメなの？
インラインの関数呼び出しでは不満？
演算子でやりたいなら、演算子をインライン展開できるように定義すればいいだけだと思うが。
- 920 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2008/10/12(日) 14:47:04 ]
- >><とか <<>とかみたいな演算子を逆輸入してくれれば良いんだがねぇ
- 921 名前：デフォルトの名無しさん mailto:sage [2008/10/13(月) 21:04:47 ]
- 無理に演算子にしなくても、
コンパイラが認識する組込関数にすれば十分だよ。
- 922 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 21:43:35 ]
- このほうがローテートっぽい
@>
<@
- 923 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 21:49:25 ]
- >reg>
<reg<
- 924 名前：デフォルトの名無しさん mailto:sage [2008/10/19(日) 22:01:01 ]
- ㊨
㊧
- 925 名前：デフォルトの名無しさん mailto:sage [2008/10/20(月) 01:05:00 ]
- _lrotr
_lrotl
- 926 名前：デフォルトの名無しさん mailto:sage [2008/10/20(月) 15:43:41 ]
- |>
<|
- 927 名前：デフォルトの名無しさん mailto:sage [2008/10/20(月) 22:06:50 ]
- >>925
指輪物語?
>>926
シュレディンガー音頭?
- 928 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 08:56:43 ]
- 記号の演算子じゃなくて普通に単語使えばいいのに
ばかでしょ
- 929 名前：デフォルトの名無しさん mailto:sage [2008/10/21(火) 23:59:57 ]
- 指輪物語はlotrだなｗ
- 930 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:38:04 ]
- >>929
tlotr
- 931 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:46:10 ]
- 公式はLOTR
- 932 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:53:09 ]
- なんで指輪物語スレになってんの・・・
- 933 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 00:56:14 ]
- >>931
tlotr
ググれば一目瞭然。
- 934 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 04:08:26 ]
- The Lord of the Rings だし。
- 935 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 08:55:55 ]
- Lordsな。両方複数系。
- 936 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 12:18:22 ]
- www.lordoftherings.net/
つまり、オフィシャルサイトは間違っていると。
- 937 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 12:34:52 ]
- >>935
Lordが正しい。
>>936
「the」がないのは、ドメイン取得の問題じゃないかな。
- 938 名前：デフォルトの名無しさん [2008/10/22(水) 16:44:03 ]
- 何時の間にか指輪スレ化している流れを豚切。
man gawk を見ると
lshift, rshift って内部関数が実装されているんだな。
- 939 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:50:42 ]
- >>925もVC++独自のローテート関数なわけだが。
指輪とはあんまり関係ない。
- 940 名前：デフォルトの名無しさん mailto:sage [2008/10/22(水) 21:59:17 ]
- 指輪物語とまで云うならthe fellowship of the ringだろ
- 941 名前：,,・´∀｀・,,）っ-○◎○ mailto:sage [2008/10/23(木) 01:44:47 ]
- lotrをロートルと呼ぼうのスレはここですか？
>>940それ第１章の副題
- 942 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 08:38:48 ]
- >>941
何…だと……？
- 943 名前：デフォルトの名無しさん mailto:sage [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 だけじゃなくてちゃんとページ見ろよ。
省略形で定冠詞を省略するのはごく普通。
２個あるうちの片っぽだけというのはちょっと違和感あるけど。
- 944 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:12:27 ]
- 流れぶったぎって次スレ案
【指輪】ビット演算 0x03【物語】
- 945 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:13:31 ]
- いや、つまんないから
- 946 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:17:20 ]
- つーかもうスレ自体不要
- 947 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 17:26:25 ]
- >>944
これはコラだね、俺は騙されんよ。
- 948 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 18:44:44 ]
- >>947
>>945
- 949 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 18:53:14 ]
- >>948
>947
- 950 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 21:52:57 ]
- >>944-950
>>9
- 951 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 20:50:31 ]
- >>943
それは省略形であって正式ではない。
テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。
- 952 名前：デフォルトの名無しさん [2008/10/26(日) 21:00:55 ]
- 0を移動していくシフト演算っていい方法ある？
111111011
↓
111110111
↓
111101111
↓
111011111
こう言う感じで
- 953 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 21:02:22 ]
- a << 1
a | 1
- 954 名前：デフォルトの名無しさん [2008/10/26(日) 21:06:31 ]
- >>953
速レスサントス
- 955 名前：,,・´∀｀・,,）っ-●◎○ mailto:sage [2008/10/26(日) 21:10:29 ]
- 逆に考えるんだ
1のほうを立てて
00000100
↓
00001000
↓
00010000
↓
00100000
参照するときに反転すればいいと考えるんだ
- 956 名前：デフォルトの名無しさん [2008/10/26(日) 23:24:33 ]
- ttp://www.amazon.co.jp/gp/product/images/0618002251/
- 957 名前：デフォルトの名無しさん mailto:sage [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 に聞けよ、クズ。
- 958 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:54:28 ]
- マジで>>944か>>946でいいような気がしてきた
もうどうでもいいよ
- 959 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 00:08:36 ]
- それ省略になってないし
|
 |
