位运算

在位计算之前，我先讲一下原码、反码和补码。
计算机字节长是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、位运算应用举例

判断奇偶数

判断一个数是基于还是偶数，相信很多人都做过，一般的做法的代码如下

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);

但是，如果题目规定不可以使用这个函数呢，那么毫无疑问，与运算将会是效率最高的解决方案。