bit operation again SRM 422

topcder: BirthdayCake

用gcc的__builtin_popcount()速度快了两倍多。

由于cake 那个是50位的，用了long long，然后调用__builtin_popcount两次分别处理高低32位然后求和。注意给常数1加上LL后缀。

// couting 1's
inline int count_bit(long long n) {
    return __builtin_popcount(n>>32) + __builtin_popcount(n &((1LL<<32)-1LL));
}

void checkmax(int &a, int b) {
    if(a < b) a = b;
}

int BirthdayCake::howManyFriends(vector <string> availableFruits, vector <string> f, int K) {

    int N = availableFruits.size(); // total number of available fruit
    int m = f.size(); // friend number
    map<string,int> fruit;
    for(int i = 0; i < N; ++i)
        fruit.insert(make_pair(availableFruits[i], fruit.size()));

    long long mask = (1LL<<N)-1LL;
    vector<long long> like(m, mask);
    for(int i = 0; i < m; ++i) {
        stringstream ss;
        ss << f[i];
        string tmp;
        while(ss >> tmp) { 
            if(!fruit.count(tmp)) continue;
            like[i] &= ~(1LL<< fruit[tmp]); // clear uliked bits
        }
    }
    int max = (1<<(m))-1; // all friends included
    
    int maxnf = 0; // max number of friends included
    // brute force traversal of all subsets
    for(int i = max; i >=0 ; --i) {
        long long cake = mask;
        for(int j = 0; j < m; ++j) if( i & (1<<j) ) {
            cake &= like[j];
            if( count_bit(cake) < K )
                goto next;
        }
        checkmax(maxnf, count_bit(i));
next:   continue;
    }
    return maxnf;
}