算法【位运算】

注意：本篇讲解的位运算是基于掌握二进制数及基本二进制数的加减乘除过程的基础上更细致地加深理解。（大致是学习过计算机组成原理中的机器数部分）

特别提醒：Python同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题。比如：

(n << shift_amount) & 0xFFFFFFFF

因为Python遇见溢出会自动扩展，比如将32为扩展到64位，所以上面的代码是手动将其限制在32位。

一、异或运算的骚操作

先来一个好玩的问题：

袋子里一共a个白球，b个黑球，每次从袋子里拿2个球，每个球每次被拿出机会均等。如果拿出的是2个白球、或者2个黑球，那么就往袋子里重新放入1个白球；如果拿出的是1个白球和1个黑球，那么就往袋子里重新放入1个黑球。那么最终袋子里一定会只剩1个球，请问最终的球是黑的概率是多少？用a和b来表达这个概率。

被镇住了吧？其实这题是一个陷阱。

答案：

黑球的数量如果是偶数，最终的球是黑的概率是0%

黑球的数量如果是奇数，最终的球是黑的概率是100%

完全和白球的数量无关。为啥？异或运算的性质了解之后，就了解了。

下面给出异或运算的性质

1. 异或运算是无进位相加
2. 异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终的结果都是一个

3. 0 ^ n = n，n ^ n = 0

4. 整体异或和如果是x，整体中某个部分的异或和如果是y，那么剩下部分的异或和是x ^ y

这些结论最重要的就是1性质，所有其他结论都可以由这个结论推论得到。其中4性质相关的题目最多，利用区间上异或和的性质。

在知道1性质后，再来看看之前的问题，将白球看为0，黑球看为1，拿球之后的放球就变成了异或运算，答案也就显而易见。

下面我们通过几个题目加深对异或运算的认识。（题目有测试链接会附测试链接，本文中只有简要描述，具体题目见链接。实现语言：c++）

题目一

简要描述：交换两个数

分析：这里肯定不是简单的设一个temp来交换两个数的值，而是用异或来实现。由4性质可知，若c = a ^ b，则a = c ^ b，b = c ^ a，将其中的c进一步替换，就可以得到代码。

#include <iostream>
using namespace std;
int main(void){
    int a, b;
    cin>>a>>b;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    cout<<a<<b<<endl;
    system("pause");
    return 0;
}

注意：如果是单纯的两数交换可以使用，但若是在数组中的两数交换，必须确保两数的下标不相同。

题目二

简要描述：不用任何判断语句和比较操作，返回两个数的最大值

测试链接：https://www.nowcoder.com/practice/d2707eaf98124f1e8f1d9c18ad487f76

分析：判断两数很容易可以想到作差，但是单纯通过差的正负来判断两数大小是有风险的，因为存在溢出可能，故在作差之后，通过一些条件判断决定大小。代码如下所示。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 获取最大值
     * @param a int整型
     * @param b int整型
     * @return int整型
     */
    // 得到num的正负 正为0 负为1
    int sign(int num) {
        return num >> 31 == 0 ? 0 : 1;
    }
    int getMax(int a, int b) {
        // write code here
        int c = a - b;
        // 得到a b c的符号
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);
        // 判断a b是否同号 同号为0 异号为1
        int diff_ab = sa ^ sb;
        // 判断a b是否同号 同号为1 异号为0
        int same_ab = diff_ab ^ 1;
        int returnA = (diff_ab * sa + same_ab * sc) ^ 1;
        int returnB = returnA ^ 1;
        return a * returnA + b * returnB;
    }
};

其中，sign函数得到num的正负，由于c++不像java有无符号右移操作符，故对于负数右移31位会得到-1，对此，sign函数手动修改，这里的判断不在题目限制范围内。在得到a，b，c的正负后，对于返回a容易想到3中情况：1.a，b同号都为正，c为正。2.a，b同号都为负，c为正。3.a，b异号且a为正，c为正。对于这三种情况分别考虑sa，sc，diff_ab，same_ab，可得returnA的表达式且returnA为0时返回a，又由于return后表达式的格式，需要returnA为1才会返回a，故再得到returnA后与1异或翻转returnA，得到returnA后，returnB即是returnA的相反值。

题目三

简要描述：找到缺失的数字

测试链接：https://leetcode.cn/problems/missing-number/

分析：再次利用4性质，将0-n的所有数异或得到x，再将数组中的所有数异或得到y，则x ^ y就是缺失的数字。代码如下。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int length = nums.size();
        int x = 0;
        int y = 0;
        for(int i = 0;i < length;++i){
            x ^= i;
            y ^= nums[i];
        }
        x ^= length;
        return x ^ y;
    }
};

题目四

简要描述：数组中1种数出现了奇数次，其他的数都出现了偶数次，返回出现了奇数次的数

测试链接：https://leetcode.cn/problems/single-number/

分析：出现偶数次的数的异或相当于自己与自己异或，结果为0，而奇数次可以看作是偶数次加一，故将数组中所有数异或得到的结果就是奇数次的数。代码如下。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0;i < nums.size();++i){
            res ^= nums[i];
        }
        return res;
    }
};

题目五

简要描述：数组中有2种数出现了奇数次，其他的数都出现了偶数次，返回这2种出现了奇数次的数

测试链接：https://leetcode.cn/problems/single-number-iii/

分析：假设出现奇数次的数是a和b，如果将数组中所有数异或得到的结果就是c = a ^ b，这时候可以提取出c最右侧的1，使用到Brian Kernighan算法。因为a和b是不一样的两个数，所以c必有1的存在，提取出1后，可以将数组中的数按提取1的位数上是否是1划分为2组数，每一组数的异或结果就是一个出现奇数次的数。代码如下。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int c = 0;
        vector<int> res;
        for(int i = 0;i < nums.size();++i){
            c ^= nums[i];
        }
        // Brian Kernighan算法 c和c按位取反加一(-c)的与结果就得到最右侧的1
        int bit = (c == -2147483648 ? (1 << 31) : (c & (-c)));
        int a = 0;
        for(int i = 0;i < nums.size();++i){
            if((nums[i] & bit) == 0){
                a ^= nums[i];
            }
        }
        res.push_back(a);
        res.push_back(a ^ c);
        return res;
    }
};

其中，在提取最右侧的1时，要进行一个判断，因为整数最小值按位取反加一会溢出报错。

题目六

简要描述：数组中只有1种数出现次数少于m次，其他数都出现了m次，返回出现次数小于m次的那种数

测试链接：https://leetcode.cn/problems/single-number-ii/

分析：每一个数在不同位上有1，将所有数32位上的1加起来，统计哪一位上的1的个数模m不是0，则所有这种位组合起来就是结果。代码如下。

class Solution {
public:
    int m = 3;
    int bits[32] = {0};
    int singleNumber(vector<int>& nums) {
        for(int i = 0;i < nums.size();++i){
            for(int j = 0;j < 32;++j){
                if((nums[i] & (1 << j)) != 0){
                    bits[j] += 1;
                }
            }
        }
        int res = 0;
        for(int i = 0;i < 32;++i){
            if(bits[i] % m != 0){
                res |= (1 << i);
            }
        }
        return res;
    }
};

其中，bits数组统计32位上1的个数，nums[i] & (1 << j)是拿出nums[i]上第j位的数。上面代码比测试题目更通用，可以指定m的值。

二、位运算的骚操作

位运算有很多奇技淫巧，位运算的速度非常快，仅次于赋值操作，常数时间极好。下面通过几个题目展示一下。

题目一

简要描述：判断一个整数是不是2的幂

测试链接：https://leetcode.cn/problems/power-of-two/

分析：首先这个数要大于0，然后只需提取出最右侧的1，看原数是否和提取出1相等即可。代码如下。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && n == (n & (-n));
    }
};

题目二

简要描述：判断一个整数是不是3的幂

测试链接：https://leetcode.cn/problems/power-of-three/

分析：如果一个数字是3的某次幂，那么这个数一定只含有3这个质数因子。1162261467是int型范围内，最大的3的幂，它是3的19次方。这个1162261467只含有3这个质数因子，如果n也是只含有3这个质数因子，那么，1162261467 % n == 0；反之如果1162261467 % n != 0 说明n一定含有其他因子。代码如下。

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

题目三

简要描述：返回大于等于n的最小的2的幂

分析：如果n小于等于0，则结果为1。如果n大于0，将n减一，然后把减一后的n的最左侧的1右边的所有位全部变为1之后加一，即得到大于等于n的最小的2的幂。代码如下。

#include <iostream>
using namespace std;
int main(void){
    int n = 120;
    if(n <= 0){
        cout<<1<<endl;
    }else{
        n--;
        // 因为int只有32位 故只需左移到16位
        n |= (n >> 1);
        n |= (n >> 2);
        n |= (n >> 4);
        n |= (n >> 8);
        n |= (n >> 16);
        n++;
        cout<<n<<endl;
    }
    system("pause");
    return 0;
}

题目四

简要描述：区间[left, right]内所有数字 & 的结果

测试链接：https://leetcode.cn/problems/bitwise-and-of-numbers-range/

分析：如果将区间的数一个一个与起来，肯定是不够快更不够好的。如果说right大于left，则right最右侧的1是保不住的，因为存在right-1这个数和right与的结果，代表着最右侧的1变为0。然后更新right的值，直到right小于等于left。代码如下。

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while (left < right)
        {
            right -= (right & (-right));
        }
        return right;
    }
};

其中，虽然也是在遍历但是，right的变化是跳跃的，不是将left到right全部遍历一次，所以时间复杂度更好。

题目五

简要描述：反转一个二进制的状态，不是0变1、1变0，是逆序

测试链接：https://leetcode.cn/problems/reverse-bits/

分析：很容易想到通过一个数组实现逆序，但是不够快。可以想到以1位为一组和相邻组交换，以2位为一组和相邻组交换，以4位为一组和相邻组交换，直到以16位为一组和相邻组交换。交换可以分两步进行，先提取出前一组的数，然后右移一组的位数，接着提取出后一组的数，然后左移一组的位数，将这两个结果或起来，就得到一次交换。代码如下。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = ((n & (0xaaaaaaaa)) >> 1) | ((n & (0x55555555)) << 1);
        n = ((n & (0xcccccccc)) >> 2) | ((n & (0x33333333)) << 2);
        n = ((n & (0xf0f0f0f0)) >> 4) | ((n & (0x0f0f0f0f)) << 4);
        n = ((n & (0xff00ff00)) >> 8) | ((n & (0x00ff00ff)) << 8);
        n = ((n & (0xffff0000)) >> 16) | ((n & (0x0000ffff)) << 16);
        return n;
    }
};

题目六

简要描述：返回一个数二进制中有几个1

测试链接：https://leetcode.cn/problems/hamming-distance/

分析：题目就是求x和y异或的值中1的个数。很容易想到使用数组实现，但不够快。可以按如下思路，从以1位为一组，一组的值就是这一组中1的个数，相邻组合并1的个数。从以1位为一组开始，提取出后一组的值，再提取出前一组的值并将其右移一组的位数，将这两个结果相加，即得到这两个组一共1的个数的值。代码如下。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int num = x ^ y;
        num = (num & (0x55555555)) + ((num & (0xaaaaaaaa)) >> 1);
        num = (num & (0x33333333)) + ((num & (0xcccccccc)) >> 2);
        num = (num & (0x0f0f0f0f)) + ((num & (0xf0f0f0f0)) >> 4);
        num = (num & (0x00ff00ff)) + ((num & (0xff00ff00)) >> 8);
        num = (num & (0x0000ffff)) + ((num & (0xffff0000)) >> 16);
        return num;
    }
};

除此之外，还有通过位运算实现加减乘除，这部分只需要按照计组中补码的加减乘除步骤写代码即可，下面给出测试链接和代码，不做分析。

测试链接：https://leetcode.cn/problems/divide-two-integers/

代码如下（java）。

class Solution {
    public static int MIN = Integer.MIN_VALUE;
 
    public static int divide(int a, int b) {
        if (a == MIN && b == MIN) {
            // a和b都是整数最小
            return 1;
        }
        if (a != MIN && b != MIN) {
            // a和b都不是整数最小，那么正常去除
            return div(a, b);
        }
        if (b == MIN) {
            // a不是整数最小，b是整数最小
            return 0;
        }
        // a是整数最小，b是-1，返回整数最大，因为题目里明确这么说了
        if (b == neg(1)) {
            return Integer.MAX_VALUE;
        }
        // a是整数最小，b不是整数最小，b也不是-1
        a = add(a, b > 0 ? b : neg(b));
        int ans = div(a, b);
        int offset = b > 0 ? neg(1) : 1;
        return add(ans, offset);
    }
 
    // 必须保证a和b都不是整数最小值，返回a除以b的结果
    public static int div(int a, int b) {
        int x = a < 0 ? neg(a) : a;
        int y = b < 0 ? neg(b) : b;
        int ans = 0;
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((x >> i) >= y) {
                ans |= (1 << i);
                x = minus(x, y << i);
            }
        }
        return a < 0 ^ b < 0 ? neg(ans) : ans;
    }
 
    public static int add(int a, int b) {
        int ans = a;
        while (b != 0) {
            // ans : a和b无进位相加的结果
            ans = a ^ b;
            // b : a和b相加时的进位信息
            b = (a & b) << 1;
            a = ans;
        }
        return ans;
    }
 
    public static int minus(int a, int b) {
        return add(a, neg(b));
    }
 
    public static int neg(int n) {
        return add(~n, 1);
    }
 
    public static int multiply(int a, int b) {
        int ans = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                // 考察b当前最右的状态！
                ans = add(ans, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return ans;
    }
 
}