ZOJ 3870：異或運算統計滿足條件的數對

題目

給 n 個數，求有多少無序數對 (i,j) 使 a_i XOR a_j > max(a_i, a_j)。

性質分析

設 a < b。a XOR b > b ⇔ a 的最高位 1 在 b 中對應位為 0。因為若該位 b 為 1，則 XOR 後該位為 0，結果必 < b。所以條件等價於：a 的最高二進制位在 b 中為 0。
排序數組降序。遍歷每個數 b（作為較大者），統計有多少已處理數 a（較小者）的最高位在 b 中為 0。用位桶記錄每個位上為 0 的數的個數。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        vector a(n);
        for (int& x : a) scanf("%d", &x);
        sort(a.begin(), a.end(), greater());
        long long ans = 0;
        int cntZero[32] = {0}; // cntZero[k] = 已處理數中第 k 位為 0 的個數
        for (int x : a) {
            // 找 x 的最高位 h
            int h = 31 - __builtin_clz(x);
            ans += cntZero[h];
            // 更新 cntZero
            for (int k = 0; k < 32; k++)
                if ((x >> k & 1) == 0) cntZero[k]++;
        }
        printf("%lld\n", ans);
    }
    return 0;
}