08/08/01 03:07:44
2^a を渡されたときaを求める方法で何かいい物はありませんか？
なるべくループやlogを使わない物がいいです
752:750
08/08/01 03:26:58
>>751
追記、1≦a≦9
753:デフォルトの名無しさん
08/08/01 03:27:44
>>752
自分の名前間違えた>>750じゃなくて>>751
754:デフォルトの名無しさん
08/08/01 04:04:46
５１３個の配列持って、その中に１～９を入れておく。[1]=なし、[2]=1、[3]=なし、[4]=2、・・・
[512]=9 演算はこれが最速。
755:デフォルトの名無しさん
08/08/01 04:06:47
サイズが問題なら、
if( n & 0x200 ) return 9;
if( n & 0x100 ) return 8;
・・・
if( n & 0x002 ) return 1;
756:デフォルトの名無しさん
08/08/01 04:15:16
x86ならBSF
757:デフォルトの名無しさん
08/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; //解なし
}
758:デフォルトの名無しさん
08/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;
}
759:デフォルトの名無しさん
08/08/01 04:52:26
>>754-758
ありがとうございます。みんなカッコイイ
760:デフォルトの名無しさん
08/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すれば合うんじゃないかな。
761:デフォルトの名無しさん
08/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;
}
762:デフォルトの名無しさん
08/08/01 10:45:43
"_\0\5\1\10\6\2__\4\7_\3"[n*0xCA030FF>>28];
763:デフォルトの名無しさん
08/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];
764:762
08/08/01 16:32:34
あー間違えてたーthx
そしてそっちのハッシュのほうが優れているね。
765:デフォルトの名無しさん
08/08/01 16:55:45
なるほど、ハッシュってそういう使い方するんだ。
766:デフォルトの名無しさん
08/08/01 17:47:48
>>762-763
異次元過ぎてついて行けないのだが解説頼む
767:デフォルトの名無しさん
08/08/01 21:25:31
俺もわかってないが
gperfとかで完全ハッシュ関数を作るのと同じように
(文字列ではなく)特定の数字から対応する特定の数値への完全ハッシュ関数を作っているんだと思う。
どうやって導いたかなんて知らん。
768:デフォルトの名無しさん
08/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の４ビットのことか。
確かに小さいほうがメモリとキャッシュに優しいですな。
という感じであってますか。
>どうやって導いたかなんて知らん。
俺も知りたい。
769:デフォルトの名無しさん
08/08/02 01:52:05
頭良すぎる
770:デフォルトの名無しさん
08/08/02 01:56:27
2chってすげーな
771:デフォルトの名無しさん
08/08/02 10:03:58
ビット演算ってたしかにすごいけど、
ソースに組み込むときは、その演算の意味とメリットなど
ビット演算を導入した経緯や思想も書いてほしい・・・
ソース理解に時間がかかったり、修正が大変・・・
まあ、俺がお馬鹿なのかもしれないけど。
あと、763って751からの流れなんですか？
それとも別の流れ？
772:デフォルトの名無しさん
08/08/02 10:14:13
最後の2行から見ても明らかに
>まあ、俺がお馬鹿なのかもしれないけど。
が正解。
773:デフォルトの名無しさん
08/08/02 10:17:05
このスレって頭のいい奴もいるけど、
771みたいなバカもいる。
バカはROMっていろ！死ね771！！
774:それは俺か (w
08/08/02 10:59:13
まあ、バカにレスする奴はもっとバカだけどな。
775:デフォルトの名無しさん
08/08/02 11:02:09
1、2、4、8、16、32、64、128、256、512の完全最小ハッシュ値を作る。
URLﾘﾝｸ(www.ic-net.or.jp)
これか？
>>762は本当に頭がいい。>>763の書き込みがなかったら
意味も解らずスルーするところだった。
776:デフォルトの名無しさん
08/08/02 12:58:48
512の完全ハッシュを作ってそれを1～9のテーブルに掛けるって事？
分かった気がする。
777:デフォルトの名無しさん
08/08/02 13:59:12
>>775
でも、保守する奴が >>762 みたいに頭いいとは限らんから、
仕事のプログラムなら >>754-755 あたりのほうがいいと思う。
778:デフォルトの名無しさん
08/08/02 14:04:14
当たり前。こんなのは所詮パズル。商用コードでこんなの書けない。
>>762みたいなのが許されるのは趣味のプログラミングだけだよ。
779:デフォルトの名無しさん
08/08/02 16:19:14
後は極端に処理速度がネックになってるところとか、
ビックリするほど容量が無いプラットフォームとか、
コンパイラが準備されてなくてアセンブラで書かなきゃいけないような場合、
更にRISCみたいに見た目と実行順が違うような環境だと
読む量が少ない短いコードが逆に役に立つ。
自慢を理由に書くと間違いなく死を招く。
780:デフォルトの名無しさん
08/08/02 16:20:19
コメントで書いておけば十分じゃないかな。
今でもまだまだ、速度やサイズ重視の分野はあるし。だいぶ少なくはなっているけど。
781:デフォルトの名無しさん
08/08/02 16:32:12
現状、用途として大きそうなのはシェーダー周りか。
782:デフォルトの名無しさん
08/08/02 16:36:45
画像処理ならいくらでも速度欲しいけどな
783:デフォルトの名無しさん
08/08/02 16:49:03
昔、VUアセンブラの実装をしたが、ライブラリの増加により俺の約700byteのプログラムが
入らなくなり削りに削って「400byteだけ下さい！」と上司に嘆願したのは懐かしい思い出。
784:デフォルトの名無しさん
08/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;
785:デフォルトの名無しさん
08/08/03 02:24:01
一番右の1を探すとき~a&(a-1)でできますよね、じゃあ一番左の1を探すときは何かありませんか?
786:デフォルトの名無しさん
08/08/03 02:37:33
掛け算が４回・割り算が１回ってのが、演算量的に・・・ 俺が8bitに慣れてるからかな？
64bit整数があるにしても、nが32bitならn*nで64bitでしょ。中間結果でbitが失われるんじゃ？
787:デフォルトの名無しさん
08/08/03 02:40:55
>>785 754とか755じゃダメなの？もっと速い／小さいのってこと？
788:デフォルトの名無しさん
08/08/03 02:55:56
>>785
関係ないがa&(-a)で右端の一ビットを得られるぞ、左端は無理じゃないか
789:デフォルトの名無しさん
08/08/03 03:17:47
URLﾘﾝｸ(www.nminoru.jp)
790:デフォルトの名無しさん
08/08/03 03:41:51
>>787-789
どうもです、今見た資料に左端を操作する命令列は存在しないって書いてあったorz
791:デフォルトの名無しさん
08/08/03 03:56:21
左右反転するビット演算子でもあればね
792:デフォルトの名無しさん
08/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 );
793:784
08/08/03 17:00:12
>>786
もちろん変数n は64ビット長
LP64なら long型だと思ってもらえばいいです
演算量については、いまどきの投機実行するCPUなら
下手に条件判定入るよりは速いと思うけど、・・・まあ状況次第ですね
794:デフォルトの名無しさん
08/08/03 17:25:07
ｎが64bitでも、n*n*n*n の中間結果はbit失われるでそ。
795:デフォルトの名無しさん
08/08/03 18:31:31
でも、仕事に使うとなると、
「シンプルにしようや」
で終わってしまうんですよね～
そうすると、754や755に落ち着くのかな・・・
796:デフォルトの名無しさん
08/08/03 19:39:21
そりゃそうだよ。
よほど特段の理由が無い限り、シンプルが一番。
797:デフォルトの名無しさん
08/08/03 19:51:28
裸が一番いいのと一緒だ
798:デフォルトの名無しさん
08/08/03 21:10:39
>>794
2^9まででしょ？
799:デフォルトの名無しさん
08/08/03 21:12:54
は？
800:デフォルトの名無しさん
08/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
これに規則性みたいなものを感じるんですが、
何か法則があるんでしょうか？
801:デフォルトの名無しさん
08/08/03 21:54:51
初めの3つはともかく、
9*9=81
99*99=9801
999*999=998001
と同じようなもんだろ
802:デフォルトの名無しさん
08/08/03 22:06:41
よくわからんが、ビット演算とかって、日本人よりも
インド人のほうが面白い発想しそうだね
803:デフォルトの名無しさん
08/08/03 22:09:36
>>800-801
２進数に考えれば、最初から綺麗に並ぶよ。
1 * 1 = 1
11 * 11 = 1001
111 * 111 = 11001
1111 * 1111 = 11100001
11111 * 1111 = 1111000001
804:デフォルトの名無しさん
08/08/03 22:16:49
0xffff * 0x10000 => 0xffff0000
0xffff0000 - 0xffff => 0xfffe0001
特に面白い事実はなさそうだが
805:デフォルトの名無しさん
08/08/03 22:21:59
99*99=9801
これが国民機ナンバーの正体かー
すると8801は？
93.8136 * 93.8136 = 8800.99
収束しないのか
806:デフォルトの名無しさん
08/08/03 22:22:36
収束？
807:デフォルトの名無しさん
08/08/03 22:25:25
ごめん適当言った
808:デフォルトの名無しさん
08/08/03 22:34:48
無理数ね。
809:デフォルトの名無しさん
08/08/03 23:10:51
λ... PC-8001, PC8201, PC-6001, &c. ...
810:デフォルトの名無しさん
08/08/03 23:48:03
獣の数字にまつわる屁理屈と同じようなもんだな
あえて8801に意味を見出すなら99*99-1100とかなんとか
811:デフォルトの名無しさん
08/08/03 23:49:53
9801-1100 = 8701だな
俺頭大丈夫ｋ
812:デフォルトの名無しさん
08/08/04 00:08:26
PC9801が長いこと繁栄したのは99*99=9801
こういった力(ちから)を持つ数字が隠されていた影響に違いない。
その証拠に型番が9821に変わろうとしたとたん没落した。
きっと9801のままなら永遠の存在だったんだよ。
813:デフォルトの名無しさん
08/08/04 00:11:55
>>798 そうか、9bitのハッシュのエレガントな解法だったのね。ごめん。
ハッシュって、必要の都度、bit数見極めて作らなきゃいけないんだな・・・
814:デフォルトの名無しさん
08/08/04 01:24:27
実際に仕事でも使用可能な、
1.実用性がある
2.比較的わかりやすい
ビット演算のアルゴリズムって何だろうね・・・
815:デフォルトの名無しさん
08/08/04 01:50:11
名前がつくぐらい有名になればいいんじゃないかな。
例えばコメントに
// 762氏ハッシュ
とか書けるぐらいに。
816:デフォルトの名無しさん
08/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"がいまいち良くわかりません。
817:デフォルトの名無しさん
08/08/04 02:06:28
ただの文字列リテラルだよ
818:デフォルトの名無しさん
08/08/04 02:06:59
コメントに、「ハッシュがどうの」なんて書く奴ばっかだからダメなんだよ。
コメントに絶対に書かなきゃいけないのは、>>751-752だよ。
どういう実装をしたかのコメントなんて二の次三の次。
それなのに仕様のコメントを怠ったままで「すげーテクニック使ってるんだぜ」的なコメントを残しても意味なし。
そんなものを残すぐらいなら、(最低限の>>751-752の他に)assertでも使った範囲チェック入れとけ。
もちろん、>>762のやり方に対するコメント(完全ハッシュ関数とテーブル)はあった方が良い。
けど、仕様についてのコメントの方がはるかに重要。
819:デフォルトの名無しさん
08/08/04 03:06:57
日本語でおｋ
820:デフォルトの名無しさん
08/08/04 03:45:03
日本人でおｋ
821:デフォルトの名無しさん
08/08/04 04:32:52
二本イレマスカ？
822:デフォルトの名無しさん
08/08/04 04:59:25
イマレス
823:デフォルトの名無しさん
08/08/04 08:02:17
#if 0 // オリジナルのロジック
...;
#else // 速度重視で書き換え
...;
#endif
824:デフォルトの名無しさん
08/08/04 08:15:04
"..."[...]という書き方をこの流れで始めて知った
何でこのスレにいるかって？
知るために見ているのさ
825:デフォルトの名無しさん
08/08/04 09:53:07
K&Rの頃のCをやってた人間からすれば常識
826:デフォルトの名無しさん
08/08/04 12:37:57
>>816 文字リテラル "abc"とかならキャラ型の配列だって判るでしょ。
スペース（0x20）より小さい値のcharは 「\８進数」 で書く約束になってる。
"\1\2\3・・・"は、char xxx[ ]={ 1, 2, 3, ・・・, 0 };という配列が生成される。
827:デフォルトの名無しさん
08/08/04 13:33:40
>>826
＞スペース（0x20）より小さい値のcharは 「\８進数」 で書く約束になってる。
なってない。
828:デフォルトの名無しさん
08/08/04 17:24:05
\001 \002 \017 とかだよ。 Hexの場合は \xhh と書く約束になってる。
俺のはLSIC85とか adUc51とか、クミコ系ばっかりで、ANSIは知らないけど。
829:デフォルトの名無しさん
08/08/04 18:13:00
0x20以上の値で使ってはいけないという決まりもないわけで。
830:デフォルトの名無しさん
08/08/04 22:15:16
最下位8bitについてなら左右を逆転するコードあった筈
こんな感じだったと思うけど、よく覚えてないや
x:src y:dest
s=(x*0x02020202)&0x84422010
t=(x<<3)&0x420
y=(s+t)%1023
831:デフォルトの名無しさん
08/08/04 22:49:39
>>792で既出だべ。
832:デフォルトの名無しさん
08/08/04 23:59:20
>>828
\n \t \r とかもあるわけで。
833:デフォルトの名無しさん
08/08/05 00:45:34
>>832
は？
834:デフォルトの名無しさん
08/08/05 01:21:35
文字リテラルが配列の名前？？？
どうも「文字リテラル＋[]」が良くわからん。
ビット演算うんぬんではなく・・・
C言語でこれを書いてコンパイルが通るのか？
どうもこのスレに付き合うには、大学などできちんと学ぶか
元々、この手のことが好きじゃないとついていけませんね・・・
社会人になってから、プログラムを覚えたアホアホな俺の
プリンみたいな脳みそでは、だめかorz
835:デフォルトの名無しさん
08/08/05 01:37:17
なんでワカラン？？？ 大学とか関係ないぞ。
char * buf = "01234567";
char a = buf[0];
が判れば、
char a = "01234567"[0];
だって判るだろ。
836:デフォルトの名無しさん
08/08/05 01:41:46
char a = 0["01234567"];
こんなのもある。これが直感的に納得しづらいというのはワカランでもないけど、
char a = "01234567"[0];
こっちは普通だべ。
837:デフォルトの名無しさん
08/08/05 09:00:56
>>834
>元々、この手のことが好きじゃないとついていけませんね・・・
当たり前だと思うんだが。
838:デフォルトの名無しさん
08/08/05 10:50:52
文字列定数がメモリ空間に配置されている状態をイメージできていないんだな。
プロセスメモリエディタかバイナリエディタと睨めっこでもしてみればいいんじゃね。
839:デフォルトの名無しさん
08/08/05 12:25:02
文字列リテラルは、コンパイラがDATAやTEXTのようなセグメントに配置して
プログラムの中に埋め込まれるちょっと特殊なchar[]にすぎん。
"hoge"とか書いた場合、これはそういう配列を暗黙にどっかに確保しろよと
コンパイラに言っているのと同時に、式の中で評価されるときは、その（無名の）
char配列の名前と同等に扱われる。
要はchar[]なのだから、char*な変数に文字列リテラルを代入したり
printf()のような関数に文字列リテラルを引数として渡したり、ということは
普通に・当然のようにやっているはずだ。
さすがにprintf("hello, world"); というコードを見たことが無いとは言わせない。
ならば、[]演算子を適用できるということも当然分かるはずだな。
多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。
840:デフォルトの名無しさん
08/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]; ならわかるだろ。。
841:デフォルトの名無しさん
08/08/05 13:15:16
おそらくは、
配列の名前[インデックス]
のように教えてる参考書の類が悪いんだろう。
842:デフォルトの名無しさん
08/08/05 15:15:59
>>834
このスレ開いただけでも望みはある！
843:デフォルトの名無しさん
08/08/05 18:04:55
すごいな。叩きが日常の2chで、ｼﾛｰﾄにここまで優しいのは、久しぶりに見た。
844:デフォルトの名無しさん
08/08/05 19:53:06
>>838
メモリをイメージする訓練も大切だが、
もっと抽象的に捉える訓練も忘れないで欲しいな。
845:デフォルトの名無しさん
08/08/05 20:05:18
そうだなー、最近そういうトレーニング怠ってるかも…俺。
846:デフォルトの名無しさん
08/08/05 21:13:44
>>841
真の文法を書いてる本は稀少なのかね。
847:デフォルトの名無しさん
08/08/05 21:27:48
>>846
真の文法を書いている本でも、いでおしんくらてっぃくなところは
はしょっているか、読み取れないようにしてるのが多いと思う。
実際、俺なんか、
int typedef integer;
なんて構文が許されるなどとはイソターネットで初めて知った。
848:デフォルトの名無しさん
08/08/05 21:44:04
なるほど、許されない理由がないから許されるんだな。
849:デフォルトの名無しさん
08/08/05 21:47:55
もしかして：void main(void)
850:デフォルトの名無しさん
08/08/05 22:11:34
>>846
真の文法をサポートする本とはLinuxのことである。
Linux以外は紛い物である。
851:デフォルトの名無しさん
08/08/06 00:58:33
>>833
いや、意味が理解できないなら別にいいんだ。
>>839-841
C/C++ に毒されすぎ (w
文字列と文字の配列が互換の言語はあまり多くないから、
"abcd"[0] を >>834 が奇異に感じるのも無理は無いよ。
852:デフォルトの名無しさん
08/08/06 00:59:35
[]はmonadの一種でしょ
853:デフォルトの名無しさん
08/08/06 01:15:22
みなさん、あほな俺に丁寧にありがとう。
さすがに理解できました。
＞多分、そういうコードを今まで見たことが無い、見慣れない、ってだけだろう。
そうですね。はじめてみました。
なんかすっきりしました。
皆さんありがとうございました。
なんかビット演算って難しそうですけど、面白そうですね。
私も、最近処理速度を意識したコードを書く機会があるので
色々参考にします。
（クロックが25KHzなので、処理速度を意識しないといけないんですよ）
854:デフォルトの名無しさん
08/08/06 01:31:44
ずいぶん遅くない？ 8ビット機のときもMHzだったが。。。
855:デフォルトの名無しさん
08/08/06 09:28:35
ケルビン・ヘルツという単位は寡聞にして知らない。
856:デフォルトの名無しさん
08/08/06 21:19:11
＞ずいぶん遅くない？
そうなんですよ。1サイクル40usなので、ビット操作（ビットクリアやビットセット）で
7サイクル取られるので、7*40=280us=0.28msもかかるんですよね・・・
857:デフォルトの名無しさん
08/08/06 21:30:37
えー！ そりゃ遅い。なんだろ。FPGAかなんかか。
最近は組み込みの分野でもJAVAだったりするが、まだまだCの出番はあるってことか。
858:デフォルトの名無しさん
08/08/06 22:00:42
ボタン電池1個で半年動かすようなものなんじゃね？
859:デフォルトの名無しさん
08/08/06 22:06:20
>>857
> まだまだCの出番はあるってことか。
て言うか、アセンブラの出番だと思うけど。
860:デフォルトの名無しさん
08/08/06 22:17:37
Cで書く予定です。アセンブラでは保守のことを考えると難しいので。
如何にCで効率の良いコードを書くか。
クロックを遅くしているのは消費電流の低減のためです。
普段は32MHzで動作しますよ。
861:デフォルトの名無しさん
08/08/09 17:23:46
>>767-768
ちょっと遅くなったが、求め方が解った。
今回は2^1～2^9だからちょっと変則的なんだが、概念としてはM系列の応用みたい。
なるほどねー。
URLﾘﾝｸ(slashdot.jp)
862:デフォルトの名無しさん
08/08/09 17:25:18
>>861
お前ここに糞スラのURL張るの禁止されていること
しらんのか？
863:デフォルトの名無しさん
08/08/09 17:27:12
スラッシュドット禁止ってどんだけ情報弱者なんだよ。
え？あっちから拒絶してんの？
864:デフォルトの名無しさん
08/08/09 17:27:38
あれ？ 板ルール？
スマンかった。忘れて。
865:861
08/08/09 17:31:07
>>863
あっちも出入りしているけど、そういうことはないと思う。
ここの板ローカルのルールなのかね？
ここも長年見ているが、あまり聞いたことないけど。
866:デフォルトの名無しさん
08/08/09 18:01:21
>>862はさすがに釣りだろお前ら釣られ杉
867:デフォルトの名無しさん
08/08/09 18:40:27
ぐぐってもあまりいいページがないんだが、どこかに解説ない？＞M系列
868:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/08/10 03:11:08
任意の長さのシフトレジスタで適当なタップを選んでフィードバックすれば
最長系列（Ｍ系列）が得られるんだが，
このタップが整数論の方の原始多項式から求められるというのは覚えてる
870:デフォルトの名無しさん
08/08/10 16:08:47
Cで保守の事を考えずに書いたときに保守しやすいのかといわれればもちろんNOだろ
素人が下手にCで最速コード書くと後で自分で読めないから、最初からアセンブリでやったほうがいいと思う
マクロが使えれば読みやすくなるのも事実だしな
MASMだと、アセンブリの癖にIFだのELSEだの使える。マクロがなければCでプリアセンブラを書けばいいし
871:870
08/08/10 16:10:30
安価書き忘れ
>>860
872:デフォルトの名無しさん
08/08/10 17:38:03
CPU換えたときの心配してるんだったらC
873:デフォルトの名無しさん
08/08/10 17:55:59
スレタイも読めないバカが多いね。
移植性や保守性を犠牲にしてでも高速化しようってのが趣旨なのに。
874:デフォルトの名無しさん
08/08/10 18:16:42
書かれてもいない事が見えるバカが居るんだね
875:デフォルトの名無しさん
08/08/10 18:25:56
【高速化】ビット演算 0x02
876:デフォルトの名無しさん
08/08/10 18:31:54
やばいですやばいです
ちょっと暴走して勃起が止まりません
リセットできないどうしよう
877:デフォルトの名無しさん
08/08/10 18:35:44
適切な勃起フラグを提げろ。
878:デフォルトの名無しさん
08/08/10 19:02:20
トシなのでフラグ立ちません！ どうしよう！
879:デフォルトの名無しさん
08/08/10 19:20:29
(´･ω･`)知らんがな
880:デフォルトの名無しさん
08/08/10 19:20:34
＞ 移植性や保守性を犠牲にしてでも
そりゃビット演算すれば多少は移植性が犠牲になるだろうけど、
それだけならぜんぜん問題にはならない。
所詮フラグなんて１本しかないんだからな。
ただまあ、
大きさはいろいろだから互換性がない場合も確かにある。
881:デフォルトの名無しさん
08/08/26 15:29:02
＊ + 巛 ヽ
〒 ! + 。 + 。 ＊ 。
+ 。 | |
＊ + / / イヤッッホォォォオオォオウ！
∧＿∧ / /
（´∀｀ / / + 。 + 。 ＊ 。
,- ｆ
/ ュヘ | ＊ + 。 + 。 +
〈＿｝ ） |
/ ! + 。 + + ＊
./ ,ヘ | このスレッドは８８０を超えました。
ガタン ||| j / | | ||| 次レスも…BITクオリティ！！
―――――― URLﾘﾝｸ(pc8.2ch.net)
ああ暇だ
882:デフォルトの名無しさん
08/08/27 20:01:38
ちょっとリンク張らせてクレ。
ｽﾚﾘﾝｸ(math板)
の427に問題を投稿したんで、暇ならチャレンジしておくれ。
883:デフォルトの名無しさん
08/08/27 20:36:01
算数得意だけど数学は苦手
884:デフォルトの名無しさん
08/09/04 14:51:58
URLﾘﾝｸ(chessprogramming.wikispaces.com)
ここまでくると、なにがなにやら
885:デフォルトの名無しさん
08/09/04 15:15:42
簡単じゃん
886:デフォルトの名無しさん
08/09/13 20:24:38
(･∀･) ｶﾞｯｰ
887:デフォルトの名無しさん
08/09/14 13:55:19
発音できません＞＜
888:デフォルトの名無しさん
08/09/16 23:19:16
ん？ヌルポはどこ？
889:デフォルトの名無しさん
08/09/17 01:25:58
>>888
888
890:デフォルトの名無しさん
08/09/17 16:29:38
又ﾉﾚ木ﾟ
891:デフォルトの名無しさん
08/09/17 16:31:31
ガッ
892:デフォルトの名無しさん
08/09/17 17:12:10
力ﾞっ
893:デフォルトの名無しさん
08/09/17 19:24:05
>>890
その表記、キモすぎるｗ
894:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/09/27 11:13:01
合ってる。
896:デフォルトの名無しさん
08/09/27 11:29:26
どうも
897:,,・´∀｀・,,）っ-○◎●
08/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:,,・´∀｀・,,）っ-○◎●
08/09/27 12:31:00
しかし、2項選択は多くのＣＰＵでは分岐命令に展開されるので一般的には遅い。
日本語しゃべれ俺
899:デフォルトの名無しさん
08/09/27 13:06:59
> bit8 = bit4 | (bit4 & 0x8) ? 0xF0 : 0;
バグってるぞ。
900:,,・´∀｀・,,）っ-○◎●
08/09/27 13:13:06
bit8 = bit4 | ((bit4 & 0x8) ? 0xF0 : 0);
これでいいのか？
901:894
08/09/27 13:35:56
なるほどsingned型って右シフトで上位ビットを補ってくれるのね。
CPUは普通のPCのIntel x86系です。
902:,,・´∀｀・,,）っ-○◎●
08/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:デフォルトの名無しさん
08/09/27 19:47:32
>>895
ちがうだろ
算術シフトか論理シフトかはコンパイラ依存
904:デフォルトの名無しさん
08/09/27 19:50:09
100レスくらいで終わってもよさそうなのに実によく伸びるなこのスレ。
905:,,・´∀｀・,,）っ-○◎●
08/09/27 22:02:58
まあメジャーなコンパイラならsignedで算術シフトになるけどね。
//でコメントにならないコンパイラ並みには非互換問題あるのかな？
ローテートくらいまではC/C++標準仕様に入れておいて欲しいものだ
906:デフォルトの名無しさん
08/09/27 22:19:03
分岐は
907:デフォルトの名無しさん
08/09/27 22:26:53
>>903
> 算術シフトか論理シフトかはコンパイラ依存
負数の右シフトの動作のことを言ってるのか？
>> 2の補数で表される4bitの値を8bitに変換する場合
という条件下なら >>894 の内容に誤りはないと思うが。
そもそも、>>894 のレスにシフトのコードなんてないし。
# レスアンカーが >>897 なら同意するけど、あまり
# 触らない方がいいと思う。
908:,,・´∀｀・,,）っ-○◎●
08/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:デフォルトの名無しさん
08/09/27 22:33:41
ダンゴさんの星が落ち着いてきたな
910:デフォルトの名無しさん
08/09/28 12:15:36
表引きもいいけど、キャッシュ容量とかミスヒットとか気になるし、
算術シフトもちょっと……という場合にはこっちがいいのでは。
bit8 = -(bit4 & 0x8) | bit4
911:デフォルトの名無しさん
08/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:,,・´∀｀・,,）っ-○◎●
08/09/28 12:34:50
この程度の小さいテーブルなら表引きは割と効果あるよ。
SSSE3のpshufbやAltiVecのvpermで16並列化もできるし。
913:,,・´∀｀・,,）っ-○◎●
08/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:デフォルトの名無しさん
08/10/11 16:18:31
Cで上手いことローテート命令に割り当てられるような書き方って何かある？
今は、8ビットローテートの場合は
(val << num) | (val >> (8-num) )
って書いてるけど、アセンブラ見てもまんまシフトとORで作られるんだよな
最後の手段でインラインアセンブラ使ってるけど、誰かＣでいい書き方知ってたら教えてくれ
915:デフォルトの名無しさん
08/10/11 16:23:26
そもそもローテート演算子がないからローテートを出力するコンパイラがないんじゃ
916:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/11 16:48:33
ダンゴさんならローテートの速度について一言ありそうだな
918:914
08/10/11 16:51:22
あぁ、コンパイラのオプション弄ったらちゃんとローテートになったわ
ちなみにCPUはARM、コンパイラはARM製のコンパイラです
速度に関しては何ビットローテートしても1クロックで済む、RISC万歳
919:デフォルトの名無しさん
08/10/11 17:56:35
>>914
インラインアセンブラで書いたものを、インライン展開できるようにしておくのはダメなの？
インラインの関数呼び出しでは不満？
演算子でやりたいなら、演算子をインライン展開できるように定義すればいいだけだと思うが。
920:,,・´∀｀・,,）っ-○◎●
08/10/12 14:47:04
>><とか <<>とかみたいな演算子を逆輸入してくれれば良いんだがねぇ
921:デフォルトの名無しさん
08/10/13 21:04:47
無理に演算子にしなくても、
コンパイラが認識する組込関数にすれば十分だよ。
922:デフォルトの名無しさん
08/10/19 21:43:35
このほうがローテートっぽい
@>
<@
923:デフォルトの名無しさん
08/10/19 21:49:25
>reg>
<reg<
924:デフォルトの名無しさん
08/10/19 22:01:01
㊨
㊧
925:デフォルトの名無しさん
08/10/20 01:05:00
_lrotr
_lrotl
926:デフォルトの名無しさん
08/10/20 15:43:41
|>
<|
927:デフォルトの名無しさん
08/10/20 22:06:50
>>925
指輪物語?
>>926
シュレディンガー音頭?
928:デフォルトの名無しさん
08/10/21 08:56:43
記号の演算子じゃなくて普通に単語使えばいいのに
ばかでしょ
929:デフォルトの名無しさん
08/10/21 23:59:57
指輪物語はlotrだなｗ
930:デフォルトの名無しさん
08/10/22 00:38:04
>>929
tlotr
931:デフォルトの名無しさん
08/10/22 00:46:10
公式はLOTR
932:デフォルトの名無しさん
08/10/22 00:53:09
なんで指輪物語スレになってんの・・・
933:デフォルトの名無しさん
08/10/22 00:56:14
>>931
tlotr
ググれば一目瞭然。
934:デフォルトの名無しさん
08/10/22 04:08:26
The Lord of the Rings だし。
935:デフォルトの名無しさん
08/10/22 08:55:55
Lordsな。両方複数系。
936:デフォルトの名無しさん
08/10/22 12:18:22
URLﾘﾝｸ(www.lordoftherings.net)
つまり、オフィシャルサイトは間違っていると。
937:デフォルトの名無しさん
08/10/22 12:34:52
>>935
Lordが正しい。
>>936
「the」がないのは、ドメイン取得の問題じゃないかな。
938:デフォルトの名無しさん
08/10/22 16:44:03
何時の間にか指輪スレ化している流れを豚切。
man gawk を見ると
lshift, rshift って内部関数が実装されているんだな。
939:デフォルトの名無しさん
08/10/22 21:50:42
>>925もVC++独自のローテート関数なわけだが。
指輪とはあんまり関係ない。
940:デフォルトの名無しさん
08/10/22 21:59:17
指輪物語とまで云うならthe fellowship of the ringだろ
941:,,・´∀｀・,,）っ-○◎○
08/10/23 01:44:47
lotrをロートルと呼ぼうのスレはここですか？
>>940それ第１章の副題
942:デフォルトの名無しさん
08/10/23 08:38:48
>>941
何…だと……？
943:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/25 01:12:27
流れぶったぎって次スレ案
【指輪】ビット演算 0x03【物語】
945:デフォルトの名無しさん
08/10/25 01:13:31
いや、つまんないから
946:デフォルトの名無しさん
08/10/25 01:17:20
つーかもうスレ自体不要
947:デフォルトの名無しさん
08/10/25 17:26:25
>>944
これはコラだね、俺は騙されんよ。
948:デフォルトの名無しさん
08/10/25 18:44:44
>>947
>>945
949:デフォルトの名無しさん
08/10/25 18:53:14
>>948
>947
950:デフォルトの名無しさん
08/10/25 21:52:57
>>944-950
>>9
951:デフォルトの名無しさん
08/10/26 20:50:31
>>943
それは省略形であって正式ではない。
テレビジョンよりテレビの方がヒットするのは当たり前だろ。アホか。
952:デフォルトの名無しさん
08/10/26 21:00:55
0を移動していくシフト演算っていい方法ある？
111111011
↓
111110111
↓
111101111
↓
111011111
こう言う感じで
953:デフォルトの名無しさん
08/10/26 21:02:22
a << 1
a | 1
954:デフォルトの名無しさん
08/10/26 21:06:31
>>953
速レスサントス
955:,,・´∀｀・,,）っ-●◎○
08/10/26 21:10:29
逆に考えるんだ
1のほうを立てて
00000100
↓
00001000
↓
00010000
↓
00100000
参照するときに反転すればいいと考えるんだ
956:デフォルトの名無しさん
08/10/26 23:24:33
URLﾘﾝｸ(www.amazon.co.jp)
957:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/10/26 23:54:28
マジで>>944か>>946でいいような気がしてきた
もうどうでもいいよ
959:デフォルトの名無しさん
08/10/27 00:08:36
それ省略になってないし