题目链接：3314. 构造最小位运算数组 I（简单）
3315. 构造最小位运算数组 II（简单）
算法原理：
解法一：暴力枚举
4ms击败30.43%
时间复杂度O(N∗M)
思路很简单，先来一层for循环遍历链表中的每个质数，再针对每个质数再来一层for循环，因为“|”运算的性质就是只要有1，结果就是1，所以 i | (i+1)的结果一定>=i+1，所以内层for循环从0遍历到x-1，逐步试探，只要有符合的，就加入到返回数组ret中，然后立刻break，防止多添，如果没有找到，就把－1加入返回数组即可
解法二：位运算
1ms击败100.00%
时间复杂度O(N)
想要降低时间复杂度就要观察题目的例子，总结出规律再对症下药
举个例子：x=100111时，x | (x+1)=100111 | 101000=101111
x和x+1必然是一奇一偶，那么上述的式子其实就是把二进制最右边的0改成了1，且这个 0右边都是1，在上述例子中0的位置在从左往右数第3个数
反过来，在 x | (x+1)=101111的情况下倒推x，需要把右边四个1的某个1变成0，
满足要求的x有：100111、101011、101101、101110，这些都是符合条件的，挑出其中最小的是 100111，也就是把101111最右边的0的右边的1置为0
那么我们现在的目标就是找到nums[i]最右边的0的右边的1，如何找到呢？
先找到最右边的0，然后>>1就是最右边的1了，如何找到最右边的0呢？
①第一个方向：
既然要找到这个0，那么就是提取出它，在位运算中，提取常常使用按位与&
把101111+1得到110000，再把101111按位取反~得到010000，这两个结果按位与&恰好得到lowbit=10000
②第二个方向：
找到这个0也可以用异或^提取，咱们要找的是最右侧的0，首先明确，找最右侧的1的式子是n&-n，那么我们可以通过对原数取反，将最右侧的1转化为最右侧的0，进而使用这个式子
这个式子可参考下面这篇博客👇
优选算法-位运算：33.判断字符是否唯一
把x=101111按位取反~得到 t=~x=010000，通过 t &-t 得到lowbit=10000
JAVA代码：
class Solution { //解法一：暴力解法 public int[] minBitwiseArray(List<Integer> nums) { int[] ret=new int[nums.size()]; int index=0; //遍历每个质数 for(int x:nums){ //获取一下加入之前的index位置 int tmp=index; for(int i=0;i<x;i++) if((i|(i+1))==x){ ret[index++]=i; break;//找到一个最小的立马弹出 } //如果没找到就添加－1 if(index==tmp) ret[index++]=-1; } return ret; } }class Solution { //解法二：位运算 public int[] minBitwiseArray(List<Integer> nums) { int[] ret=new int[nums.size()]; int index=0; for(int x:nums){ if(x==2) ret[index++]=-1; else{ //写法一 //int lowbit=(x+1)&~x; //写法二 int lowbit=(~x)&-(~x); ret[index++]=x^(lowbit>>1); } } return ret; } }
