奇技淫巧之位运算

奇技淫巧之位运算

Tans 1,094 2022-03-21

位运算是直接对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);
    }
}
算法 ACM