位运算题目

不用额外变量交换两个整数的值

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