冷湘宇 Coldxiangyu's blog

从头学算法(五、位运算)


刷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,自己证明着玩去吧。


Comments

Content