- 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
- 862 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 17:25:18 ]
- >>861
お前ここに糞スラのURL張るの禁止されていること
しらんのか？
- 863 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 17:27:12 ]
- スラッシュドット禁止ってどんだけ情報弱者なんだよ。
え？あっちから拒絶してんの？
- 864 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 17:27:38 ]
- あれ？ 板ルール？
スマンかった。忘れて。
- 865 名前：861 mailto:sage [2008/08/09(土) 17:31:07 ]
- >>863
あっちも出入りしているけど、そういうことはないと思う。
ここの板ローカルのルールなのかね？
ここも長年見ているが、あまり聞いたことないけど。
- 866 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 18:01:21 ]
- >>862はさすがに釣りだろお前ら釣られ杉
- 867 名前：デフォルトの名無しさん mailto:sage [2008/08/09(土) 18:40:27 ]
- ぐぐってもあまりいいページがないんだが、どこかに解説ない？＞M系列
- 868 名前：デフォルトの名無しさん mailto:sage [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になりますよ、と。ビット溢れによるマスクなども組み合わせているが。
- 869 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 03:11:08 ]
- 任意の長さのシフトレジスタで適当なタップを選んでフィードバックすれば
最長系列（Ｍ系列）が得られるんだが，
このタップが整数論の方の原始多項式から求められるというのは覚えてる
- 870 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 16:08:47 ]
- Cで保守の事を考えずに書いたときに保守しやすいのかといわれればもちろんNOだろ
素人が下手にCで最速コード書くと後で自分で読めないから、最初からアセンブリでやったほうがいいと思う
マクロが使えれば読みやすくなるのも事実だしな
MASMだと、アセンブリの癖にIFだのELSEだの使える。マクロがなければCでプリアセンブラを書けばいいし
- 871 名前：870 mailto:sage [2008/08/10(日) 16:10:30 ]
- 安価書き忘れ
>>860
- 872 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 17:38:03 ]
- CPU換えたときの心配してるんだったらC
- 873 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 17:55:59 ]
- スレタイも読めないバカが多いね。
移植性や保守性を犠牲にしてでも高速化しようってのが趣旨なのに。
- 874 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:16:42 ]
- 書かれてもいない事が見えるバカが居るんだね
- 875 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:25:56 ]
- 【高速化】ビット演算 0x02
- 876 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:31:54 ]
- やばいですやばいです
ちょっと暴走して勃起が止まりません
リセットできないどうしよう
- 877 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 18:35:44 ]
- 適切な勃起フラグを提げろ。
- 878 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 19:02:20 ]
- トシなのでフラグ立ちません！ どうしよう！
- 879 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 19:20:29 ]
- (´･ω･`)知らんがな
- 880 名前：デフォルトの名無しさん mailto:sage [2008/08/10(日) 19:20:34 ]
- ＞ 移植性や保守性を犠牲にしてでも
そりゃビット演算すれば多少は移植性が犠牲になるだろうけど、
それだけならぜんぜん問題にはならない。
所詮フラグなんて１本しかないんだからな。
ただまあ、
大きさはいろいろだから互換性がない場合も確かにある。
- 881 名前：デフォルトの名無しさん [2008/08/26(火) 15:29:02 ]
- ＊ + 巛 ヽ
〒 ! + 。 + 。 ＊ 。
+ 。 | |
＊ + / / イヤッッホォォォオオォオウ！
∧＿∧ / /
（´∀｀ / / + 。 + 。 ＊ 。
,- ｆ
/ ュヘ | ＊ + 。 + 。 +
〈＿｝ ） |
/ ! + 。 + + ＊
./ ,ヘ | このスレッドは８８０を超えました。
ガタン ||| j / | | ||| 次レスも…BITクオリティ！！
―――――――――――― pc8.2ch.net/tech/
ああ暇だ
- 882 名前：デフォルトの名無しさん mailto:sage [2008/08/27(水) 20:01:38 ]
- ちょっとリンク張らせてクレ。
science6.2ch.net/test/read.cgi/math/1209732803/
の427に問題を投稿したんで、暇ならチャレンジしておくれ。
- 883 名前：デフォルトの名無しさん mailto:sage [2008/08/27(水) 20:36:01 ]
- 算数得意だけど数学は苦手
- 884 名前：デフォルトの名無しさん mailto:sage [2008/09/04(木) 14:51:58 ]
- chessprogramming.wikispaces.com/Bitboards
ここまでくると、なにがなにやら
- 885 名前：デフォルトの名無しさん mailto:sage [2008/09/04(木) 15:15:42 ]
- 簡単じゃん
- 886 名前：デフォルトの名無しさん [2008/09/13(土) 20:24:38 ]
- (･∀･) ｶﾞｯｰ
- 887 名前：デフォルトの名無しさん mailto:sage [2008/09/14(日) 13:55:19 ]
- 発音できません＞＜
- 888 名前：デフォルトの名無しさん mailto:sage [2008/09/16(火) 23:19:16 ]
- ん？ヌルポはどこ？
- 889 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 01:25:58 ]
- >>888
888
- 890 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 16:29:38 ]
- 又ﾉﾚ木ﾟ
- 891 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 16:31:31 ]
- ガッ
- 892 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 17:12:10 ]
- 力ﾞっ
- 893 名前：デフォルトの名無しさん mailto:sage [2008/09/17(水) 19:24:05 ]
- >>890
その表記、キモすぎるｗ
- 894 名前：デフォルトの名無しさん [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;
という考え方で合ってます？
- 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 ]
- それ省略になってないし
|
 |
