ショートコーディング: Not演算

チルダみたいな記号「~」ってC/C++にあるけど、いつ使うのだろう。。

ショートコーダーは日常茶飯事に使う。

例えば、EOF。

EOFは多くのコンパイラでは-1である。そして整数の中で優一ビットをすべて反転した場合に0になるのが-1である。

while (scanf("%d", &n) != EOF)

を

while (~scanf("%d", &n))

と書いたりする。

最近、私がよく使うのは、bool値を配列に格納したい場合である。普通なら0で初期化して、0でなければ値が設定されているとすればいいが、boolの場合はFalseを設定すると0とみなされる。

なので、char型にboolをぶちこむ。そして、char配列は-1で初期化しておく。

すると、not値が0の場合は、値が未設定となるので、スマートなコーディングが可能となる。

boolをcharに入れるなんてメモリの無駄と思う人もいるかもしれないが、実は、C/C++ではboolはほとんどの環境では1byteである。。なので実は無駄じゃない。

で、boolをchar配列に入れて、not演算を使ってエレガントに値の設定を判別したコードがこちら。。

Nimという数取りゲームの一般形において先手に必勝手が存在するかどうかをゲーム木で判定しています。注目すべきは、solveの3行目です！

int n;
VI nums;
char memo[1<<15][22];

bool solve(int turn, int s) {
   if (!s) return true;
   if (~memo[s][turn])
       return memo[s][turn];

   turn %= (2*n);
   int ret = false;
   FOR (x, 1, nums[turn]+1)
       if (s-x >= 0)
           ret |= !solve(turn+1,s-x);

   return memo[s][turn] = ret;
}

int main() {
   while (scanf("%d", &n), n) {
       int s;
       scanf("%d", &s);
       nums.clear();
       memset(memo, 0xFF, sizeof(memo));
       int x;
       REP(i, 2*n) {
           scanf("%d", &x);
           nums.push_back(x);
       }
       printf("%d\n", (int)solve(0, s));
   }

   return 0;
}