・500GBのHDDに500GBのファイルを置いて消す場合(ext2), rmだと12分近くかかった.
再フォーマットなら3分ぐらいですんだが, ちと乱暴すぎる. 何かいい方法はないだろうか.
・また料金の一部を改定したらしい. いっその事「時価」にしたらどうだろう.
流出が多ければ高く, 流入が多ければ安く. 名付けて利益定額サービス.
bool org(int x)
{
static bool s = false;
static int p = -1;
assert(x < 32);
if (x == p) {
s = !s;
} else {
s = (x == 1 || x == 4);
p = x;
}
return s;
}
要は前回と同じ値なら, 前回と反対の真偽値を, そうでなければ1か4のときのみtrueを返せというもの(ここでは問題自体の是非は問わない).
小次郎さんによる現在の最善解は
/*
@retval 0 if false
@retval !0 if true
*/
int ans1(int x)
{
static const uint32 D = (1 << 4) | (1 << 1);
static uint32 s = D;
uint32 m = 1 << x;
uint32 r = s & m;
s = ~r & (D | m);
return r;
}
なんと, わずか5個のビット演算. 感心する点は二つ.
一つはオリジナルの(x == 1 || x == 4)のところの特殊値の比較が増えても演算量は変わらない点.
もう一つは前回の真偽値と位置の二つのstatic変数を一つですませた点. お見事.
金子光晴がもっともたいせつにしたのは「個人」というものでした。 国家権力にも強制された思想にも、そっぽをむいて、 「自分自身の頭で考える、自分自身のからだで感じとる」という根本の権利を、 なにものにもゆずりわたそうとしませんでした。
これはごくあたりまえで、単純なことのようにみえますが、日本人にとって、 もっともにがてなことなのでした。
歴史をふりかえってみれば、その時々の権力に、 思考力まであずけっぱなしという例はいくつもみつけだすことができるでしょう。
八つの惑星すべてと冥王星の素顔を撮影し3年前の本なのに何故か冥王星が別枠. 恐るべし.
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 calc(i+1, i) 0 0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5これを見ると2巾のところは半分です. それ以外でも2で割るとよいところがちらほら. これは偶然ではないだろうといくつシフトすればなるのか調べてみました.
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 calc(i+1, i) 0 0 1 0 2 1 3 0 4 2 5 1 6 3 7 0 8 4 9 2 10 5 シフト数 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2お, 扱い易そうな数値が出てきています. 一つ置きに1. これは一体なんだろう.
i 0の数 +1
00001 0 1
00010 1 2
00011 0 1
00100 2 3
00101 0 1
00110 1 2
00111 0 1
01000 3 4
01001 0 1
01010 1 2
01011 0 1
01100 2 3
01101 0 1
01110 1 2
01111 0 1
10000 4 5
どんぴしゃです. さて下から並んだ0の数の数え方ですが, これは定石があります.
0が並んでいるところから1を引くとその部分は繰り下がって全て1になり,
それは初めて1があるところまで続きます. 従ってそれらを xor すると,
初めて1がたつところより大きいところは消えるのです.
┌下から見て初めての1
v
x = ? ? ? 1 0 0 ... 0 0 ; ? は 0 または 1
x - 1 = ? ? ? 0 1 1 ... 1 1
---------------------------
x^(x-1)= 0 0 0 1 1 1 ... 1 1
ここで 2 を底とした対数関数を越えない最大の数を返す関数 [log2 x]
が登場します. 大昔書きましたが,
x を浮動小数で表すと指数部 e - 127 がまさにそれを表します.
x = 2e - 127 1.f とすると
bit |31|30 23|22 0| x = |s | e | f |だから, それは下に書いたように
int ilog2(unsigned int x)
{
float a = (float)x;
return (*(unsigned int*)&a >> 23) - 127;
}
となるわけです. これで斜辺のときはうまく行きました.
ここまでくればこれを2次元に拡張するのは(幸い)容易です.
int FindBit(unsigned int x)
{
if (x == 0) { return 0; }
unsigned int y;
int n = 1;
y = x & 0xffff0000; if (y != 0) { x = y; n += 16; }
y = x & 0xff00ff00; if (y != 0) { x = y; n += 8; }
y = x & 0xf0f0f0f0; if (y != 0) { x = y; n += 4; }
y = x & 0xcccccccc; if (y != 0) { x = y; n += 2; }
y = x & 0xaaaaaaaa; if (y != 0) { x = y; n += 1; }
return n;
}
はビット長 + 1を求めているので x == 0 を除いては bsr + 1 と同じです.
int FindBit2(unsigned int x)
{
if (x == 0) return 0;
__asm {
bsr eax, x
inc eax
}
}
Cの範囲で記述するなら s < 22 という制限の元では
int FindBit3(unsigned int x)
{
if (x == 0) return 0;
float a = (float)x;
return (*(int*)&a >> 23) - 126;
}
という処理もあります.
FPUレジスタをいじってよいなら
_controlfp(_RC_DOWN, _MCW_RC);
と丸め処理を切り捨てモードにすることで(Linuxなら_FPU_SETCW())上記の s の制限をとることもできます.
単独なら bsr が最適解とおもいますが, FindBit3はSSE2を使えばメモリを介さず複数個同時処理できるのでこっちの方がよいと思います.
dskさんのテーブル引き(FindBit4)はアドレスが決まるまでテーブル引きができない場所が続いてしまうので今回のケースでは遅くなるようです.
int x = 0x1234567;
int sum = 0;
int begin = clock();
for (i = 0; i < 100000000; i++) {
unsigned int y = x;// & ((1<<25) - 1);
sum += FindBit(y);
x *= x + 0x12345;
}
で実行時間を測ってみると(@P4D 2.8GHz + VC2005),
1～4で1.92, 0.47, 1.33, 18.08(単位:sec)でした.
int ilog2(unsigned int x)
{
#ifdef WIN32
__asm {
bsr eax, x
}
#else
float a = (float)x;
return (*(unsigned int*)&a >> 23) - 127;
#endif
}
int calc(int a, int b, int s)
{
return b >> (ilog2(b ^ a) + 1);
}
でした(a != bなので x != 0 も仮定できる). 面白いことに s に依存してません.
FindBit()の引数が異なるのですが結果は同じっぽいですね. 何故だろう.