位运算的一些技巧

判断一个数是不是2的整数次幂

对于2的整数次幂，2进制的形式的一个特点是只有一个1。我第一次遇到这个问题是在一个公司的笔试上，当时我也想到了这一点，然后我想到的方法是利用位运算，统计1的个数。然而，后来百度之后才发现，有一个更简单的方法，具体代码如下。

bool isPowerOfTwo(int n){
    return ( n & (n - 1) ) == 0;
}

在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数

给一个数组arr，其中只有一个数出现了奇数次，其它数出现了偶数次，打印这个数。

这个题算是比较经典的了，主要是利用异或运算的两个性质，a ^ a=0，0 ^ a=a。所以这里只要把所有的元素都异或一次，就可以得到最后的结果。

int numTimesOne(vector<int> &arr){
    int n = arr.size();
    int res = 0;
    for(int i=0;i<n;i++){
        res ^= arr[i];
    }
    return res;
}

求一个二进制数的最低位的1在哪里

给定一个数字arr，其中只有有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。

第一次遇到这个问题，是在字节跳动的二面，当时第一题出的是上面的题，我做出来了之后又问了这个问题，我没做出来，面试官后来说了算法，我写了实现。这个题其实还是比较好想，但我当时没想到这个点上。假设两个不同的数为a和b，这道题的算法是通过a和b一个不同的位，把数组分为两组，然后利用上一题的结论来做。我当时对掩码的求取也做的不好，没有想到下面这种求取方法。

vector<int> numTimesOne(vector<int> &arr){
    int n = arr.size();
    int ab = 0;
    for(int i=0;i<n;i++){
        ab ^= arr[i];
    }
    int mask = ab & (~ab + 1); //二进制数的最低位的1的位置
    int a = 0;
    for(int i=0;i<n;i++){
        if( (arr[i] & mask) != 0 ){
            a ^= arr[i];
        }
    }
    int b = ab ^ a;
    if(a > b){
        swap(a,b);
    }
    vector<int> res = {a,b};
    return res;
}

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

这里可以用异或来做，也是利用了异或的性质，代码如下。

void swap(int &a, int &b){
    a = a ^ b;
    b = a ^ b; // b = a^b^b = a
    a = a ^ b; // a = a^b^a = b
}

不用判断求两个数中比较大的数

int getMax(int a, int b) {
    int c = a - b;
    int d = c & (c >> 31); //a >= b 时,d = 0,否则等于a - b
    int res = a - d;
    return res;
}