ABC147 C問題-HonestOrUnkind2とbit全探索

変数iを定義して、1周するごとにiを1足す(i++)、i＜nの条件を満たさなくなったらループから抜ける、だが、
iをビット列に対応づけることで、上記のような組み合わせを全て検査することができ、これをbit全探索という。

例えば上記のように5個の要素が0か1を取ることを考えれば、
ループは
0(10進数)→00000(2進数)→(不良品,不良品,不良品,不良品,不良品)
1→00001→(不良品,不良品,不良品,不良品,良品)
2→00010→(不良品,不良品,不良品,良品,不良品)
…
31→11111→(良品,良品,良品,良品,良品)
と2^5回のループで、5つの製品がそれぞれ不良品,良品の場合について、全ての組み合わせを調べることができる。
計算量はO(2^n)

ABC147 C問題
https://atcoder.jp/contests/abc147/tasks/abc147_c
は15人が正直者か不親切な人かの2種類をとるので、bit全探索することができる。
bit全探索をしつつ、それぞれの証言が矛盾しないかどうかを検証していく。
計算量も2^15×ループの中身の処理数(証言の数はマックスで14^2個)　程度なので充分まにあう。
証言が矛盾しなかったら、その場合は正直者が何人になるのかカウントする。

カウントの方法。
ビット列と1の&を取って、1になるか0になるか判断した後、ビット列を1個右シフトする。
ビット列が0になるまでこれを繰り返して、1が何回出てきたかを数えれば、
ビット列の中に1がいくつ含まれているかカウント出来る。

例えば
11010 & 1 = 0
1101 & 1 = 1
110 & 1 = 0
11 & 1 = 1
1 & 1 = 1
答えが1になるのは3回あったので、11010に含まれる1の数は3。
良品不良品の話だったら、11010の場合は良品の数=3ということになる

コード例
https://atcoder.jp/contests/abc147/submissions/9092845

たぶん同じ考え方で3進数を使って状態が3つある場合も記述できるのだと思うが、
3進数を計算しやすいように作られていないので、むしろ2bitずつ区切って行うほうがやり易いのかもしれない
(実際はどうなのか知りません)