题解 | 小O的数位翻转

#include <bits/stdc++.h>
using namespace std;
// 翻转定义的函数 f(x)
static inline long long flipBin(long long x) {
    // 去掉末尾的 0（反转后这些会变成前导 0 被删掉）
    int t = __builtin_ctzll(x);     // x >= 1 题目保证
    long long y = x >> t;
    // 完全反转 y 的二进制
    long long z = 0;
    while (y) {
        z = (z << 1) | (y & 1);
        y >>= 1;
    }
    return z;
}

int main() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        if (flipBin(x) > x) ++ans;
    }
    cout << ans << '\n';
    return 0;
}