小O的数位翻转

[题目链接](https://www.nowcoder.com/practice/80a2e1aa90a24841bb153d14f13aa24a)

思路

对数组中的每个数字，将其二进制表示翻转（去除前导零），如果翻转后的值严格大于原值，则计入答案。

二进制翻转

对于一个正整数 $x$ ，将其二进制从低位到高位逐位取出，依次拼到结果 $rev$ 的低位。具体做法：每次取 $x$ 的最低位追加到 $rev$ ，然后 $x$ 右移一位，直到 $x$ 为 0。这样自然去除了前导零。

例如 $11 = (1011)_2$ ，翻转后得 $(1101)_2 = 13 > 11$ ，计入答案。

$12 = (1100)_2$ ，翻转后得 $(0011)_2 = 3 < 12$ ，不计入。

判断条件

翻转后值严格大于原值，等价于二进制的最低位为 1（否则翻转后位数变少，不可能更大）且翻转后确实更大。直接比较即可，无需额外优化。

时间复杂度 $O(n \log V)$ ，其中 $V$ 为数值上界。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        scanf("%lld", &x);
        long long rev = 0, tmp = x;
        while (tmp > 0) {
            rev = (rev << 1) | (tmp & 1);
            tmp >>= 1;
        }
        if (rev > x) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            long rev = 0, tmp = x;
            while (tmp > 0) {
                rev = (rev << 1) | (tmp & 1);
                tmp >>= 1;
            }
            if (rev > x) ans++;
        }
        System.out.println(ans);
    }
}