位运算是直接对0、1两种状态，在程序当中，合理的位运算更能显著提高代码在机器上的执行效率；

1.位运算概览

符号 描述 运算规则
& 与 两者都为1 则为1
| 或 有
^ 异或 两个位相同为0 相异为1
~ 取反 0变1， 1变0
>> 右移位 各二进位全部右移若干位，无符号数前面补0 ， 对于有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）
<< 左移位 左移动若干位，高位丢弃，低位补0

2.各个运算符的奇技淫巧

1.与运算

  • 通常用来清零操作，很容易理解
  • 取一个数的指定位：比如取数 X=1010 1110 的低4位，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行按位与运算（X&Y=0000 1110）即可得到X的指定位。

  • 判断奇偶，一个数X，使其与 1做 &操作,那么结果为1就是奇数， 为0则为偶数；

    2.或运算

  • 置1操作，对指定位进行置1 操作

    3.异或运算

    性质（重要！！！）:

  • 交换律： X ^ Y = Y ^ X

  • 结合律：(a^b)^c == a^(b^c)
  • X ^ X = 0, X ^ 0 = X
  • 自反性： a^b^b=a^0=a

用途：

  • 翻转指定位：比如将数 X=1010 1110 的低4位进行翻转，只需要另找一个数Y，令Y的低4位为1，其余位为0，即Y=0000 1111，然后将X与Y进行异或运算（X^Y=1010 0001）即可得到。

  • 交换两个数

    1. void Swap(int &a, int &b){
    2.   if (a != b){
    3.       a ^= b;
    4.       b ^= a;
    5.       a ^= b;
    6.   }
    7. }

    3.相关例题

    1720. 解码异或后的数组

    题目要求：
    未知 整数数组 arr 由 n 个非负整数组成。
    经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。
    给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
    请解码返回原数组 arr 。可以证明答案存在并且是唯一的。
    示例：

    1. 输入：encoded = [1,2,3], first = 1
    2. 输出：[1,0,2,1]
    3. 解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

    解题思路: 这道题目我们使用了异或运算的性质，根据题意，我们知道：
    根据交换律：arr[i] XOR arr[i+1] = arr[i+1] XOR arr[i] = encode[i],
    左右同乘arr[i] : arr[i+1] XOR arr[i] XOR arr[i] = encode[i] XOR arr[i]
    根据结合律： arr[i+1] XOR 0 = arr[i+1] = encode[i] XOR arr[i]
    至此我们可以从arr[i]推导出arr[i+1],本题到此结束。
    代码：

    1. class Solution {
    2.   public int[] decode(int[] encoded, int first) {
    4.       int length = encoded.length;
    6.       int[] result = new int[length+1];
    7.       result[0] = first;
    8.       for(int i = 1; i <= length; i++){
    9.           result[i] = result[i-1] ^ encoded[i-1]; 
    10.       } 
    11.       return result;
    12.   }
    13. }

1734. 解码异或后的排列

题目要求：
给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。
它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。
给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。
示例：

  1. 输入：encoded = [3,1]
  2. 输出：[1,2,3]
  3. 解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]

思路：这道题就是通过encoded数组来求解原来的数组，我们发现本题和1720题目有点类似，不一样的是我们不知道第一个元素是多少，但是多了一个条件是所求序列是前n个元素序列，同时n是个奇数，所以本题的关键是找到perm[0].
Ok,那我们来分析一下，首先我们可以轻易求出前n个元素序列的异或结果，也就是：
total=1⊕2⊕…⊕n=perm[0]⊕perm[1]⊕…⊕perm[n−1]
接下来，我们要求的是perm[1]⊕…⊕perm[n−1]，这样我们才可以逆推出来perm[0]，还记得，我们还有encode数组，找规律：

  1. // 设 encoded数组长度为 6
  2. encoded[0] = perm[0] ^ perm[1]
  3. encoded[1] = perm[1] ^ perm[2]
  4. encoded[2] = perm[2] ^ perm[3]
  5. encoded[3] = perm[3] ^ perm[4]
  6. encoded[4] = perm[4] ^ perm[5]
  7. encoded[5] = perm[5] ^ perm[6]

由此可以发现，下面包含了除了第一个元素外的所有元素

  1. encoded[1] = perm[1] ^ perm[2]
  2. encoded[3] = perm[3] ^ perm[4]
  3. encoded[5] = perm[5] ^ perm[6]

perm[1]⊕…⊕perm[n−1] = encode[1] ⊕ encode[3] ⊕ encode[5] ⊕…⊕ encode[n-1];
所以，带入第一个式子就可以求出来prem[0]了，然后运用 1720. 解码异或后的数组 题解就可以解决啦。
AC代码：

  1. class Solution {
  2.     public int[] decode(int[] encoded) {
  3.         int length = encoded.length + 1;
  4.         int[] result = new int[length];
  5.         int total = 0;
  6.         for(int i = 1; i <= length; i++){
  7.             total ^= i;
  8.         }
  9.         int odd = 0;
  10.         for(int i = 1; i < length; i += 2){
  11.             odd ^= encoded[i];
  12.         }
  13.         result[0] = total ^ odd;
  14.         for(int i =  1; i < length; i++ ){
  15.             result[i]  = encoded[i-1] ^ result[i-1];
  16.         }
  17.         return result; 
  18.     }
  19. }

1310. 子数组异或查询

题目要求：
有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。
对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。
并返回一个包含给定查询 queries 所有结果的数组。
示例：

  1. 输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
  2. 输出：[2,7,14,8] 
  3. 解释：
  4. 数组中元素的二进制表示形式是：
  5. 1 = 0001 
  6. 3 = 0011 
  7. 4 = 0100 
  8. 8 = 1000 
  9. 查询的 XOR 值为：
  10. [0,1] = 1 xor 3 = 2 
  11. [1,2] = 3 xor 4 = 7 
  12. [0,3] = 1 xor 3 xor 4 xor 8 = 14 
  13. [3,3] = 8

思路：
这道题目就是给定一个数组，求任意区间内的异或结果，于是我们可以想到前缀和线段树，但是线段树码量太大，于是我们可以使用前缀和来求解。OK，我们定义preAdd数组来表示前缀和数组，那么有
preAdd[i]``= arr[0] xor arr[1] xor arr[2] xor .... xor arr[i-1];也就是arr数组的[0,i) (记住是左闭右开)所有元素的异或结果；
设我们所需要求的是query[i to j],也就是从i 到j 的所有元素的异或；
那么我们通过构造—->有 preAdd[i] xor query[i to j] = preAdd[j+1],
那么根据异或的交换律就有query[i to j] = preAdd[j+1] xor preAdd[i];
到此分析结束，我们只需要preAdd[i]和preAdd[j+1]异或就可以得到query[i to j]了。
AC代码：

  1. class Solution {
  2.     public int[] xorQueries(int[] arr, int[][] queries) {
  3.         int length_q = queries.length;//query的长度
  4.         int[] result = new int[queries.length];
  5.         int length = arr.length;//arr的长度
  6.         int[] preadd = new int[length+1];
  7.         preadd[0]= 0;//[0,0)当然为0
  8.         for(int i = 1; i <= length; i++){
  9.             preadd[i] = arr[i-1] ^ preadd[i-1];
  10.         }
  11.         for(int i = 0; i < length_q; i++){
  12.             result[i] = preadd[queries[i][1] + 1] ^ preadd[queries[i][0]];
  13.         }
  14.         return result;
  15.     }
  16. }

421. 数组中两个数的最大异或值

题目要求:

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

示例1： 输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例2： 输入：nums = [0]
输出：0

思路：本题是找到两个数字求异或来解得最大解，显而易见，我们可以暴力解法，时间复杂度为O(n^2)，显然可能超过时间限制，我们如何在O(n)时间复杂度来求解呢？
根据异或的性质我们可以得知，当相同位分别为0和1的时候，结果为1，例如有一个数5(0101)，那么我们如何找到一个数使其（只分析4位）最大呢，很显然我们可以找到(1010）和其进行异或，异或结果为(1111),这就是我们所需要取得最优结果，所以我们可以使用字典树。关于字典树可以参考我的另一篇文章《数据结构之字典树》,OK,我们可以根据具体代码来讲解。
代码：

  1. class Trie{        //定义字典树结构，我们定义左节点为0，有节点为1
  2.     Trie left = null;
  3.     Trie right = null;
  4. }
  5. class Solution {
  6.     Trie root = new Trie();
  7.     static final int HIGH_BIT = 30;
  8.     public int findMaximumXOR(int[] nums) {
  9.         int length = nums.length;
  10.         int max = 0;
  11.         for(int i = 1 ; i < length; i++){
  12.             add(nums[i-1]);
  13.             max = Math.max(max, check(nums[i]));
  14.         }
  15.         return max;
  17.     }
  18.     //字典树添加节点函数
  19.     public void add(int numToAdd){
  20.         Trie cur = root;
  21.         //从最高位依次装入字典树
  22.         for(int i = HIGH_BIT; i >= 0; i--){
  23.             int bit = (numToAdd >> i) & 1;
  24.             if(bit == 0){
  25.                 if(cur.left == null){ 
  26.                     cur.left = new Trie();
  27.                 }
  28.                 cur = cur.left;
  29.             }else{
  30.                 if(cur.right == null){
  31.                     cur.right = new Trie();
  32.                 }
  33.                 cur = cur.right;
  34.             }
  35.        }
  36.     }
  37.     //求取num的最大异或结果
  38.     public int check(int num){
  39.         Trie cur = root;
  40.         int result = 0;
  41.         //从最高位进行比较，如果num的第i位为1，那么我们需要向左边查找第i位为0的数。
  42.         for(int i = HIGH_BIT; i >=0; i--){
  43.             int bit = (num >> i) & 1;
  44.             if(bit == 1){
  45.                 //如果左子树为空，那么我们就只能继续寻找右子树了；
  46.                 if(cur.left == null){
  47.                     result = (result << 1);
  48.                     cur = cur.right;
  49.                 }else{
  50.                     //如果左子树不为空，那么我们更新结果和现在节点，然后继续搜索子树。
  51.                     result = (result << 1) + 1;
  52.                     cur = cur.left;
  53.                 }       
  54.             }else{
  55.                 if(cur.right == null){
  56.                     result = result << 1;
  57.                     cur = cur.left;
  58.                 }else{
  59.                     result = (result << 1) + 1;
  60.                     cur = cur.right;
  61.                 }
  62.             }
  63.         }
  64.         return result;
  65.     }
  66. }

1442. 形成两个异或相等数组的三元组数目

题目要求：

给你一个整数数组 arr 。 现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。 a 和 b 定义如下： a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1] b = arr[j] ^ arr[j + 1] ^ … ^ arr[k] 注意：^ 表示 按位异或 操作。 请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

示例： 输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)

思路
这道题我们如果不想重复计算需要使用前缀和数组，降低时间的复杂度。
三重循环解法：直接暴力循环求解，依次循环i，j，k；
二重循环解法：如果a==b,那么有a^b=0, 基于此，通过二重循环 i 和 j，计算(i,j)区间的异或和是否为0，如果为0，那么中间存在j-i个k，所以我们可以直接定义result += (j-i)就解决了。

代码：

  1. class Solution {
  2.     public int countTriplets(int[] arr) {
  3.         int length = arr.length;
  4.         int[] preAdd = new int[length + 1];
  5.         for(int i = 1; i <= length; i++){
  6.             preAdd[i] = preAdd[i-1] ^ arr[i-1];
  7.         }
  8.         int result = 0;
  9.         for(int i = 0; i < length-1; i++){
  10.             for(int j = i + 1; j < length; j++){
  11.                 if((preAdd[j+1] ^ preAdd[i]) == 0){
  12.                     result += (j-i);
  13.                 }
  14.             }
  15.         }
  16.         return result;
  17.     }
  18. }

1738. 找出第 K 大的异或坐标值

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。 请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

思路：这道题目的意思也就是找出一个二维矩阵中(0,0)和(m,n)的异或值的第k大，我们首先要找到每一个位置对应的异或的值，然后排序最后输出第K大；我们还是运用前缀和，相对于之前的题目，我们这个题目使用二维前缀和。
奇技淫巧之位运算 - 图1
图中’⊕’表示按位异或，根据上图我们可以求得前缀和数组，然后求解。

AC代码

  1. class Solution {
  2.     public int kthLargestValue(int[][] matrix, int k) {
  3.         int h = matrix.length;
  4.         int w = matrix[0].length;
  5.         //这里为了后面无需判断下标是否溢出，我们从preadd(1，1)表示matrix(0,0)的前缀和
  6.         int[][] preadd = new int[h+1][w+1];    
  7.         preadd[1][1] = matrix[0][0];    
  8.         List<Integer> results = new ArrayList<Integer>();
  9.         for(int i = 1; i <= h; i++){
  10.             for(int j = 1; j <= w; j++){
  11.                 if(j < 2 || i < 2){
  13.                 }
  14.                 preadd[i][j] = preadd[i-1][j] ^ preadd[i][j-1] ^ preadd[i-1][j-1] ^matrix[i-1][j-1];
  15.                 results.add(preadd[i][j]);
  16.             }
  17.         }
  18.         //进行排序
  19.         Collections.sort(results, new Comparator<Integer>() {
  20.             public int compare(Integer num1, Integer num2) {
  21.                 return num2 - num1;
  22.             }
  23.         });
  24.         return results.get(k - 1);
  25.     }
  26. }