题目解析
* 输入输出:输入一个整数 xxx (0≤x<20250 \le x < 20250≤x<2025)。输出最小的正整数 yyy,使得 (x \bitand y) + (x \bitor y) = 2025;若不存在则输出 −1-1−1。
* 数据范围:0≤x<20250 \le x < 20250≤x<2025。目标值 202520252025 的二进制位数约为 111111 位(210=1024,211=20482^{10}=1024, 2^{11}=2048210=1024,211=2048)。
* 复杂度要求:代码采用枚举策略,时间复杂度 O(2⌈log22025⌉)≈O(2025)O(2^{\lceil\log_2 2025\rceil}) \approx O(2025)O(2⌈log2 2025⌉)≈O(2025),可接受;也可利用数学性质优化至 O(1)O(1)O(1)。
* 算法知识点:位运算性质、枚举、数学推导
思路解析
1. 关键数学性质:对于任意两个整数 a,ba, ba,b,存在恒等式 (a \bitand b) + (a \bitor b) = a + b。该性质对二进制下的每一位均成立(0+0=0&0+0∣00+0=0\&0+0|00+0=0&0+0∣0, 1+0=1&0+1∣01+0=1\&0+1|01+0=1&0+1∣0, 1+1=1&1+1∣11+1=1\&1+1|11+1=1&1+1∣1),故对整体亦成立。
2. 方程化简:原条件 (x \bitand y) + (x \bitor y) = 2025 可转化为 x+y=2025x + y = 2025x+y=2025,即 y=2025−xy = 2025 - xy=2025−x。
3. 解的存在性:由数据范围 x<2025x < 2025x<2025 可知 y=2025−x∈[1,2025]y = 2025 - x \in [1, 2025]y=2025−x∈[1,2025],故正整数解必然存在且唯一。
4. 枚举策略(代码实现):代码选择直接枚举验证。计算 202520252025 的二进制位数 bit_length≈11\textit{bit\_length} \approx 11bit_length≈11,在 [0,211][0, 2^{11}][0,211](即 [0,2048][0, 2048][0,2048])范围内从小到大枚举 iii。由于 2025<20482025 < 20482025<2048,该范围必然包含正确答案。首个满足位运算等式的 iii 即为最小正整数 yyy。
5. 终止条件:若枚举结束未找到(理论上不会发生在此数据范围),输出 −1-1−1。
完整代码