数据结构与算法：位运算专题

红太狼 2023-10-06 22:01 30阅读 0赞

## 数据结构与算法：位运算专题 ##

#### 文章目录 ####

*  数据结构与算法：位运算专题
 *   *   *  位运算基础
         *  位运算例题
         *   *  例题1：PIPI的位运算问题Ⅳ
             *   *  问题
                 *  解题思路
                 *  代码
             *  例题2：PIPI的位运算问题Ⅲ
             *   *  问题
                 *  解题思路
                 *  代码

#### 位运算基础 ####

位运算指的是直接对二进制位进行的一系列操作。常用的位运算有以下几种：

*  AND(按位与)：运算符为&，作用是把两个数字对应的二进制位相与，只有对应的两个位为1，结果位才为1，否则结果位为0。比如：13&12=1101&1100=1100=12。
 *  OR(按位或)：运算符为|，作用是把两个数字对应的二进制位相或，只有对应的两个位为0，结果位才为0，否则结果位为1。比如：9|10=1001|1010=1011=11。
 *  XOR(按位异或)：运算符为 ^ ，作用是把两个数字对应的二进制位相异或，如果对应的两个位不同，结果位为1；如果对应的两个位相同，结果位为0。比如：13 ^ 12=1101 ^ 1100=0001=1。
 *  移位运算：  
      a. 左移运算：运算符为<<，作用是在二进制表示下把数字同时向左移， 低位以0填充， 高位越界后舍弃。比如2<<1=…00010<<1=…00100=4。  
      b. 右移运算：运算符为>>，作用是在二进制表示下把数字同时向右移，高位以0填充，低位越界后舍弃。比如2>>1=…00010>>1=…00001=1。

利用以上几种位运算操作，可以实现这些常用功能：

*  `if((1<<i)&x)`，判断x二进制上的第i位是否为1。
 *  `x^(1<<i)`，将x二进制上的第i位取反。
 *  `x|(1<<i)` ，将x二进制上的第i位赋值为1。
 *  `x>>1`，等价于x/2，效率上比使用除法运算符更快。
 *  `if(x&1)`，判断奇偶，当x为奇数，其二进制上的最低位为1；当x为偶数，其二进制上的最低位为0。
 *  状态压缩，以一个二进制数表示一个状态集合。比如我们进行二进制枚举：for(i=0;i<(1<<4);i++)，就是从0000~枚举到1111，那么i的第j位为0表示不取这个数字，i的第j位为1表示取这个数字。状态压缩常用于搜索/动态规划等题目。

#### 位运算例题 ####

##### 例题1：PIPI的位运算问题Ⅳ #####

###### 问题 ######

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

###### 解题思路 ######

对于大部分位运算的问题，我们需要掌握按位考虑的思想。什么是按位考虑呢？也就是不对数字整体考虑，而是把数字转换成二进制形式，从它的每一位来思考解题的方法。  
  例如对于此题，题目是要计算第i个数与前i - 1个数的异或之和，那么我们就需要把这些数字都看成二进制形式，第i个数与其前某个数相异或，当第i个数的第j位与另一个数的第j位不同时，ans就需要加上2 ^ (j - 1)。对于前i - 1个数，计算方式都一样，于是我们就要按位考虑，计算每一位对答案ans的贡献：`如果第i个数字的第j位为1，那么它对最终答案的贡献就是前i-1个数第j位为0的个数 * 2 ^ (j - 1)；如果第i个数字的第j位为0，那么它对最终答案的贡献就是前i-1个数第j位为1的个数 * 2 ^ (j - 1)`。  
  因此我们用i遍历的时候使用一个JthBitHasOne数组，JthBitHasOne\[j\]表示前i-1个数第j位为1的有JthBitHasOne\[j\]个，那么前i-1个数第j位为0的就有i-1-JthBitHasOne\[j\]个。一个不超过1e9的数字最多只要遍历到第29位，根据上面提到的按位考虑算贡献的方法，我们就可以把题面上O(n^2)的时间复杂度优化成O(n\*log(max(ai)))。

接下来通过样例（1,2,3）来理解这个按位考虑计算贡献的方法：  
  当i=1，前面没有数能与它异或，此时ans=0。  
  当i=2，a2的二进制形式为10。a2的第0位为0，根据异或的特性，相同为0，不相同为1，那么前i-1个数第0位为1的，都能对最终答案产生2 ^ 0的贡献。前i-1个数只有a1一个数第0位为1，因此对答案的贡献是1 x 2 ^ 0=1。则ans+=1，此时ans=1。  
  a2的第1位为1，根据异或的特性，相同为0，不相同为1，那么前i-1个数第1位为0的，都能对最终答案产生2 ^ 1的贡献。前i-1个数只有a1一个数第1位为0，因此对答案的贡献是1 x 2 ^ 1=2。则ans+=2，此时ans=3。  
  当i=3，a3的二进制形式为11。a3的第0位为1，根据异或的特性，相同为0，不相同为1，那么前i-1个数第0位为0的，都能对最终答案产生2 ^ 0的贡献。前i-1个数只有a2一个数第0位为0，因此对答案的贡献是1 x 2 ^ 0=1。则ans+=1，此时ans=4。  
  a3的第1位为1，根据异或的特性，相同为0，不相同为1，那么前i-1个数第1位为0的，都能对最终答案产生2 ^ 1的贡献。前i-1个数只有a1一个数第1位为0，因此对答案的贡献是1x2^1=2。则ans+=2，此时ans=6。因此最终答案就是6。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_15_color_FFFFFF_t_70_g_se_x_16]

###### 代码 ######

import java.util.*;
    
    public class Main {
        
        static int[] JthBitHasOne = new int[32];
        static long[] twoPower = new long[32];
        public static void main(String[] args) {
        
            long ans = 0;
            int n, i, j;
            long a;
            twoPower[0] = 1;
            for (i = 1; i < 32; i++) {
        
                twoPower[i] = twoPower[i - 1] * 2;
            }
            Arrays.fill(JthBitHasOne, 0);
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            for (i = 1; i <= n; i++) {
        
                a = scanner.nextLong();
                for (j = 0; j < 32; j++) {
        
                    if ((a & (1L << j)) != 0) {
        
                        ans += (i - 1 - JthBitHasOne[j]) * twoPower[j];
                        JthBitHasOne[j]++;
                    } else {
        
                        ans += JthBitHasOne[j] * twoPower[j];
                    }
                }
            }
            System.out.println(ans);
        }
    }

需要注意的点有：

*  如何判断第i个数第j位是1还是0？  
    `a & (1L << j)`即可，结果为1，则a的第j + 1位为1，否则为0

##### 例题2：PIPI的位运算问题Ⅲ #####

###### 问题 ######

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]

###### 解题思路 ######

与上题一样，我们按位考虑。解决该题的关键在于对或运算和异或运算的理解。n个数进行或运算，对于第i位，如果有一个数该位为1，根据或运算的性质，或的结果该位也为1，因此会对答案产生2 ^ i的贡献；n个数进行异或运算，对于第i位，如果有奇数个数字该位为1，根据异或运算的性质，异或的结果该位也为1，因此会对答案产生2 ^ i的贡献。n个数异或的情况，对于第i位，只有拥有奇数个1时，该位异或结果才为1，其他情况下该位异或结果都为0。  
  又因为题目要求最大值，所以我们不妨从高位往低位进行贪心。我们用变量i从高位遍历到低位，对于每个i，我们先对这n个数求出第i位为1的个数。若第i位为1的个数为0，则我们需要使用一次改变机会，使第i位为1的个数变为1个，这样异或和或的结果都为1，一共产生2 x 2 ^ i的贡献。若第i位为1的个数不为0，则1的个数要么是奇数要么是偶数，若是奇数，则异或和或的结果都为1，一共产生2 x 2 ^ i的贡献。若是偶数，则可以使用一次改变机会将其变为奇数。

###### 代码 ######

import java.util.*;
     
    public class Main {
        
        static int[] oneNum = new int[65];
        static long[] twoPower = new long[65];
        public static void main(String[] args) {
        
            twoPower[0] = 1;
            int i, n, j, maxj = 1;
            for (i = 1; i < 65; i++) {
        
                twoPower[i] = twoPower[i - 1] * 2;
            }
            Arrays.fill(oneNum, 0);
            long k, a, ans = 0;
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            k = scanner.nextLong();
            for (i = 0; i < n; i++) {
        
                a = scanner.nextLong();
                for (j = 0; j < 64; j++) {
        
                    if ((a & (1L << j)) != 0) {
        
                        oneNum[j + 1]++;
                        maxj = Math.max(j + 1, maxj);
                    }
                }
            }
            for (j = maxj; j >= 1; j--) {
        
                    if (oneNum[j] == 0) {
        
                        if (k > 0) {
        
                            k--;
                            ans += 2 * twoPower[j - 1];
                        }
                    }else if ((oneNum[j] & 1) == 0) {
        
                        if (k > 0) {
        
                            k--;
                            ans += 2 * twoPower[j - 1];
                        } else {
        
                            ans += twoPower[j - 1];
                        }
                    } else {
        
                        ans += 2 * twoPower[j - 1];
                    }
            }
            System.out.println(ans);
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8c5e7817c2ca474fa6636fc8d87efcb0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/d5006c300d3f4fb99dcbb9e661df9860.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_15_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/c30111231eb347b18a1db6760d88b90a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_15,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/ae2fc5366491461786495758e1507dfd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/ff57eb60a5304341a00f11839c127a12.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16