pairs between 1 and x such that sum of digits of p < q code example

Example: 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;
}