算法专题五：位运算

1.位1的个数

题目链接：LCR 133. 位 1 的个数 - 力扣（LeetCode）

每次干掉最右边的1，统计count的个数并且每次都更新。

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int count =0;while(n!=0){n=n&(n-1);count++;}return count;}
}

2.比特位个数

题目链接：LCR 003. 比特位计数 - 力扣（LeetCode）

class Solution {public int[] countBits(int n) {int[] ret=new int[n+1];for(int i=1;i<=n;i++){ret[i]=ret[i & (i-1)]+1;}return ret;}
}

 3.汉明距离

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

求完之后，求出其中1的个数，不同数的个数，就是1的个数

class Solution {public int hammingDistance(int x, int y) {int p=x ^ y;int count=0;while(p!=0){p=p&(p-1);count++;}return count;}
}

4.只出现1次的数字

题目链接：136. 只出现一次的数字 - 力扣（LeetCode）

class Solution {public int singleNumber(int[] nums) {int x=0;for(int num:nums){x=x^num;}return x;}
}

5.只出现一次的数字Ⅲ

题目链接：260. 只出现一次的数字 III - 力扣（LeetCode）

class Solution {public int[] singleNumber(int[] nums) {int m=0;for(int num:nums){m=m^num;}int r=m & (-m);int x=0,y=0;for(int num:nums){if((num&r)==0){x=x^num;}else{y=y^num;}}return new int[]{x,y};}
}

 6.判断字符是否唯一

题目链接：面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

class Solution {public boolean isUnique(String astr) {int n=astr.length();int num=0;for(int i=0;i<n;i++){int x=astr.charAt(i)-'a';if(((num>>x)&1)==1){return false;}else{num|=(1<<x);}}return true;}
}

 

7.丢失的数字

题目链接：268. 丢失的数字 - 力扣（LeetCode）

class Solution {public int missingNumber(int[] nums) {int ret=0;for(int x:nums){ret=ret^x;}for(int i=0;i<nums.length+1;i++){ret=ret^i;}return ret;}
}

 

 8.两整数之和

题目链接：371. 两整数之和 - 力扣（LeetCode）

class Solution {public int getSum(int a, int b) {while(b!=0){int x=a^b;int y=(a&b)<<1;a=x;b=y;}return a;}
}

9.只出现一次的数字Ⅱ

题目链接：137. 只出现一次的数字 II - 力扣（LeetCode）

class Solution {public int singleNumber(int[] nums) {int ret=0;for(int i=0;i<32;i++){int sum=0;for(int x:nums){if(((x>>i) & 1)==1){sum++;}}sum%=3;if(sum==1){ret=ret|(1<<i);}}return ret;}
}

 

10.消失的两个数字

题目链接：面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

运用的原理是  " 丢失的数字 " + " 只出现一次的数字Ⅲ "

看这两道题，这个问题就会迎刃而解

class Solution {public int[] missingTwo(int[] nums) {int ret=0;for(int x:nums){ret^=x;}for(int i=1;i<=nums.length+2;i++){ret^=i;}int r=ret&(-ret);int a=0,b=0;for(int i=1;i<=nums.length+2;i++){if((i & r)==0){a=a^i;}else{b=b^i;}}for(int x:nums){if((x & r)==0){a=a^x;}else{b=b^x;}}return new int[]{a,b};}
}

希望能对大家有所帮助！！！！！