-
发表于 2026.02.06
-
位运算的题目,数组
nums的元素为质数并没有太多特殊的含义,只是告诉你除了2之外,其他必然为奇数(也就是二进制表示法中,必定以1比特位结尾)。对于给出的条件ans[i] OR (ans[i] + 1),不难想到对于任意整数x,x OR (x + 1)的效果是将x从右往左数遇到的第一个二进制0变为1(比如,对于a = 111000011,那么a + 1 = 111000100,a OR a + 1即111000111,就是将最低位0反转成1)。因此,要让等式成立,意味nums[i]必然是将某个数的最低位0变1得到的,而这个数的最低位左侧的比特位和nums[i]是一致的。根据上述规律,
nums[i]的二进制形式一定是...011...1(最后以连续的1结尾)。要构造最小的ans[i],最优做法是找到nums[i]末尾这一串连续1中最高位置的那个1,并将其变为0。例如,如果nums[i]的二进制末尾是...0111,那么对应的最小ans[i]就是...0011。在代码实现上,可以通过位移操作定位到从右往左第一个0的位置,然后将该位右侧的1抹除即可。比如,对于
11100001111,那么其最优解是11100000111,其加1会变成11100001000(不断进位,直至遇到0),两者OR操作后会变成11100001111。还能有更小的解吗?没有了,毕竟前面的0不能改成1(比如11010001111)(OR的特点,有1的位,必然结果都会有1,必然凑不成原来的数字);将更前面的1改成0(比如11000001111),其加1后,也不能将前面改成的0翻转回去1,所以也凑不成原来的数字。class Solution { public: vector<int> minBitwiseArray(vector<int>& nums) { vector<int> ans(nums.size(), -1); for (int i = 0; i < nums.size(); ++i) { if (nums[i] == 2) continue; int mask = 1; // 从右到左寻找尾部连续1的最左位 -> 寻找第一个0bit while (mask & nums[i]) { mask <<= 1; } mask >>= 1; ans[i] = nums[i] - mask; // 将这个1抹为0即为解 } return ans; } }; - LC 题目链接
-