【面试锦囊】位运算介绍与经典例题总结

水深无声 2022-11-19 07:49 193阅读 0赞

> 原创公众号：[bigsai][]  
> 原创不易，如果有收获请不要吝啬你的**赞赞**！  
> 文章已收录在 [全网都在关注的数据结构与算法学习仓库][Link 1] 欢迎star

## 前言 ##

位运算隐藏在编程语言的角落中，其神秘而又强大，暗藏内力，有些人光听位运算的大名的心中忐忑，还有些人更是一看到位运算就远远离去，我之前也是。但狡猾的面试官往往喜欢搞偷袭，抓住我们的弱点搞我们，为了防患于未然，特记此篇！

本篇的内容为位运算的介绍和一些比较经典的位运算问题进行介绍分析，当然，位运算这么牛，后面肯定还是要归纳总结的。

## 认识位运算 ##

什么是位运算？

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

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

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

**位运算 & (与)**

规则：二进制对应位两两进行逻辑AND运算(只有对应位的值都是 1 时结果才为 1, 否则即为 0)即 `0&0=0`,`0&1=0`,`1&1=1`

例如：2 & -2

![image-20210103203435246][]

**位运算 | (或)**

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

例如：2 | -2

![image-20210103203852165][]

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

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

例如：2 ^ -2

![image-20210103204258194][]

**按位取反~**

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

![image-20210103204832085][]

**移位运算符**

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

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

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

*  对于左移运算符`<<`没有悬念右侧填个零无论正负数相当于整个数乘以2。
 *  而右移运算符就有分歧了，分别是左侧补0`>>>`和左侧补原始位`>>`，如果是正数没争议左侧都是补0，达到除以2的效果；如果是负数的话左侧补0`>>>`那么数值的正负会发生改变，会从一个负数变成一个相对较大的正数。而如果是左侧补原始位(负数补1)`>>`那么整个数还是负数，也就是相当于除以2的效果。

下面这张图可以很好的帮助你理解负数的移位运算符：

![image-20210111203911045][]

到这里，我想你应该对位运算有了初步的认识，在这里把上面提到的部分案例执行对比一下让你看一下可能会理解的更清晰：

![image-20210112233233639][]

## 位运算小技巧 ##

在这里有些常用的位运算小技巧。

### 判断奇偶数 ###

正常判断奇数偶数的时候我们会这样写：

if( n % 2 == 1)
        // n 是个奇数
    }

使用位运算可以这么写：

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

其核心就是判断二进制的**最后一位是否为1**，如果为1那么结果加上2^0=1一定是个奇数，否则就是个偶数。

### 交换两个数 ###

对于传统的交换两个数，我们需要使用一个变量来辅助完成操作，可能会是这样：

int team = a;
    a = b;
    b = team;

但是使用位运算可以不需要借助额外空间完成数值交换：

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=b

原理已经写在注释里面了，是不是感觉非常diao呢？

### 二进制枚举 ###

在遇到子集问题的处理时候，我们有时候会借助二进制枚举来遍历各种状态(效率大于dfs回溯)。这种就属于排列组合的问题了，对于每个物品(位置)来说，就是使用和不使用的两个状态，而在二进制中刚好可以用1和0来表示。而在实现上，通过枚举数字范围分析每个二进制数字各符号位上的特征进行计算求解操作即可。

![image-20210122160614157][]

二进制枚举的代码实现为：

for(int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
    {
        
      for(int j = 0; j < n; j++) //遍历二进制的每一位 共n位
      {
        
        if(i & (1 << j))//判断二进制数字i的第j位是否存在
        {
        
          //操作或者输出
        }
      }
    }

## 位运算经典问题 ##

有了上面的位运算基础，我们怎么用位运算处理实际问题呢？或者有哪些经典的问题可以用位运算来解决呢。

### 不用加减乘除做加法 ###

**题目描述**

> 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。

**分析**：  
这道题咋一听可能没啥思路，简单研究一下位运算还是能独立推出来和理解的。

当然，解决这题前，需要了解上面的四种位运算。还要知道二进制的运算：**0+0=0，0+1=1,1+1=0(进位)**

对于加法的一个二进制运算。**如果不进位**那么就是非常容易的。这时候相同位都为0则为0，0和1则为1.满足这种运算的**异或(不相同取1，相同取0)和或(有一个1则为1)都能满足.  
![在这里插入图片描述][2b7d193abd4e48577122db905a1bf10c.png]  
但事实肯定有进位的运算啊！看到上面操作的不足之后，我们肯定还需要解决进位的问题**对于进位的两数相加，**这种核心思想为**：

*  用两个数，**一个正常m相加**(不考虑进位的)。用**异或a^b**就是满足这种要求，先不考虑进位(如果没进位那么就是最终结果)。另一个**专门考虑进位的n**。两个1需要进位。所以我们用**a&b与**记录需要进位的。但是还有个问题，进位的要往上面进位，所以就变成这个需要进位的数左移一位。
 *  然后就变成**m+n**重新迭代开始上面直到不需要进位的(即n=0时候)。

![在这里插入图片描述][06342a7bff0496e5d2d2e8df40b01bb0.png]

实现代码为：

public class Solution {
        
        	public int Add(int num1,int num2) {
        
    		/*
    		 *  5+3   5^3(0110)   5&3(0001) 
    		 *  0101    
    		 *  0011 
    		 */
    		int a=num1^num2;
    		int b=num1&num2;
    		b=b<<1;
    		if(b==0)return a;
    		else {
        
    			return Add(a, b);
    		}        
    	 }
    }

当然，这里也可以科普一下二进制求加法：**average = （a&b） + ((a^b)>>1)** ;

### 二进制中1的个数 ###

这是一道经典题，在剑指offer上也有对应题目，其具体题目要求**输入一个整数，输出该数二进制表示中1的个数(其中负数用补码表示)**。

对于这个问题，不用位运算将它转成二进制字符串直接枚举字符’1’的个数也可以直接求出来，但是这样做是没有灵魂的并且效率比较差。这里提供两种解决思路

**法一**： 大家知道每个**类型的数据它的背后实际都是二进制操作**。大家知道int的数据类型的范围是(-231,231 -1)。并且int有32位。但是并非32位全部用来表示数据。**真正用来表示数据大小的也是31位。最高位用来表示正负**。

首先要知道：

> 1<<0=1 =00000000000000000000000000000001  
> 1<<1=2 =00000000000000000000000000000010  
> 1<<2=4 =00000000000000000000000000000100  
> 1<<3=8 =00000000000000000000000000001000  
> . . . . . .  
> 1<<30=2^30 =01000000000000000000000000000000  
> **1<<31=-2^31 =10000000000000000000000000000000**

其次还要知道位运算`&`与。两个十进制与运算.**每一位同1为1**。所以我们用2的正数次幂与知道的数分别进行与运算操作。**如果结果不为0，那么就说明这位为1.**(前面31个都是大于0的最后一个与结果是负数但是如果该位为1那么结果肯定不为0)

![image-20210122170223380][]

具体代码实现为：

public int NumberOf1(int n) {
        
      int va=0;
      for(int i=0;i<32;i++)
      {
        
        if((n&(1<<i))!=0)
        {
        	        		
          va++;
        }
      }
      return va;	      
    }

**法二**是运用`n&(n-1)`。n如果不为0，那么`n-1`就是**二进制第一个为1的变为0，后面全为1**.这样的`n&(n-1)`一次运算就相当于把最后一个1变成0.这样一直到运算的数为0停止计算次数就好了，如下图共进行三次运算那么n的二进制中就有三个1。  
![image-20210122163518288][]  
实现代码为：

public class Solution {
        
        public int NumberOf1(int n) {
        
    	   int count=0;
    	   while (n!=0) {
        
    		   n=n&(n-1);
    		   count++;
    	   }
    	   return count;
    	}
    }

### 只出现一次的(一个)数字① ###

**问题描述：**

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

**分析：**

这是一道简单的面试题，面试官常问怎么样用不太复杂的方法找出数组中仅出现一次的数字(其他均出现两次)，暴力枚举或者使用其他的存储结构都不够优化，而这个问题最高效的答案就是使用位运算。首先你要注意两点：

*  0和任意数字进行异或操作结果为数字本身.
 *  两个相同的数字进行异或的结果为0.

具体的操作就是用0开始和数组中每个数进行异或，得到的值和下个数进行异或，最终获得的值就是出现一次(奇数次)的值。

![image-20210122002813297][]

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

### 只出现一次的(一个)数字② ###

**问题描述：**

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

**分析：**

这题和上一题的思路略有不同，这题其他数字出现了3次，那么我们如果直接使用位运算异或操作的话无法直接找到结果，就需要巧妙的运用二进制的其他特性：**判断整除求余**操作。即判断所有数字二进制1的总个数和0的总个数一定有一个不是三的整数倍，如果0不是三的整数倍那么就说明结果的该位二进制数字为0，同理否则为1.

![image-20210122122756549][]

在具体的操作实现上，问题中给出数组中的数据在int范围之内，那么我们就可以在实现上可以对int的32个位每个位进行依次判断该位1的个数求余3后是否为1，如果为1说明结果该位二进制为1可以将结果加上去。最终得到的值即为答案。

具体代码为：

class Solution {
        
        public int singleNumber(int[] nums) {
        
            int value=0;
            for(int i=0;i<32;i++)
            {
        
                int sum=0;
                for(int num:nums)
                {
        
                    if(((num>>i)&1)==1)
                    {
        
                        sum++;
                    }
                }
                if(sum%3==1)
                    value+=(1<<i);
            }
            return value;
        }
    }

### 只出现一次的(两个)数字③ ###

**题目描述**

> 一个整型数组里除了两个数字之外，**其他的数字都出现了两次**。请写程序找出这两个只出现一次的数字。

**思路**：

上面的问题处理和理解起来可能比较容易，但是这个问题可能稍微复杂一点，但是这题可以通过特殊的手段转化为上面只出现一次的一个数字问题来解决，当然核心的位运算也是异或`^`。

具体思路就是想办法**将数组逻辑上一分为二**！先异或一遍到最后得到一个数，得到的肯定是`a^b`(假设两个数值分别为a和b)的值。在看异或`^`的属性：不同为1，相同为0. 也就是说最终这个结果的二进制为1的位置上a和b是不相同的。而我们可以找到这个第一个不同的位，然后将数组中的数分成两份，该位为0的进行异或求解得到其中一个结果a，该位为1的进行异或求解得到另一个结果b。

具体可以参考下图流程：

![image-20210121225712670][]

实现代码为：

public int[] singleNumbers(int[] nums) {
        
        int value[]=new int[2];
        if(nums.length==2)
            return  nums;
        int val=0;//异或求的值
        for(int i=0;i<nums.length;i++)
        {
        
            val^=nums[i];
        }
        int index=getFirst1(val);
        int num1=0,num2=0;
        for(int i=0;i<nums.length;i++)
        {
        
            if(((nums[i]>>index)&1)==0)//如果这个数第index为0 和num1异或
                num1^=nums[i];
            else//否则和 num2 异或
                num2^=nums[i];
        }
        value[0]=num1;
        value[1]=num2;
        return  value;
    }
    
    private int getFirst1(int val) {
        
        int index=0;
        while (((val&1)==0&&index<32))
        {
        
            val>>=1;// val=val/2
            index++;
        }
        return index;
    }

## 结语 ##

当然，上面的问题可能有更好的解法，也有更多经典位运算问题将在后面归纳总结，希望本篇的位运算介绍能够让你有所收获，对位运算能有更深一点的认识。对于很多问题例如博弈问题等二进制位运算能够很巧妙的解决问题，日后也会分享相关内容，敬请期待！

原创不易，如果觉得有所收获，希望大家点赞、分享、在看一键三连帮忙扩散，谢谢！

咱们下次再见！

![image-20201114211553660][]

[bigsai]: https://mp.weixin.qq.com/s/IW_GNK254ijIuuupjJsKCA
[Link 1]: https://github.com/javasmall/bigsai-algorithm
[image-20210103203435246]: /images/20221119/5e5751244356478eae5690d0aeb33a02.png
[image-20210103203852165]: /images/20221119/b53688e6d1fa4d8890f287c80a718a4e.png
[image-20210103204258194]: /images/20221119/713aaa8a26694668b3f638ddd7da8fd8.png
[image-20210103204832085]: /images/20221119/cc6b4fc483034e468dde62364e25010c.png
[image-20210111203911045]: /images/20221119/7118f3a8c0ca42bfa0caf63f878619d4.png
[image-20210112233233639]: /images/20221119/dd4ae18a96594f228fad6da2cf3eb0cd.png
[image-20210122160614157]: /images/20221119/b05cadd2432b4f3189b66ab9c96ac83b.png
[2b7d193abd4e48577122db905a1bf10c.png]: /images/20221119/6789c4e088514fff8e8edfe2e2bcdc4b.png
[06342a7bff0496e5d2d2e8df40b01bb0.png]: /images/20221119/aab04abf063f4d97b5322d9c550244cb.png
[image-20210122170223380]: /images/20221119/7459b71e80ff47c5aad72aacb00e097c.png
[image-20210122163518288]: /images/20221119/bed33b5948ae4cd5b03dfeb4794c11f2.png
[image-20210122002813297]: /images/20221119/e68494ec59044d46961ac3003cf6f068.png
[image-20210122122756549]: /images/20221119/795f7b6e09114289a6408865dc38110d.png
[image-20210121225712670]: /images/20221119/fa503274e1454f07bd4d505b98145c0d.png
[image-20201114211553660]: /images/20221119/109a7b0c6ae0470b89af75bd8f1dc4ab.png