bit全探索でやらかしたメモ（個人用）

概要

c++でbit全探索を実装しようとして、個人的に引っかかったところを紹介します。

問題個所

AtcoderさんのABC190のC問題（Bowls and Dishes）を解いていたときに問題が発生しました。

もともと、int型2次元配列 Putting_table[N][2] に対してbit全探索をするつもりでした。

つまり、想定していた動作としては N=3 のとき、

======
bit: 0
Putting table [0][0]
Putting table [1][0]
Putting table [2][0]
======
bit: 1
Putting table [0][1]
Putting table [1][0]
Putting table [2][0]
======
bit: 2
Putting table [0][0]
Putting table [1][1]
Putting table [2][0]
======
bit: 3
Putting table [0][1]
Putting table [1][1]
Putting table [2][0]
======
bit: 4
Putting table [0][0]
Putting table [1][0]
Putting table [2][1]
======
bit: 5
Putting table [0][1]
Putting table [1][0]
Putting table [2][1]
======
bit: 6
Putting table [0][0]
Putting table [1][1]
Putting table [2][1]
======
bit: 7
Putting table [0][1]
Putting table [1][1]
Putting table [2][1]

という感じでPutting tableの要素にアクセスすることを意図していました。

問題のコード

以上の想定動作に対して、当初は

for (int i = 0; i < 3; i++) {
      Putting_table[i][bit & (1 << i)]
}

という実装をすればよいものだと思っていました。

しかし、この実装を行うと

======
bit: 0
Putting table [0][0]
Putting table [1][0]
Putting table [2][0]
======
bit: 1
Putting table [0][1]
Putting table [1][0]
Putting table [2][0]
======
bit: 2
Putting table [0][0]
Putting table [1][2]
Putting table [2][0]
======
bit: 3
Putting table [0][1]
Putting table [1][2]
Putting table [2][0]
======
bit: 4
Putting table [0][0]
Putting table [1][0]
Putting table [2][4]
======
bit: 5
Putting table [0][1]
Putting table [1][0]
Putting table [2][4]
======
bit: 6
Putting table [0][0]
Putting table [1][2]
Putting table [2][4]
======
bit: 7
Putting table [0][1]
Putting table [1][2]
Putting table [2][4]

という出力結果になってしまい、最悪の場合 Segmentation Fault が起きてしまいます。

この理由は、例えばbit=7のときを考えると、

7&(1<<0) は バイナリで考えると、"111"&"001" という意味になり 1 が出力される一方、

7&(1<<1) のときは、"111"&"010" という意味になり 2 が

7&(1<<2) のときは、"111"&"100" という意味になり 4 が出力されてしまうからです。

どうすりゃよかったの？

先ほどのソースコードに少し手を加えて

for (int i = 0; i < 3; i++) {
      Putting_table[i][bit & (1 << i) ? 1 : 0]
}

とすればよさそうです。

c++ ではint型 0 はbool型 False に対応し、

int型 非0は bool型 True に対応するので、

それらを生かして三項演算子を使う感じですね。

追記

以下のサイトを見たところ、安易にint型 0 はbool型 False に対応し、int型 非0は bool型 True に対応すると決めつけてしまうのは良くなさそうですね。 www.pc-gear.com