alighters

程序、写作、人生

位运算之巧用

| Comments

之前接触到位运算的时候,总是似懂非懂,一脸萌比。最近花点时间,细细研究,其实发现也相当简单。下面来举两个相当实用的例子,来彻底掌握位运算。

异或实现交换

在涉及到两个数的相交换的诸多实现中,一个不错的及格的算法,就是利用加法来做。如下:

1
2
3
a = a + b;
b = a - b;
a = a - b;

写出这个的话,还算不错,再来个惊艳的,就是利用位运算,如下:

1
2
3
a = a ^ b;
b = a ^ b;
a = a ^ b;

如此工整的代码也是没谁了。初始乍看起来,是一脸懵逼,不知道其到底原理何在? 首先,说说加法。加法与减法是相对的,因为相加得到的和为固定值,再利用减法可以逆转回去,根据其中相加两个数的一个值,得到另一个值。这里,我称之为加减法的可逆转性。 再者,来看看异或运算,是如何做到的?先看如下的表格,来理解异或运算的特性。

Tables Col1 Col2 Col3 Col4
a 0 1 0 1 |
b 0 1 1 0 |
c(result) 0 0 1 1 |

其中,c 为 a ^ b 的值,可以看出异或最直白的表述为相同为假(即0),不同为真(即1)。另外,也可以运算得出 a = b ^ c, b = a ^ c。我称之为真正的可逆性,即不再需要其他运算符,即可再转换回去。

这时,结合上述的表格,便可理解上述的异或交换算法了。(若是没理解,也不用着急,算法就是慢慢理解,慢慢消化的,可在闲时慢慢回想,揣摩这段简单的代码。)

实现两个数的相加

这是在网上看到的一道面试题,需要不采用加减乘除的四则运算,来实现一个数的 7倍。

7 倍的问题可以转换为(8 – 1) 的问题,即左移 3 位,然后加上自身的负数。最终还是转换为如何实现加法的问题。所以这里只关注如何实现加法的核心问题。

首先,先以两个二进制数相加,查看其有什么特征。

0 1 1 0 0 1 0 0 这两个数相加,可得 1010, 期间可拆分为两个过程,相对应的位数为 0 与 1 或 1 与 0 相加所得为 1 的过程一;相对应的位数为 1 与 1 相加所得为 10,即需要发生进位的过程二。(0 与 0 相加为 0,不需要考虑)。

过程一可转换为异或运算,过程二转换为与运算,然后左移一位,来发生进位。若此时所得的数为 0,则表示没有进位发生,上步异或的结果,即为运算的结果;若不为 0,则表示有进位,则需要拿这个数,与相与所得的数,来重复过程一,过程二。写出的算法如下:

1
2
3
4
5
6
7
8
9
public static int add(int x, int y) {
  int result;
  while (x != 0) {
      result = x ^ y;
      x = (x & y) << 1;
      y = result;
  }
  return y;
}

测试所得,对负数也是没问题的,(这里只要不发生溢出,都是没有问题的)。纠其原因,还是计算机在运算的时候,是采用补码的形式来运行的。另外补码的相加减,符号位也是参与运算的。

参考资料

版权归作者所有,转载请注明原文链接:/blog/2016/10/27/bit-skill/

给 Ta 个打赏吧...

Comments