共计 5097 个字符，预计需要花费 13 分钟才能阅读完成。
前言
位运算暗藏在编程语言的角落中，其神秘而又弱小，暗藏内力，有些人光听位运算的小名的心中忐忑，还有些人更是一看到位运算就远远离去，我之前也是。但刁滑的面试官往往喜爱搞偷袭，抓住咱们的弱点搞咱们，为了防患于未然，特记此篇！
本篇的内容为位运算的介绍和一些比拟经典的位运算问题进行介绍剖析，当然，位运算这么牛，前面必定还是要演绎总结的。
意识位运算
什么是位运算？
程序中的所有数在计算机内存中都是以二进制的模式贮存的。位运算就是间接对整数在内存中的二进制位进行操作。
位运算就是间接操作二进制数，那么有哪些品种的位运算呢？
常见的运算符有与(&)、或(|)、异或(^)、取反(~)、左移(<<)、右移(>> 是带符号右移 >>> 无符号右挪动)。上面来细看看每一种位运算的规定。
位运算 & (与)
规定：二进制对应位两两进行逻辑 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^b
b=a^b;//b=(a^b)^b=a^0=a
a=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
原创不易，如果有播种请不要悭吝你的 赞赞 ！
文章已收录在 全网都在关注的数据结构与算法学习仓库
咱们下次再见！
