本文是在看了很多leetcode大神的题解之后整理的一个笔记，分享出来供大家参考。其中很多图来自这些大佬的原创，如果有冒犯到作者，请作者联系我。

&运算

可以用来求模

如

a&1 <=> a%2

巧用n&(n-1)运算

**(n-1)解析：**二进制数字最右边的1变成0，此1右边的0都变成1

**n&(n-1)解析：**二进制数字n最右边的1变成0，其余不变

剑指offer 15. 二进制1的个数

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res

巧用n&(-n)运算

其中 -n是 n 的相反数，是一个负数。该位运算技巧可以直接获取 n 二进制表示的最低位的 1。

由于负数是按照补码规则在计算机中存储的，−n 的二进制表示为 n的二进制表示的每一位取反再加上 1，因此它的原理如下：

leetcode 231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

function isPowerOfTwo(n){
    return n>0&&(n&(-n))===n
}

思考：如果题目是判断是否为4的幂，你会怎么做？

^运算

异或运算经常用在找不同的算法中，下面看个例子：

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 *t* 由字符串 *s* 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

关于异或运算的规律：

a^a=0; 任何数字和自己异或都是0
a^0=a; 任何数字和0异或还是他自己
a^ba=a^ab 异或运算具有交换律

根据上述规律我们可以写出如下代码解决该问题：

char findTheDifference(string s, string t) { 
        
        string r = s+r;
		char res = 0;
        for (char ch:r){
            res = res^r;
        }
        
        return res;
    }

此外，亦或运算也经常用在数组中出现次数的问题中，这种数组通常是排序好的，下面看个例子：

LeetCode 268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

int missingNumber(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for(int i=0;i<=n;i++){
            res ^=i;
        }
        for(int n:nums){
            res ^= n;
        }
        return res;

    }

此外，厦门大学2020考研数据结构903B的算法第一道题也可以用位运算：

题目大致是给一个数组，然后里面有很多数字，其中只有一个数字只出现一次，其他数字都出现偶数次，求这个出现一次的数字。

这题如果知道亦或运算，一个for循环直接秒杀。

左移(<<)、右移(>>)运算

<<相当于*2；>>相当于/2。这个技巧经常用在求高精度幂的题目上，如求2的100000方。

另外在二进制的题目中移位运算也经常用到，举个例子

剑指offer 15. 二进制中1的个数

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

int hammingWeight(uint32_t n) {
        int res=0;
        for(int i=0;i<32;i++){	
            if(n&1)					
                ++res;
            n>>=1;
        }
        return res;
    }

其思路就是每次把二进制最后一位跟1作位&算数，比较位一位就向右移一位（其实等价于/2)

位运算做加法

设两数字二进制形式a,b,其求和s=a+b,a(i)代表二进制第i位，则分以下四种情况：

观察发现，无进位和与**^运算规律相同，进位和与&**运算规律相同(并需左移一位)。由此可得：

二进制加法公式：

1）分析上面对二进制的计算过程，不难发现：
1.计算不进位的和，相当于对两个数进制异或：1101^1001=0100；
2.计算进位，第1位相当于对两个数求与：1101&1001=1001，然后再对其进行左移1位：1001<<1=10010。
然后再重复以上两个步骤。这里再异或一次就得到结果了，没进位：0100^10010=10110=22。

2）计算a+b，等价于(a^b)+((a&b)<<1)。
由于公式中又出现了+号，因此要再使用^运算直至没有进位。

代码：

class Solution {
public:
    int add(int a, int b) {
        // ^表示不进位的加法，&并且<<1表示进位的加法
        while(b){
            int plus = a^b;
            b = (unsigned int)(a&b)<<1;	//c++中负数不能直接移位
            a = plus;
        }
        return a;

    }
};