力扣-位运算-1【算法学习day.41】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

tip:下面题目套路类似，就不分析了

1.使两个整数相等的位更改次数

题目链接:3226. 使两个整数相等的位更改次数 - 力扣（LeetCode）

题面:

代码:

class Solution {public int minChanges(int n, int k) {if(n==k)return 0;if(n<k)return -1;int ans = 0;while(n>0){if((n&1)==1&&(k&1)==0){ans++;}else if((n&1)==0&&(k&1)==1){return -1; }n>>=1;k>>=1;//  if(max>0&&min==0)return -1;}return ans;}
}

2.根据数字二进制下1的数目排序

题目链接:1356. 根据数字二进制下 1 的数目排序 - 力扣（LeetCode）

题面:

代码:

class Solution {public int[] sortByBits(int[] arr) {int n = arr.length;for(int i = 0;i<n-1;i++){for(int j = i+1;j<n;j++){if(getOneNumber(arr[i])>getOneNumber(arr[j])){swap(arr,i,j);}else if(getOneNumber(arr[i])==getOneNumber(arr[j])&&arr[i]>arr[j]){swap(arr,i,j);}}}  return arr;}public int getOneNumber(int n){int ans = 0;while(n>0){if((n&1)==1){ans++;}n>>=1;}return ans;}public void swap(int[] arr,int i,int j){int flag = arr[i];arr[i] = arr[j];arr[j] = flag;}
}

3.汉明距离

题目链接:461. 汉明距离 - 力扣（LeetCode）

题面:

代码:

class Solution {public int hammingDistance(int x, int y) {int ans = 0;while(x>0||y>0){if((x&1)!=(y&1)){ans++;}x>>=1;y>>=1;}return ans;}
}

4.转换数字的最少位翻转次数

题目链接:2220. 转换数字的最少位翻转次数 - 力扣（LeetCode）

题面:

代码:

class Solution {public int minBitFlips(int start, int goal) {int ans = 0;for(int i = start^goal;i>0;i-=lowbit(i))ans++;return ans;}public int lowbit(int n){return n&(-n);}
}

5.数字的补数

题目链接:476. 数字的补数 - 力扣（LeetCode）

题面:

代码:

class Solution {public int findComplement(int num) {int flag = 0;int flag2 = num;while(num>0){flag<<=1;flag+=1;num>>=1;}return flag^flag2;}
}

6.十进制整数的反码

题目链接:1009. 十进制整数的反码 - 力扣（LeetCode）

题面:

代码:

class Solution {public int bitwiseComplement(int n) {if(n==0)return 1;int flag = n;int flag2 = 0;while(n>0){flag2<<=1;flag2+=1;n>>=1;}return flag^flag2;}
}

7.二进制间距

题目链接:868. 二进制间距 - 力扣（LeetCode）

题面:

代码:

class Solution {public int binaryGap(int n) {int max = 0;int[] arr = new int[40];int count = 0;for(int i = n;i>0;i-=lowbit(i)){int flag = lowbit(i);arr[count++] = (int)(Math.log(flag)/Math.log(2))+1;}for(int i = 1;i<count;i++){max = Math.max(max,arr[i]-arr[i-1]);}return max;}public int lowbit(int n){return n&(-n);}
}

8.生成不含相邻零的二进制字符串

题目链接:3211. 生成不含相邻零的二进制字符串 - 力扣（LeetCode）

题面:

代码:

class Solution {List<String> ans = new ArrayList<>();int n;public List<String> validStrings(int n) {this.n = n;recursion(1,"",0);return ans;}public void recursion(int t,String str,int flag){if(t==n+1){ans.add(str);return;}if(t==1||flag==1){recursion(t+1,str+"0",0);recursion(t+1,str+"1",1);}else if(flag==0){recursion(t+1,str+"1",1);}}
}

9.找出数组中的K-or值

题目链接:2917. 找出数组中的 K-or 值 - 力扣（LeetCode）

题面:

代码:

class Solution {public int findKOr(int[] nums, int k) {int n = nums.length;int ans = 0;for (int i = 0; i < 31; i++) {int sum = 0;for (int j = 0; j < n; j++) {sum+=(nums[j] & 1);nums[j] >>= 1;}  if(sum>=k){ans |= 1 << i;    }}return ans;}
}

10.交替位二进制数

题目链接:693. 交替位二进制数 - 力扣（LeetCode）

题面:

代码:

class Solution {public boolean hasAlternatingBits(int n) {int len = (int)(Math.log(n)/Math.log(2))+1;int flag = n&1;n>>=1;for(int i = 1;i<len;i++){int lin = n&1;if(lin==flag)return false;flag = lin;n>>=1;}return true;}
}

11.找到两个数组的前缀公共数组

题目链接:2657. 找到两个数组的前缀公共数组 - 力扣（LeetCode）

题面:

代码:

class Solution {public int[] findThePrefixCommonArray(int[] A, int[] B) {int n  = A.length;int[] ans = new int[n];long flaga = 0;long flagb = 0;for(int i = 0;i<n;i++){int a = A[i];int b = B[i];flaga|=(1L<<(a-1));flagb|=(1L<<(b-1));long lin = (flaga&flagb);ans[i] = Long.bitCount(lin);}return ans;}// public long lowbit(long n){//     return n&(-n);// }
}