不用额外变量交换两个整数的值
public void swap(int a,int b){
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
整数二进制表达式中有多少个 1
public int count(int num){
int res = 0;
while(num!=0){
num = num & (num-1);
res++;
}
return res;
}
其他数都出现偶数次的数组中找到出现奇数次的数
//只有一个数出现了奇数次
public int findOddTimesNum(int[] arr){
int helper = 0;
for(int i:arr){
helper ^= i;
}
return helper;
}
//有两个数出现了奇数次
public int[] find(int[] arr){
int helper = 0;
for(int i:arr){
helper ^= i;
}
int rightOne = helper&(~helper+1);//得到最右边的1，如n=01000010 -> 00000010
int hasOne = 0;
for(int i:arr){//这个循环的思想和之前的一致
if(i^arr!=0){
hasOne ^= i;
}
}
return new int[]{hasOne,hasOne^helper};
}
这里解释下原因。
首先，0 与 n 异或为 n，n 与 n 异或为 0 。并且，异或操作满足交换律，最终都可以写成 A ^ A ^ B ^ B ^ C 的形式，显然最后的结果就是只出现一次的 C 。
其他数都出现 k 次的数组中找到只出现一次的数
public int find(int[] arr,int k){
int[] helper = new int[32];
for(int i:arr){
setExclusiveOr(helper,i,k);
}
return getNumfromKSysNum(helper,k);
}
public void setExclusiveOr(int[] helper,int val,int k){
int[] curKSysNum = getKSysNumFromNum(val,k);
for(int i=0;i<curKSysNum.length;i++){
helper[i]=(helper[i]+curKSysNum)&k;
}
}
public int[] getKSysNumFromNum(int val,int k){
int idx = 0;
int[] res = new int[32];
while(val>0){
res[idx++]=val%k;
val=val/k;
}
return res;
}
public int getNumfromKSysNum(int[] helper,k){
int res = 0;
for(int i=helper.length-1;i>=0;i--){
res = res*k + helper[i];
}
return res;
}
这题的思路是 k 个 相同的 k 进制数无进位相加的结果为 0 ，举个例子，两个二进制的 1 相加，不考虑进位的话就是 0 。
突然发现国外 leetcode 上有篇讨论给出了很多常见位运算题目的解法，比较可惜的是没有分析。
这里贴一下链接：https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
