从头学算法（五、位运算）

数据结构及算法

刷LeetCode已经有一段时间了，中间遇到了不少关于位运算的解题思路，以至于在看到其他人给的solution之后会有“原来还可以这样做”的感叹。
我们回顾以下常用的位运算符都有哪些：

与运算：&
或运算：|
非运算：~
异或运算：^
左移运算：<<
右移运算：>>
右移运算（无符号）：>>>

位运算的操作对象是bit级的，我们要将数字转换成二进制来看。
&：与（AND）运算。eg:2(0010)&7(0111) = 2(0010)
运算过程：都为1时为1，其余为0

|：或（OR）运算。eg:2(0010)|7(0111) = 7(0111)
运算过程：有一位为1则为1，其余为0

^：异或（XOR）运算。eg:2(0010)^7(0111) = 5(0101)
运算过程：同则0，异则1

~：非（NOT）运算。eg:~2(0010) = -3(1101)
运算过程：0则1，1则0，按位取反
这里你一定会疑惑，1101明明是13，你不要骗我。
这里就需要了解反码和补码的概念了。
计算机存储的是补码，补码对于正数，是其本身。对于负数是取反码+1，-3(1101)取反码，0010， + 1，0011，也就是3。由此我们还可以推出， x 相反数为 ~x + 1。
关于原码、反码、补码，这里就不做过多介绍了，大家可以参考一下这篇：http://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html 写的很详细。
这里我们就知道，其实1101是一个补码，是谁的补码呢，跟我来。
首先你要知道，Integer类型是32位的，我们将2的字节码补全：
2(0000 0000 0000 0000 0000 0000 0000 0010)
~2(1111 1111 1111 1111 1111 1111 1111 1101)
那么(1111 1111 1111 1111 1111 1111 1111 1101)是谁的补码呢，我们按补码的过程逆向推一下，首位为符号位，保持不变：
先-1，再取反码(1000 0000 0000 0000 0000 0000 0000 0011)
符号位为1，值为-3。See？我没骗你吧。

<<：左移运算符。eg:2(0010)<<3 = 16(10000)
运算过程：左移n位，低位补0

>>：右移运算符。eg:8(1000>>2) = 2(0010)
运算过程：右移n位，值为正，高位补0，值为负，高位补1

>>>：右移运算符。eg:8(1000>>2) = 2(0010)
运算过程：右移n位，不论正负，高位补0

此外，x<<y 相当于 x*2的y次方 ；x>>y相当于x/2的y次方

OK，到这里，基本的东西介绍完了，这些大学接触完之后就再也没遇到过的东西究竟有什么应用呢？接下来我们就来搞一搞。

LeetCode题目一：

371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 3, return 4.

简而言之，就是不用加、减号进行两数求和。
这是一种非常典型的位运算。
我们以给的Example为例：
a = 1, b = 3;
a = 0001,b = 0011;
首先我们要对a,b进行与运算，a & b = 0001，赋值给c = 0001
我们想想与运算的特性，同1则1，其余为0.
这点你想到什么作用了呢？
1.通过一个数 & 1，我们可以得知它的二进制末位数是0还是1，也就能判断出一个数是奇数还是偶数。
2.二进制相同位同为1，相加进位。
比如 0001 + 0001 = 0010 [0001 & 0001 = 0001 << 1 = 0010]
0010 + 0010 = 0100 [0010 & 0010 = 0010 << 1 = 0100]
0011 + 0011 = 0110 [0011 & 0011 = 0011 << 1 = 0110]
由此可以看出，与运算的结果还可以判断出需要进位的二进制位数。
a & b = 0001 也就是末位需要进位。
接下来我们要使用^(XOR)，^有什么特性呢？相同为0，不同为1。由此我们常用异或来寻找不同位。
a ^ b = (1)0001 ^ (3)0011 = 0010 ，赋值给a = 0010
接下来，c = 0001 << 1 = 0010，赋值给b = 0010
循环上述过程，直到没有进位为止。
据此我们写出实现代码：

//非递归
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}
//递归
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

老实说，这个弯你能绕过来的话，位运算你就已经入门了。
那么如果a - b呢，

//非递归
public int getSubtract(int a, int b) {
    while (b != 0) {
        int borrow = (~a) & b;
        a = a ^ b;
        b = borrow << 1;
    }
    return a;
}
//递归
public int getSubtract(int a, int b) {
    return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}
//我们上面说到的取反
public int negate(int x) {
    return ~x + 1;
}

LeetCode题目二：

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

描述一下就是：在一个int数组中，除了一个元素只出现一次，其余元素都出现两次，找出其中出现一次的元素。
额外要求，算法必须保证时间复杂度不能超过O(n)

这个题目，如果你用循环遍历的方式，无疑将它复杂化了。
想一下，所有元素除了一个单元素，其余都是成对出现，你想到了什么？
这时候你想不到^这个东西就说不过去了。
相同元素异或值是什么，0啊
0异或任何值，还是该值本身啊
OK，这样我们已经得出了本题的算法：

public class Solution {
    public int singleNumber(int[] nums) {
        int temp = 0;
        for(int i = 0;i < nums.length;i++){
            temp ^= nums[i];
        }
        return temp;
    }
}

LeetCode题目三：

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 231.
Example:
Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

汉明距离问题，也是位运算的典型问题之一。
简单来说，汉明距离就是求两个数不同位的个数。
下面是我们给出的解决方案：

public class Solution {
    public int hammingDistance(int x, int y) {
        int i = 0;
        int temp = x ^ y;
        while (temp != 0) {
            i++;
            temp &= temp - 1;
        }
        return i;
    }
}

以上三个LeetCode实例，第一个理解之后，后面就很随意了。
最后抛出一个小彩蛋，a^b^a=b，自己证明着玩去吧。