位运算简介及基本技巧

Algorithms

什么是位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：

110 AND 1011 --> 0010(b) --> 2(d)

由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。本文就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。

位运算基础

基本的位操作符有与、或、异或、取反、左移、右移这6种，它们的运算规则如下所示：

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
丨 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

需要注意以下几点：

  • 这6种操作符，只有~取反是单目操作符，其它5种都是双目操作符；

  • 位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错；

  • 移位操作都是采取算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。如下面代码会输出-4和3；

    1
    2
    3
    a, b = -15, 15
    puts a >> 2
    puts b >> 2

    因为15=0000 1111(二进制)，右移二位，最高位由符号位填充将得到0000 0011即3。-15 = 1111 0001(二进制)，右移二位，最高位由符号位填充将得到1111 1100即-4。

  • 位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序，否则很可能会得到莫明其妙的结果。比如要得到像1，3，5，9这些2^i+1的数字。写成a = 1 << i + 1是不对的，程序会先执行i + 1，再执行左移操作。应该写成a = (1 << i) + 1;

  • 另外位操作还有一些复合操作符，如&=、|=、 ^=、<<=、>>=。

常用位操作小技巧

下面对位操作的一些常见应用作个总结，有判断奇偶、交换两数、变换符号及求绝对值。这些小技巧应用易记，应当熟练掌握。

判断奇偶

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

下面程序输出0到100之间的所有奇数。

1
2
3
100.times do |i|
  puts i if i & 1
end

交换两数

一般交换函数的写法是：

1
2
3
4
5
6
7
def swap(a, b)
  if a != b
    c = a
    a = b
    b = c
  end
end

注：ruby中这么写简直就是蠢，a, b = b, a即可，这里方便举例。

可以用位操作来实现交换两数而不用第三方变量：

1
2
3
4
5
6
7
def swap(a, b)
  if a != b
    a ^= b
    b ^= a
    a ^= b
  end
end

可以这样理解：

  1. a ^= b 即a = (a ^ b);
  2. b ^= a 即b = b ^ (a ^ b)，由于^运算满足交换律，b ^ (a ^ b)=b ^ b ^ a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值;
  3. a ^= b 就是a = a ^ b，由于前面二步可知a = (a ^ b)，b = a，所以a = a ^ b即a = (a ^ b) ^ a。故a会被赋上b的值。

再来个实例说明下以加深印象。a = 13, b = 6:
a的二进制为 13 = 8 + 4 + 1 = 1101(二进制)
b的二进制为 6 = 4 + 2 = 110(二进制)

  1. a ^= b a = 1101 ^ 110 = 1011;
  2. b ^= a b = 110 ^ 1011 = 1101; 即b == 13
  3. a ^= b a = 1011 ^ 1101 = 110; 即a == 6

变换符号

变换符号就是正数变成负数，负数变成正数。
如对于-11和11，可以通过下面的变换方法将-11变成11:

1111 0101(二进制)
取反-> 0000 1010(二进制) 
加1-> 0000 1011(二进制)

同样可以这样的将11变成-11

0000 1011(二进制)
取反-> 1111 0100(二进制)
加1-> 1111 0101(二进制)

因此变换符号只需要取反后加1即可。完整代码如下：

1
2
3
def sign_reversal(n)
  return ~n + 1
end

求绝对值

位操作也可以用来求绝对值，对于负数可以通过对其取反后加1来得到正数。对-6可以这样：

1111 1010(二进制)
取反->0000 0101(二进制)
加1-> 0000 0110(二进制)

来得到6。

因此先移位来取符号位，i = a >> 31;要注意如果a为正数，i等于0，为负数，i等于-1。然后对i进行判断——如果i等于0，直接返回；否之，返回~a + 1。完整代码如下：

1
2
3
4
def my_abs(n)
  i = n >> 31
  return i == 0 ? n : (~n + 1)
end

现在再分析下。对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，n与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：

1
2
3
4
def my_abs(n)
  i = a >> 31
  return ((a ^ i) - i)
end

注意这种方法没用任何判断表达式，而且有些笔面试题就要求这样做，因此建议读者记住该方法。

两个位运算的实例

Single Number

原题

一个数组中除了一个数字出现过一次外，其余的数字都出现了两次，找出那个只出现一次的数字。

注意点：

  • 算法时间杂度要求为O(n)
  • 空间复杂度为O(1)

例子:

输入: nums = [1, 2, 3, 4, 3, 2, 1]
输出: 4

解题思路

非常常见的一道算法题，将所有数字进行异或操作即可。对于异或操作明确以下三点：

  • 一个整数与自己异或的结果是0
  • 一个整数与0异或的结果是自己
  • 异或操作满足交换律，即a^b=b^a

所以对所有数字进行异或操作后剩下的就是那个只出现一次的数字。

AC源码

1
2
3
4
5
6
7
def single_number(nums)
  res = 0
  nums.each do |num|
    res ^= num
  end
  res
end

Power Of Two

原题

这道题让我们判断一个数是否为2的次方数，而且要求时间和空间复杂度都为常数。

解题思路

比较下x - 1和x的关系试试？以x=4为例。

0100 ==> 4
0011 ==> 3

两个数进行按位与就为0了！如果不是2的整数幂则无上述关系，反证法可证之。

AC源码

1
2
3
def is_power_of_two(n)
 return (n > 0 and not (n & n-1))
end