位运算
在位计算之前，我先讲一下原码、反码和补码。
计算机字节长是8位， 而我们正常是显示一个10进制数3：
0000 0011
这是一个正数， 如果是负数的话， 在最高位进行标记，如果正数为0， 负数为1
3 = 0000 0011
-3 = 1000 0011
如果要计算两个数和时：
3 + 3 = 0000 0011 + 0000 0011 = 0000 0110 = 6
但是要计算两个数相减时：
3 - 3 = 3 + （-3）= 0000 0011 + 1000 0011 = 1000 0110 = -6
很明显这是错误的计算， 于是出现了反码， 其规则是：
1、正数的反码是其本身
2、负数的反码， 符号位不变其余取反
例子
3 = 0000 0011 = 0000 0011（取反）
-3 = 1000 0011 = 1111 1100 (取反）
现在我们使用反码进行计算：
如果要计算两个数和时：
3 + 3 = 0000 0011(反) + 0000 0011(反） = 0000 0110（正和反） = 6
但是要计算两个数相减时：
3 - 3 = 3 + （-3）= 0000 0011（反） + 1111 1100（反）
= 1111 1111（反）= 1000 0000（原） = -0
0就是0，怎么能有正负之分， 计算机最好是不要特殊处理， 以节省不必要的逻辑处理
于是补码出现了， 补码规则：
1、正数的补码就是其本身
2、负数的补码的规则，符号不变， 其余位取反， 最后是加1
现在我们使用补码计算：
如果要计算两个数和时：
3 + 3 = 0000 0011(补) + 0000 0011(补） = 0000 0110（原和补） = 6
但是要计算两个数相减时：
3 - 3 = 3 + （-3）= 0000 0011（补） + 1111 1101（补）
= 0000 0000（补）= 0000 0000（原） = 0
还有个特殊的情况，那就是-1 + -127 = -128
-1 + -127 = 1000 0001(原) + 1111 1111(原) = 1111 1111(补) + 1000 0001(补)
= 1000 0000（补）(无法转回原码)
所以补码1000 0000就是-128
8位可以表示的范围[-128, 127] = [-2^7,2^7-1]
int占4位字节， 4 * 8=32位， 范围[ -2^31~2^31-1 ]
位算法是一种高效率运算方式。在计算机中，数据都会以二进制代码的形式进行存储。位运算符号有以下几种：
| 符号 | 描述 | 规则 |
|---|---|---|
| & | 按位与 | 两位全为1，结果才为1，见0则为0 |
| l | 按位或 | 两位全为0，结果才为0，见1则为1 |
| ^ | 异或 | 相同为0，不同为1 |
| ~ | 取反 | 0变1,1变0 |
| << | 左移 | 二进制位向左移动1位，高位去掉，低位补0，相当于乘2 |
| >> | 右移 | 二进制位向右移动1位，低位去掉，高位补0，相当于除2 |
1、位运算应用举例
判断奇偶数
判断一个数是基于还是偶数，相信很多人都做过，一般的做法的代码如下
if( n % 2 == 1） n 为奇数
如果把 n 以二进制的形式展示的话，其实我们只需要判断最后一个二进制位是 1 还是 0 就行了，如果是 1 的话，代表是奇数，如果是 0 则代表是偶数，所以采用位运算的方式的话，代码如下：
if(n & 1 == 1) n 为奇数。
在我们写成 n % 2 的形式，程序在运行时编译器也会自动帮我们优化成位运算。但我们自己能够采用位运算的形式写出来，将编译器要做的事情提前做了，时间效率也会快很多。
偶数的二进制编码最低位为是0 奇数的二进制编码最低位为是1 于是我们每次位与1， 就可以奇数会得到1， 偶数会得到0 3 & 1 = 11 & 01 = 1 = 1 2 & 1 = 10 & 01 = 0 = 0
2、交换两个数的值
交换数值在程序中经常用到，一般情况下都会使用一个额外的临时变量来进行辅助交换，我们要交换 a 与 b 值，传统代码如下：
int tmp = a; a = b; b = tmp;
这里我们也可以用异或来完成交换操作
a = a ^ b b = a ^ b a = a ^ b
三行代码都是 a ^ b，就莫名交换成功了。我们看一下是如何实现的吧。
a = 3, b= 5 a = a ^ b = 011 ^ 101 = 110 b = a ^ b = 110 ^ 101 = 011 = 3 a = a ^ b = 110 ^ 011 = 101 = 5 a = 5, b = 3
3、m的n次方
如果让你实现pow函数的功能，求解 m 的 n 次方，该如何呢？我们可能会这样写：
public static int pow(int n){
int sum = 1;
for(int i = 0; i <n; i++) {
sum * =m;
}
return sum;
}这样做的话，时间复杂度为 O(n) ！如果用位运算来做，时间复杂度接近为 O(logn)!
我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:
m^1101 = m^0001 * m^0100 * m^1000。
我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。
public static int pow(int n){
int sum = 1;
int tmp = m;
while(n != 0){
if(n & 1 == 1){
sum *= tmp;
}
tmp *= tmp;
n = n >> 1;
}
return sum;
}时间复杂度近为 O(logn)，而且看起来很牛逼！
这里又想到青蛙跳台阶的问题
我们列出前几阶对应的步数分别为：
0,1,2,4,8,16……
可以得出公式 步数 step=2^(n-1);
用代码表示就是：
int step=Math.pow(2,n-1);
但这里我们使用左移运算符进行计算
public static int JumpFloorII(int n) {
int a=1;
return a<<(n-1);
}这里a<<(n-1) 相当于 1*2^(n-1)=2^(n-1)
这里说一下，位运算很多情况下都是很二进制扯上关系的，所以我们要判断是否适合位运算，很多情况下都会把他们拆分成二进制，然后观察特性，或者就是利用与，或，异或的特性来观察，总之，我觉得多看一些例子，加上自己多动手，就比较容易上手了。
4、找出没有重复的数
给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。
这道题可能很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)了。
然而我想告诉你的是，采用位运算来做，绝对高逼格！
我们刚才说过，两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身，所以我们把这一组整型全部异或一下，例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：
由于异或支持交换律和结合律，所以:
1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。
也就是说，那些出现了两次的数异或之后会变成0，那个出现一次的数，和 0 异或之后就等于它本身。所以代码如下
public static int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
tmp = tmp ^ arr[i];
}
return tmp;
}时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼。
5、找出不大于N的最大的2的幂指数
传统的做法就是让 1 不断着乘以 2，代码如下：
public static int findN(int N){
int sum = 1;
while(true){
if(sum * 2 > N){
return sum;
}
sum = sum * 2;
}
}这样做的话，时间复杂度是 O(logn)，那如果改成位运算，该怎么做呢？我刚才说了，如果要弄成位运算的方式，很多时候我们把某个数拆成二进制，然后看看有哪些发现。这里我举个例子吧。
例如 N = 19，那么转换成二进制就是 00010011（这里为了方便，我采用8位的二进制来表示）。那么我们要找的数就是，把二进制中最左边的 1 保留，后面的 1 全部变为 0。即我们的目标数是 00010000。那么如何获得这个数呢？相应解法如下：
- 1、找到最左边的 1，然后把它右边的所有 0 变成 1
2、把得到的数值加 1，可以得到 00100000即 00011111 + 1 = 00100000。
3、把 得到的 00100000 向右移动一位，即可得到 00010000，即 00100000 >> 1 = 00010000。
那么问题来了，第一步中把最左边 1 中后面的 0 转化为 1 该怎么弄呢？我先给出代码再解释吧。下面这段代码就可以把最左边 1 中后面的 0 全部转化为 1，
n |= n >> 1; n |= n >> 2; n |= n >> 4;
就是通过把 n 右移并且做或运算即可得到。我解释下吧，我们假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后，那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算，那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理，再次把 n 右移两位，那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算，那么就能得到第 k, k+1, k+2, k+3 都是 1，如此往复下去….
最终的代码如下
int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
return (n + 1) >> 1;
}这种做法的时间复杂度近似 O(1)，重点是，高逼格。
6、二进制中1的个数
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
}
}是不是不用转换成二进制，然后一位一位的判断了。
当然，java中有个函数专门用于统计二进制中1的个数
Integer.bitCount(n);
但是，如果题目规定不可以使用这个函数呢，那么毫无疑问，与运算将会是效率最高的解决方案。
投递联想等公司10个岗位 >
