题目:
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ,对于所有 0 <= i < n - 1 ,满足 nums[i + 1] 大于 nums[i] ,并且数组 nums 中所有元素的按位 AND 运算结果为 x 。
返回 nums[n - 1] 可能的 最小 值。
示例 1:
输入:n = 3, x = 4
输出:6
解释:
数组 nums 可以是 [4,5,6] ,最后一个元素为 6 。
示例 2:
输入:n = 2, x = 7
输出:15
解释:
数组 nums 可以是 [7,15] ,最后一个元素为 15 。
提示:
1 <= n, x <= 108
思路:
目标是构造数组,数组中所有元素的 AND 结果是 x, 没有思路的主要原因是一下需要构造 n 个数字,这是没有直接抓手的
没有思路时就需要从已经条件发掘, AND 操作就是已知条件, 多个元素 AND, 只有该位上全是1,才能做到 结果位是 1, 那么要想 数组元素 AND 结果是 x, 那么 x 的bit位上为 1 的, x 的数组元素那位也是 1。
那么可以提供给我们变化的就是 x 的bit位为 0 的位,其中第一个最小的一定是那些位置全是 0, 然后逐步增长即可。
具体实现直接看代码吧,我真不知道怎么自然语言描述了
代码:
class Solution {
public:
    long long minEnd(int n, int x) {
        n--; // 先把 n 减一,这样下面讨论的 n 就是原来的 n-1
        long long ans = x;
        int i = 0, j = 0;
        while (n >> j) {
            // x 的第 i 个比特值是 0,即「空位」
            if ((ans >> i & 1) == 0) {
                // 空位填入 n 的第 j 个比特值
                ans |= (long long) (n >> j & 1) << i;
                j++;
            }
            i++;
        }
        return ans;
    }
};