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

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

数据结构及算法


刷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

  1. Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
  2. Example:
  3. 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
循环上述过程,直到没有进位为止。
据此我们写出实现代码:

  1. //非递归
  2. public int getSum(int a, int b) {
  3. if (a == 0) return b;
  4. if (b == 0) return a;
  5. while (b != 0) {
  6. int carry = a & b;
  7. a = a ^ b;
  8. b = carry << 1;
  9. }
  10. return a;
  11. }
  12. //递归
  13. public int getSum(int a, int b) {
  14. return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
  15. }

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

  1. //非递归
  2. public int getSubtract(int a, int b) {
  3. while (b != 0) {
  4. int borrow = (~a) & b;
  5. a = a ^ b;
  6. b = borrow << 1;
  7. }
  8. return a;
  9. }
  10. //递归
  11. public int getSubtract(int a, int b) {
  12. return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
  13. }
  14. //我们上面说到的取反
  15. public int negate(int x) {
  16. return ~x + 1;
  17. }

LeetCode题目二:

136. Single Number

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

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

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

  1. public class Solution {
  2. public int singleNumber(int[] nums) {
  3. int temp = 0;
  4. for(int i = 0;i < nums.length;i++){
  5. temp ^= nums[i];
  6. }
  7. return temp;
  8. }
  9. }

LeetCode题目三:

461. Hamming Distance

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

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

  1. public class Solution {
  2. public int hammingDistance(int x, int y) {
  3. int i = 0;
  4. int temp = x ^ y;
  5. while (temp != 0) {
  6. i++;
  7. temp &= temp - 1;
  8. }
  9. return i;
  10. }
  11. }

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注