bit全探索と演算子優先順位(C++)

いままで全然論理演算子を使っていなかったのでここで不意打ちを食らって全然通らなくて悩んでいたのでまとめてみた。

基本的に、

代入系 ＜ 論理OR, AND ＜ ビットOR, NOT, AND ＜ 関係演算子 ＜ ビットシフト ＜ その他のやつ(四則演算てきな)

と覚えておけばよさそう。特にbit演算を使うような場面では特に太字部分に気を付けるとよいかもしれない。

atcoder.jp

はbit全探索を使う代表的な例だが、

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;

int main(){
    //1
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<int>> x(n);
    vector<vector<int>> y(n);
    rep(i, n){
        cin >> a.at(i);
        rep(j, a.at(i)){
            int x_ij, y_ij;
            cin >> x_ij >> y_ij;
            x.at(i).push_back(x_ij - 1);
            y.at(i).push_back(y_ij);
        }
    }

    //2
    int maxhonest = 0;
    bool possible;
    rep(bit, 1 << n){   //正直者1, 不親切な人0, n bit
    possible = true;
        rep(i, n){      //発言と正直者の一致を正直者のみ見ていく
            if((1<<i) & bit != 0){      //ここ間違い
                rep(j, a.at(i)){
                    if((bool)((1 << x.at(i).at(j)) & bit) != y.at(i).at(j)){
                        possible = false;
                        break;
                    }
                }
            }
            if(!possible) break;
        }
        if(possible) maxhonest = max(maxhonest, (int)__builtin_popcount(bit));
    }

    //3
    cout << maxhonest << endl;
}

としていて、なかなか間違いに気づかなかった。当然コメントした部分を

if(((1<<i) & bit) != 0){

とするべき。こういう比較演算子とbit演算子は特に気をつける部分かも。基本的に動作してほしい順にすべて括弧をくくっていけば良いと思う。