位运算是直接对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）即可得到。交换两个数
void Swap(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
}
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 。可以证明答案存在并且是唯一的。 示例：
输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 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],本题到此结束。 代码：
class Solution {
public int[] decode(int[] encoded, int first) {
int length = encoded.length;
int[] result = new int[length+1];
result[0] = first;
for(int i = 1; i <= length; i++){
result[i] = result[i-1] ^ encoded[i-1];
}
return result;
}
}
1734. 解码异或后的排列
题目要求： 给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。 它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。 给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。 示例：
输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
思路：这道题就是通过encoded数组来求解原来的数组，我们发现本题和1720题目有点类似，不一样的是我们不知道第一个元素是多少，但是多了一个条件是所求序列是前n个元素序列，同时n是个奇数，所以本题的关键是找到perm[0].
Ok,那我们来分析一下，首先我们可以轻易求出前n个元素序列的异或结果，也就是：
Stotal=1⊕2⊕…⊕n = perm[0]⊕perm[1]⊕…⊕perm[n−1] （1）
接下来，total我们可以轻易算出来，我们要求的是perm[1]⊕…⊕perm[n−1]，这样我们才可以逆推出来perm[0]，还记得我们还有encode数组没有使用么?，开始找规律：
// 设 encoded数组长度为 6 有：
encoded[0] = perm[0] ^ perm[1]
encoded[1] = perm[1] ^ perm[2]
encoded[2] = perm[2] ^ perm[3]
encoded[3] = perm[3] ^ perm[4]
encoded[4] = perm[4] ^ perm[5]
encoded[5] = perm[5] ^ perm[6]
由此可以发现，下面等式子包含了除了第一个元素外的所有元素
encoded[1] = perm[1] ^ perm[2]
encoded[3] = perm[3] ^ perm[4]
encoded[5] = perm[5] ^ perm[6]
我们把‘⊕’看作是异或符号：
我们看出：perm[1]⊕…⊕perm[n−1] = encode[1] ⊕ encode[3] ⊕ encode[5] ⊕...⊕ encode[n-1]; （2）
所以，根据式（1）和式（2）我们就可以解来prem[0]了，然后运用 1720. 解码异或后的数组 题解就可以解决本题啦。 AC代码：
class Solution {
public int[] decode(int[] encoded) {
int length = encoded.length + 1;
int[] result = new int[length];
int total = 0;
for(int i = 1; i <= length; i++){
total ^= i;
}
int odd = 0;
for(int i = 1; i < length; i += 2){
odd ^= encoded[i];
}
result[0] = total ^ odd;
for(int i = 1; i < length; i++ ){
result[i] = encoded[i-1] ^ result[i-1];
}
return result;
}
}
1310. 子数组异或查询
题目要求： 有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。 对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。 并返回一个包含给定查询 queries 所有结果的数组。 示例：
输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[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代码：
class Solution {
public int[] xorQueries(int[] arr, int[][] queries) {
int length_q = queries.length;//query的长度
int[] result = new int[queries.length];
int length = arr.length;//arr的长度
int[] preadd = new int[length+1];
preadd[0]= 0;//[0,0)当然为0
for(int i = 1; i <= length; i++){
preadd[i] = arr[i-1] ^ preadd[i-1];
}
for(int i = 0; i < length_q; i++){
result[i] = preadd[queries[i][1] + 1] ^ preadd[queries[i][0]];
}
return result;
}
}
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,我们可以根据具体代码来讲解。代码：
class Trie{ //定义字典树结构，我们定义左节点为0，有节点为1
Trie left = null;
Trie right = null;
}
class Solution {
Trie root = new Trie();
static final int HIGH_BIT = 30;
public int findMaximumXOR(int[] nums) {
int length = nums.length;
int max = 0;
for(int i = 1 ; i < length; i++){
add(nums[i-1]);
max = Math.max(max, check(nums[i]));
}
return max;
}
//字典树添加节点函数
public void add(int numToAdd){
Trie cur = root;
//从最高位依次装入字典树
for(int i = HIGH_BIT; i >= 0; i--){
int bit = (numToAdd >> i) & 1;
if(bit == 0){
if(cur.left == null){
cur.left = new Trie();
}
cur = cur.left;
}else{
if(cur.right == null){
cur.right = new Trie();
}
cur = cur.right;
}
}
}
//求取num的最大异或结果
public int check(int num){
Trie cur = root;
int result = 0;
//从最高位进行比较，如果num的第i位为1，那么我们需要向左边查找第i位为0的数。
for(int i = HIGH_BIT; i >=0; i--){
int bit = (num >> i) & 1;
if(bit == 1){
//如果左子树为空，那么我们就只能继续寻找右子树了；
if(cur.left == null){
result = (result << 1);
cur = cur.right;
}else{
//如果左子树不为空，那么我们更新结果和现在节点，然后继续搜索子树。
result = (result << 1) + 1;
cur = cur.left;
}
}else{
if(cur.right == null){
result = result << 1;
cur = cur.left;
}else{
result = (result << 1) + 1;
cur = cur.right;
}
}
}
return result;
}
}
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)就解决了。
代码：
class Solution {
public int countTriplets(int[] arr) {
int length = arr.length;
int[] preAdd = new int[length + 1];
for(int i = 1; i <= length; i++){
preAdd[i] = preAdd[i-1] ^ arr[i-1];
}
int result = 0;
for(int i = 0; i < length-1; i++){
for(int j = i + 1; j < length; j++){
if((preAdd[j+1] ^ preAdd[i]) == 0){
result += (j-i);
}
}
}
return result;
}
}
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大；我们还是运用前缀和，相对于之前的题目，我们这个题目使用二维前缀和。[图片上传失败...(image-9161b6-1621384176330)]图中'⊕'表示按位异或，根据上图我们可以求得前缀和数组，然后求解。
AC代码
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int h = matrix.length;
int w = matrix[0].length;
//这里为了后面无需判断下标是否溢出，我们从preadd(1，1)表示matrix(0,0)的前缀和
int[][] preadd = new int[h+1][w+1];
preadd[1][1] = matrix[0][0];
List<Integer> results = new ArrayList<Integer>();
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
if(j < 2 || i < 2){
}
preadd[i][j] = preadd[i-1][j] ^ preadd[i][j-1] ^ preadd[i-1][j-1] ^matrix[i-1][j-1];
results.add(preadd[i][j]);
}
}
//进行排序
Collections.sort(results, new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
return results.get(k - 1);
}
}
