位运算

亦或运算

  亦或运算本质是定义了一组操作，0^0 = 0, 1^1 = 0, 1^0 = 1, 0^1 = 1，描述为相同为0，不同为1。从定义来看，可以判断两个数是否相同，如果为0则相同，为1则不同。进一步，由于有结合律，可以消除一个序列中所有相同的数组，即a^b^c = (a^b)^c = a^(b^c)。在进一步思考，其实所有能够满足上述运算规律的情况都可以用亦或运算来实现，简单有效。比如无进位二进制加法，实际上与0+0 = 0, 1+1 = 0, 1+0 = 1, 0+1 = 1相同。奇偶性检验，如果我们把奇数看做1，偶数看做0，则有0+0 = 0, 1+1 = 0, 1 + 0 = 1, 0 + 1 = 1，和亦或操作一样。凡是有两个相反、相对的状态，都可以抽象为 0 和 1。另外对于奇偶性一般都会有简单的考察：奇数+奇数 = 偶数，以及奇数 - 1 = 偶数这两条基本性质。

​ 状态压缩题目中一般应用按位与、或和亦或运算会将状态之间的转换变得容易很多。包括如果想取得某一位的状态，可以用 i >> j & 1来计算。

与运算

与运算的简单性质：

1. 按位与之后，当前位有一个0则以后一直是0。
2. 基于上述运算，可以得知与运算有连续运算单调性质，每次与运算的结果不大于原先两个数。

与运算的应用：

LC.201 数字范围按位与（中等）

//找到前缀，因为连续，所以后边一定都是0
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n)
        {
            m >>= 1;
            n >>= 1;
            ++ shift;
        }

        return m << shift;
    }
};

//Brian Kernighan 算法，就是除去最后一位1的算法，n & (n - 1);
//和lowbit操作可以对比来看
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) n = n & (n - 1);

        return n;
    }
};