关于位运算的巧妙性：小乖，你真的明白吗？

灰太狼 2024-03-26 00:26 67阅读 0赞

一.位运算的概念

什么是位运算？

> 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

位运算就是直接操作二进制数，那么有哪些种类的位运算呢？

常见的运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>是带符号右移 >>>无符号右移动)。下面来细看看每一种位运算的规则。

1.  **&操作符：运算规则：将两个数字的二进制位进行按位与操作，即当两个数字的某位二进制数中同时为1结果才为1，否则是0** 0&0=0, 0&1=0, 1&1=1

例子：

![5c1d7f88396e20fc686b4607874a075f.png][]

1.  **位运算 | (或)**

规则：二进制对应位两两进行逻辑或运算(对应位中有一 个为1则为1) 即0|0=0,0|1=1,1|1=1

![8446dc12245057d388d5d8f81dca134c.png][]

3.**位运算 ^ (异或)**

规则：二进制对应位两两进行逻辑XOR (异或) 的运算(当对应位的值不同时为 1, 否则为 0)即0^0=0, 0^1=1, 1^1=0

![e7a5ebd9f50bb26a34fb6bbb68a709b1.png][]

**按位取反~**

规则：二进制的0变成1，1变成0。

左移运算<<：左移后右边位补 0

右移运算>>：右移后左边位补**原最左位值(可能是0，可能是1)**

右移运算>>>：右移后左边位补 0

关于位运算的规则，我们再进行详细的讲述：关于左移，无论对于正数还是负数，结果都是在原来数值的基础上进行乘2操作，但是对于右移符号，这其中就有说法了：>>>,对于无符号右移：它的运算规则是将原有数字右移，在左边补0，也就是说，如果原有的数字是负数，通过无符号右移会变成正数，对于正数则是简单的除2的效果，对于>>右移符号，则是无论对于正数还是负数，达到的效果都是除2

![5c3c824735b97d62af7d368033a3b28a.png][]

二.关于位运算的常见题目

1.  交换两个数

> 利用位运算将数个数值进行交换

a=a^b;//a=a^b
    b=a^b;//b=(a^b)^b=a^0=a
    a=a^b;//a=(a^b)^(a^b^b)=0^b=0

1.  判断奇偶数

> 给定一个数值，判断这个数字是奇数还是偶数

if(n & 1 == 1){
        // n 是个奇数。
    }

1.  不用加减乘除做加法

> 牛客链接： [https://www.nowcoder.com/practice/e7e0d226f1e84ba7ab8b28efc6e1aebc?tpId=8&&tqId=11065&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking][https_www.nowcoder.com_practice_e7e0d226f1e84ba7ab8b28efc6e1aebc_tpId_8_tqId_11065_rp_1_ru_activity_oj_qru_ta_cracking-the-coding-interview_question-ranking]

实现思路：关于实现加法运算而不使用加减乘除运算，我们则可以选择调用相关的位运算进行求解

①按位异或（^）:可以实现无进位的加法运算

比如： 1 ^ 1 = 0 ---> 1 + 1 = 0 (当前位值为0，进一位)

1 ^ 0 = 1 ---> 1 + 0 = 1 (当前位值为1)

0 ^ 0 = 0 ---> 0 + 0 = 0 (当前位值为0

②按位与（&）然后左移一位：能够表示进位情况：

比如： 1 & 1 = 1 ---> 1 + 1 = 0 (当前位的值进一位)

1 & 0 = 0 ---> 1 + 0 = 1 (当前位的值不进位)

0 & 0 = 0 ---> 0 + 0 = 0 (当前位的值不进位)

③

两个数相加：对应二进制位相加的结果 + 进位的结果

比如：3 + 2 --> 0011 + 0010 --> 0011 ^ 0010 + ((0011 & 0010) << 1)

\---> (0011 ^ 0010) ^ ((0011 & 0010) << 1)， 当进位之后的结果为0时，相加结束

public int addAB(int A, int B) {
    // write code here
    if(B==0){
    return A;
    }
    int sum=0;
    int carray=0;
    while(B!=0){
    sum=A^B;
    carray=(A&B)<<1;
    A=sum;
    B=carray;
    }
    return A;
    }

1.  求出现一次的数字①

> 给定一个非空整数数组，除了某个元素只出现一次以外， **其余每个元素均出现两次**。找出那个只出现了一次的元素。  
> 说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

实现思路：

根据异或运算的特性，我们能够理解的是：任何数字异或自身，结果都是0，所以对于所有成对出现的数字而言，我们将其全部异或一遍，其结果是0，再将唯一出现的数字再次异或，最后的结果也就是那个唯一出现的数字。

我们给出code：

class Solution {
        public int singleNumber(int[] nums) {
            int value=0;
            for(int i=0;i<nums.length;i++)
            {
                value^=nums[i];
            }
            return value;
        }
    }

1.  求出现一次的数字②

> 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

LeetCode链接：[https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/][https_leetcode.cn_problems_shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof_solution_jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom]

与①有所不同的是，这次题目的给出的条件是有两个不同的数字，让我们分别找出这两个数字，既然仍然是出现多组出现两次的数字，那么我们的实现大思路仍然保持不变，就是通过不断异或来排除出现两次的数字，那么这时候便引出了问题的关键，**异或之后剩下的结果是两个数字异或之后的结果，那么我们如何在结果中将这两个数字分别拿出来呢？**这里我们选择的策略是区分两个数字中不同的一位，具体实现思路如下：**首先将所有数字进行异或，将最后生成的结果与m(m=1)进行异或，目的是找出异或结果中为1的一位（因为两个不同的数字必然有一位不同，异或结果是1），我们利用这个辨识特点，分别对数组进行分组异或，最后的两个数字就是异或的结果**，具体code如下：

class Solution {
        public int[] singleNumbers(int[] nums) {
            //因为相同的数字异或为0，任何数字与0异或结果是其本身。
            //所以遍历异或整个数组最后得到的结果就是两个只出现一次的数字异或的结果：即 z = x ^ y
            int z = 0;  
            for(int i : nums) z ^= i;
            //我们根据异或的性质可以知道：z中至少有一位是1，否则x与y就是相等的。
            //我们通过一个辅助变量m来保存z中哪一位为1.（可能有多个位都为1，我们找到最低位的1即可）。
            //举个例子：z = 10 ^ 2 = 1010 ^ 0010 = 1000,第四位为1.
            //我们将m初始化为1，如果（z & m）的结果等于0说明z的最低为是0
            //我们每次将m左移一位然后跟z做与操作，直到结果不为0.
            //此时m应该等于1000，同z一样，第四位为1.
            int m = 1;
            while((z & m) == 0) m <<= 1;
            //我们遍历数组，将每个数跟m进行与操作，结果为0的作为一组，结果不为0的作为一组
            //例如对于数组：[1,2,10,4,1,4,3,3]，我们把每个数字跟1000做与操作，可以分为下面两组：
            //nums1存放结果为0的: [1, 2, 4, 1, 4, 3, 3]
            //nums2存放结果不为0的: [10] (碰巧nums2中只有一个10，如果原数组中的数字再大一些就不会这样了)
            //此时我们发现问题已经退化为数组中有一个数字只出现了一次
            //分别对nums1和nums2遍历异或就能得到我们预期的x和y
            int x = 0, y = 0;
            for(int i : nums) {
                //这里我们是通过if...else将nums分为了两组，一边遍历一遍异或。
                //跟我们创建俩数组nums1和nums2原理是一样的。
                if((i & m) == 0) x ^= i;
                else y ^= i;
            }
            return new int[]{x, y};
        }
    }

实现思路：

6.求出现一次的数字③

> 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。  
>

LeetCode链接：[https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/][https_leetcode.cn_problems_shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof]

实现思路：相对于出现两次的数字，能够利用异或的规律解决问题，出现三次的数字显得毫无规律可言，那么我们又该如何解决出现三次的数字问题呢？我们可以观察其每一位数字的规律：对于每一位数字而言，既然是出现三次，那么则可以对数组中的每一位数字的32个二进制位进行遍历，记录每一位的结果，至于最后返回的数字，我们可以通过res(res=0)和数组中的每一位进行%3然后进行或操作，然后将res左移，让二进制中的每一位回到原来的位置即可，code如下：

class Solution {
        public int singleNumber(int[] nums) {
            int[] counts = new int[32];
            for(int num : nums) {
                for(int j = 0; j < 32; j++) {
                    counts[j] += num & 1;
                    num >>>= 1;
                }
            }
            int res = 0, m = 3;
            for(int i = 0; i < 32; i++) {
                res <<= 1;
                res |= counts[31 - i] % m;
            }
            return res;
        }
    }

7.n皇后问题的位运算优化

**notes：需要注意的是，利用位运算解决n皇后问题的暴力递归问题只是对效率问题进行常数级别的优化：**

limit:是位数限制,对于行列数为N的棋盘，limit的限制是：对于前N个二进制位数均为1，对于N行列的棋盘而言，前N个二进制位代表棋盘的每一行（第一个二进制位代表第一行，第二个代表第二行........）

①col:对于每次摆放个皇后，就将这个二进制位置变为1，表示这个二进制位不能摆放皇后了

②leftLim:左斜线限制，如果leftLim为1，代表对于当前行来说，这个位置不能摆放皇后了。

③RightLim:右斜线限制，如果RightLim为1，同样对于当前行来说，这个位置不能摆放皇后了。

④limit==col:代表col前N个二进制位都是1，表示N个皇后都已经摆放好了，游戏结束，退出递归

⑤limit&(~(col|leftLim|rightLim))：pos是在每一行中能选择的列

![0027a5c47eadba26287e04696ca009e5.png][]

⑥ mostRight=pos&(~pos+1)：取出最右边的一位

⑦ pos-=mostRight：将最右边的位置从可选择的位数中去除，使当前行不能放置皇后

⑧while(pos!=0) 循环当前行中能选择的位置

⑨res+= process2(limit,col|mostRight,(leftLim|mostRight)<<1, (rightLim|mostRight)>>>1)：循环下一层

code如下：

public static int process2(int limit,int col,int leftLim,int rightLim){
            //递归出口
        if(limit==col){
            return 1;
        }
        //计算能放的位置：
        int pos= limit&(~(col|leftLim|rightLim));
        int mostRight=0;
       int res=0;
        //检验是否能递归
        while(pos!=0){
            //找最右的位置
             mostRight=pos&(~pos+1);
     
            pos-=mostRight;
          res+=  process2(limit,col|mostRight,(leftLim|mostRight)<<1, (rightLim|mostRight)>>>1);
        }
        return res;

[5c1d7f88396e20fc686b4607874a075f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1f8514e60aa84b0593c66db148ab0d78.png
[8446dc12245057d388d5d8f81dca134c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/34d9de1eb6234a6bafe34201c5c16400.png
[e7a5ebd9f50bb26a34fb6bbb68a709b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e72fefbe12ad47489f7ce68a9ac7f128.png
[5c3c824735b97d62af7d368033a3b28a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3e7a37ffd3de40758e1a8a8b7413ebec.png
[https_www.nowcoder.com_practice_e7e0d226f1e84ba7ab8b28efc6e1aebc_tpId_8_tqId_11065_rp_1_ru_activity_oj_qru_ta_cracking-the-coding-interview_question-ranking]: https://www.nowcoder.com/practice/e7e0d226f1e84ba7ab8b28efc6e1aebc?tpId=8&&tqId=11065&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[https_leetcode.cn_problems_shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof_solution_jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom]: https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/
[https_leetcode.cn_problems_shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof]: https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
[0027a5c47eadba26287e04696ca009e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3d37d765264c4f2ca2adaa0bb6f91d20.png