奇技淫巧之位运算

奇技淫巧之位运算

Tans 1,273 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);
    }
}