Count of pairs whose bitwise AND is a power of 2 O(n)
long countPairs(const vector<int>& arr) { long ans=0; int mx=0; map<int,int> mp; for(int ai : arr){ mp[ai]++; mx = max(mx,ai); } for(int i=0; i<=mx; ++i){ if(!mp.count(i)) continue; for(int j=i; j<=mx; ++j){ if(!mp.count(j)) continue; // cout<<i<<':'<<mp[i]<<','<<j<<':'<<mp[j]<<'\n'; if(__builtin_popcountll(i&j)==1){ if(i==j) ans+=((long(mp[i])*(mp[i]-1))/2); else ans+= (long(mp[i])*mp[j]); } } } return ans; }
