前言
位运算暗藏在编程语言的角落中，其神秘而又弱小，暗藏内力，有些人光听位运算的小名的心中忐忑，还有些人更是一看到位运算就远远离去，我之前也是。但刁滑的面试官往往喜爱搞偷袭，抓住咱们的弱点搞咱们，为了防患于未然，特记此篇！
本篇的内容为位运算的介绍和一些比拟经典的位运算问题进行介绍剖析，当然，位运算这么牛，前面必定还是要演绎总结的。
意识位运算
什么是位运算？
程序中的所有数在计算机内存中都是以二进制的模式贮存的。位运算就是间接对整数在内存中的二进制位进行操作。
位运算就是间接操作二进制数，那么有哪些品种的位运算呢？
常见的运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>>是带符号右移 >>>无符号右挪动)。上面来细看看每一种位运算的规定。
位运算 & (与)
规定：二进制对应位两两进行逻辑AND运算(只有对应位的值都是 1 时后果才为 1, 否则即为 0)即 0&0=0, 0&1=0, 1&1=1
例如：2 & -2
位运算 | (或)
规定：二进制对应位两两进行逻辑或运算(对应位中有一 个为1则为1) 即0|0=0,0|1=1,1|1=1
例如：2 | -2
位运算 ^ (异或)
规定：二进制对应位两两进行逻辑XOR (异或) 的运算(当对应位的值不同时为 1, 否则为 0)即0^0=0, 0^1=1, 1^1=0
例如：2 ^ -2
按位取反~
规定：二进制的0变成1，1变成0。
移位运算符
左移运算<<：左移后左边位补 0
右移运算>>：右移后右边位补原最左位值(可能是0，可能是1)
右移运算>>>：右移后右边位补 0
- 对于左移运算符
<<没有悬念右侧填个零无论正负数相当于整个数乘以2。 - 而右移运算符就有一致了，别离是左侧补0
>>>和左侧补原始位>>，如果是负数没争议左侧都是补0，达到除以2的成果；如果是正数的话左侧补0>>>那么数值的正负会产生扭转，会从一个正数变成一个绝对较大的负数。而如果是左侧补原始位(正数补1)>>那么整个数还是正数，也就是相当于除以2的成果。
上面这张图能够很好的帮忙你了解正数的移位运算符：
到这里，我想你应该对位运算有了初步的意识，在这里把下面提到的局部案例执行比照一下让你看一下可能会了解的更清晰：
位运算小技巧
在这里有些罕用的位运算小技巧。
判断奇偶数
失常判断奇数偶数的时候咱们会这样写：
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^bb=a^b;//b=(a^b)^b=a^0=aa=a^b;//a=(a^b)^(a^b^b)=0^b=0原理曾经写在正文外面了，是不是感觉十分diao呢？
二进制枚举
在遇到子集问题的解决时候，咱们有时候会借助二进制枚举来遍历各种状态(效率大于dfs回溯)。这种就属于排列组合的问题了，对于每个物品(地位)来说，就是应用和不应用的两个状态，而在二进制中刚好能够用1和0来示意。而在实现上，通过枚举数字范畴剖析每个二进制数字各符号位上的特色进行计算求解操作即可。
二进制枚举的代码实现为：
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)都能满足.
但事实必定有进位的运算啊！看到下面操作的有余之后，咱们必定还须要解决进位的问题对于进位的两数相加，这种核心思想为：
- 用两个数，一个失常m相加(不思考进位的)。用异或a^b就是满足这种要求，先不思考进位(如果没进位那么就是最终后果)。另一个专门思考进位的n。两个1须要进位。所以咱们用a&b与记录须要进位的。然而还有个问题，进位的要往上面进位，所以就变成这个须要进位的数左移一位。
- 而后就变成m+n从新迭代开始下面直到不须要进位的(即n=0时候)。
实现代码为：
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的数据类型的范畴是(-2^31,2^31 -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)
具体代码实现为：
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。
实现代码为：
public class Solution { public int NumberOf1(int n) { int count=0; while (n!=0) { n=n&(n-1); count++; } return count; }}只呈现一次的(一个)数字①
问题形容：
给定一个非空整数数组，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素。阐明：你的算法应该具备线性工夫复杂度。 你能够不应用额定空间来实现吗？
剖析：
这是一道简略的面试题，面试官常问怎么样用不太简单的办法找出数组中仅呈现一次的数字(其余均呈现两次)，暴力枚举或者应用其余的存储构造都不够优化，而这个问题最高效的答案就是应用位运算。首先你要留神两点：
- 0和任意数字进行异或操作后果为数字自身.
- 两个雷同的数字进行异或的后果为0.
具体的操作就是用0开始和数组中每个数进行异或，失去的值和下个数进行异或，最终取得的值就是呈现一次(奇数次)的值。
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.
在具体的操作实现上，问题中给出数组中的数据在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。
具体能够参考下图流程：
实现代码为：
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;}结语
当然，下面的问题可能有更好的解法，也有更多经典位运算问题将在前面演绎总结，心愿本篇的位运算介绍可能让你有所播种，对位运算能有更深一点的意识。对于很多问题例如博弈问题等二进制位运算可能很奇妙的解决问题，日后也会分享相干内容，敬请期待！
原创公众号：bigsai
原创不易，如果有播种请不要悭吝你的赞赞！
文章已收录在 全网都在关注的数据结构与算法学习仓库
咱们下次再见！