@coldxiangyu 2017-05-23T05:39:01.000000Z 字数 3281 阅读 554

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

数据结构及算法

与运算：&



&：与（AND）运算。eg:2(0010)&7(0111) = 2(0010)

|：或（OR）运算。eg:2(0010)|7(0111) = 7(0111)

^：异或（XOR）运算。eg:2(0010)^7(0111) = 5(0101)

~：非（NOT）运算。eg:~2(0010) = -3(1101)

2(0000 0000 0000 0000 0000 0000 0000 0010)
~2(1111 1111 1111 1111 1111 1111 1111 1101)

<<：左移运算符。eg:2(0010)<<3 = 16(10000)

>>：右移运算符。eg:8(1000>>2) = 2(0010)

>>>：右移运算符。eg:8(1000>>2) = 2(0010)

此外，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.

a = 1, b = 3;
a = 0001,b = 0011;

1.通过一个数 & 1，我们可以得知它的二进制末位数是0还是1，也就能判断出一个数是奇数还是偶数。
2.二进制相同位同为1，相加进位。

0010 + 0010 = 0100 [0010 & 0010 = 0010 << 1 = 0100]
0011 + 0011 = 0110 [0011 & 0011 = 0011 << 1 = 0110]

a & b = 0001 也就是末位需要进位。

a ^ b = (1)0001 ^ (3)0011 = 0010 ，赋值给a = 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);}

//非递归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?

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 = 4Output: 2Explanation: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;    }}

• 私有
• 公开
• 删除