解析位运算

为什么要学习位运算

位运算能够高效率的完成数值的计算，因为机器本身就是基于二进制的存储和计算，所有的数值或者对象最终都要转化为二进制，对象的话，可能需要一些编解码的动作，位运算主要是针对数据运算的，把人们熟悉的数字转化为机器熟悉的数字，其中又牵扯到原码，反码和补码，补码的出现是为了减低机器运算的复杂度，把减法转变为加法，可以这么说机器运算只有加法和移位，乘法最终是通过加法和移位操作完成的，而除法首先转变为乘法。

大多数位运算出现在底层的算法逻辑中，当然不乏有人为了显示高逼格，会把2*2写成1<<2。

当然，除了这些原因，还有一个极其重要的原因-----算法，因为最近一段时间在练习算法题，猛然发现位运算的重要性。

先来看看有哪些运算符

举例

public class Test {
  public static void main(String[] args) {
     int a = 60; // 60 = 0011 1100 
     int b = 13; // 13 = 0000 1101
     int c = 0;
     c = a & b;       // 12 = 0000 1100
     System.out.println("a & b = " + c );
 
     c = a | b;       // 61 = 0011 1101 
     System.out.println("a | b = " + c );
 
     c = a ^ b;       // 49 = 0011 0001
     System.out.println("a ^ b = " + c );
 
     c = ~a;          // -61 = 1100 0011 */
     System.out.println("~a = " + c );
 
     c = a << 2;     // 240 = 1111 0000 
     System.out.println("a << 2 = " + c );
 
     c = a >> 2;     // 15 = 1111
     System.out.println("a >> 2  = " + c );
  
     c = a >>> 2;     // 15 = 0000 1111
     System.out.println("a >>> 2 = " + c );
  }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

来展现一下位运算的方便吧

剑指 Offer II 070. 排序数组中只出现一次的数字
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

输入: nums = [3,3,7,7,10,11,11]
输出: 10

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
           // 使用位运算来判断mid是偶数还是奇数，
           //偶数运算结果则为 mid  与 mid + 1
          //奇数位 mid 与 mid - 1  
            if (nums[mid] == nums[mid ^ 1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这道题是采用了二分法，我们首先要知道的是，数组长度必为奇数，因为数组中只存在一个与其他数都不相同的元素，所以我们也可以知道，以该元素为分割，左右两边的元素个数必定为偶数，并且在该元素左边必定有nums[i] = nums[i+1],右边必定有nums[i] = nums[i-1],由此我们可以由二分法得出结果。

再来一个例子
剑指 Offer 65. 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

因为这道题要求我们不能使用“+” “-” “*” “/”，那我们只能想到用位运算来解决问题了。

class Solution {
    public int add(int a, int b) {
        // sum记录为进位的和 tmp记录进位
        int sum, tmp;
        do{
            sum = a ^ b;
            tmp = (a & b) << 1;
            a = sum;
            b = tmp;
        }while(tmp != 0);
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

首先，我们使用异或运算计算出不进位的结果例如 1+1 如果不进位 异或的结果就为0000 0000，然后再进行进位的运算 1+1 的结果就是0000 0010，或者 5+7举例，不进位运算就是 0000 0010，进位运算结果就是 0000 1010,之后循环运算即可得出结果。