美柑の部屋

涙は見せないと誓った。

たとえ僕らは、遠く離れてしまっても、いつもこの場所で、繋がっている。切なくてロマンチックだね、まだ知らない明日。

无论我们分隔多远，我们的羁绊总是在这里相连。引导着我们，走向那悲伤却浪漫的、尚无人知的明天。

————彩音「いつもこの場所で」

位运算的Tricks

很多初学程序设计的人不熟悉位运算，或者只是听说过名字，没有真正在程序中使用过。实际上，位运算不仅可以大大提升程序的执行速度，而且可以很巧妙地解决一些普通方法无法解决的问题。这篇文章就来盘点几个常见的位运算tricks。

一、交换两个整数

如何交换两个整数呢？不少人的第一反应是下面的代码：

1
2
3

int tmp = b;
b = a;
a = tmp;

如果对问题做一些限制：不能引入临时变量。那么很多人会进一步想到下面的代码：

1
2
3

a = a + b;
b = a - b;
a = a - b;

但是上面的代码有一个问题：当a和b太大的时候，有可能在执行a = a + b一行的之后直接溢出。有没有可以避免溢出，并且不引入临时变量的方法呢？答案就是利用异或运算。

1
2
3

a = a ^ b;
b = a ^ b;
a = a ^ b;

上面的代码为什么是正确的？我们要从异或谈起。异或运算满足三个性质：首先，一个数异或0等于它本身；其次，一个数异或它本身等于0；最后，异或满足交换律和结合律。
所以，第二句话中的b其实等于(a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a。
同理，第三句话中的a其实等于(a ^ b) ^ a = b ^ (a ^ a) = b ^ 0 = b。
这就达到了交换两个整数的目的。

二、判断整数二进制表示中1的个数

首先我们来观察a & (a - 1)这个表达式干了什么。
如果a的二进制最后一位是1，那么将a减一，即最后一位变为0，而前面其他位都不变，将a和a - 1按位与，也就相当于消掉了a的最后一个1。
如果a的二进制最后一位为0，且从右往左数第m位第一次出现1，那么将a减一，则第m位由1变成0，m右面的所有位都变成1，m左边的所有位不变。将a和a - 1按位与，还是相当于消掉了a的最后一个1。
总结：a & (a - 1)用来消去a的二进制表示的最右边的1。
所以，为了判断a的二进制表示中1的个数，我们可以一直让a与a - 1进行按位与，一直消掉最右边的1，直到所有的1全部消掉为止。这个判断方法对于负数好像依然有效。

1
2
3
4
5
6

int count = 0;
while(n){
    n &= (n-1);
    count++;
}
return count;

扩展：如何判断一个整数是否是2的整数次方？

思路与答案展开

扩展：输入一个非负整数n，我们要输出一个大小为n+1的数组arr，其中arr[i]表示i的二进制表示中所含有的1的个数。

思路与答案展开

三、数组中只出现一次的元素

有一个int类型的数组arr，其中除了一个元素只出现一次之外，其他的每个元素都出现正好两次。将这个单独的元素找出来。要求O(n)的时间复杂度以及O(1)的空间复杂度。
这个题仍然是利用异或运算的性质，我们只需要令res = 0，然后令res依次异或arr中的每个元素。这样，arr中成对出现的元素都会异或成0，最后剩余的就是那个单独的元素。

1
2
3
4
5
6

int singleNumber(vector<int>& nums) {
    int res = 0;
    for(int i=0; i<nums.size(); i++)
        res ^= nums[i];
    return res;
}

扩展：还是上面那个数组arr，这次变成了有两个单独的元素。需要把这两个单独的元素全部找出来。

思路与答案展开

扩展：还是上面那个数组arr，这次除去一个单独的元素之外，每个元素都出现正好三次。找出那个单独的元素。

思路与答案展开

四、求一个数组的所有子集

已知一个数组中没有相同的元素，且该数组长度不大于32，求它的所有子集，且每个子集中的元素按照从小到大的顺序排列。
通过集合论的知识，我们知道对于一个集合来说，若其元素个数为n，则其子集的个数为2 ^ n。对于任意一个子集，我们用一个长度为n的二进制串来表示元素的状态。如果第i位是1，说明原数组的第i个元素位于当前子集中，否则说明没有位于当前子集中。
因此我们可以枚举0到2 ^ n - 1，然后对其中的每一个数依次还原相应的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ret;
    int limit = (1 << nums.size()) - 1;
    sort(nums.begin(), nums.end());
    for (int i = 0; i <= limit; ++i){
        vector<int> tp;
        int p = i, now = 0;
        while(p){
            if (p & 1 == 1)
                tp.push_back(nums[now]);
            p >>= 1;
            ++now;
        }
        ret.push_back(tp);
    }
    return ret;
}

扩展：给定一个9×9大小的char类型数组，代表一个尚未被填充的数独。其中.代表该位置为空位，1-9代表该位置有数字，判断这个数独是否是有效的。（需要注意的是，一个有效的数独不一定有解，只需要初始状态下被填充的格子满足数独的要求即可。）

思路与答案展开

上面的两个问题使我们意识到，我们可以利用二进制记录一个元素在或不在的状态，也就是建立一个简易的hashset。事实上，在海量数据的处理问题中，经常用到一种类似的方法：将一组有范围的数据中的每一个数据映射为内存中的一个bit，该方法叫做bitmap。
例题：我们有40亿个不重复的无序unsigned int数据，然后给定一个数，如何快速判断这个数是否在那40亿个数当中？

思路与答案展开

扩展：如何在2.5亿个int中找出不重复的整数？

思路与答案展开

五、反转一个整数的二进制表示

将一个unsigned int类型的二进制表示中的32位反转，并输出得到的新整数。以4位二进制为例，如果输入为1（二进制为0001），则输出为8（二进制为1000）。
我们可以定义一个变量m = 0存储结果，每次将m左移一位，然后取原数字n的最低位赋给m的最低位，最后将n右移一位。这样循环32次即为结果。

1
2
3
4
5
6
7
8
9

uint32_t reverseBits(uint32_t n) {
    uint32_t m = 0;
    for(int i=0; i<32; i++){
        m <<= 1;
        m = m | (n & 1);
        n >>= 1;
    }
    return m;
}

当然，关于这个问题，还有许许多多更加变态的方法。下面举一例不那么变态的：
反转一个数的二进制表示，其实可以用类似于归并排序的方法完成。第一步，将原数字的第1位和第2位、第3位和第4位……依次交换；第二步，将原数字的第1-2位与第3-4位、第5-6位与第7-8位……依次交换；第三步，将原数字的第1-4位和5-8位、第9-12位和13-16位……依次交换。依次类推，对于32位的unsigned int类型，仅需进行log(32) = 5次即可完成。这种思路写成代码更是十分工整：

1
2
3
4
5
6
7
8
9

uint32_t reverseBits(uint32_t n) {
    uint32_t x = n;
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
    return x;
}

六、格雷码

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码。比如三位的典型格雷码序列为000, 001, 011, 010, 110, 111, 101, 100。现在输入一个整数n（不大于31），输出n位的典型格雷码序列。
我们不妨称k位的典型格雷码序列为ans{k}，如何由ans{k-1}得到ans{k}呢？
观察格雷码的规律我们可以发现，ans{k}的前半部分的最高位均为0，且除了最高位之外的部分与ans{k-1}完全相同；后半部分的最高位均为1，而除了最高位之外的部分正好和ans{k-1}成倒序关系。
通过这个规律，我们可以写出生成n位典型格雷码序列的递归版本和非递归版本。这里仅写出非递归版本：

1
2
3
4
5
6
7
8
9

vector<int> grayCode(int n){
    vector<int> ans(1, 0);
    for(int i = 0; i < n; i++){
        for (int j = ans.size() - 1; j >= 0; j--) {
            ans.push_back((1 << i) + ans[j]);
        }
    }
    return ans;
}

七、不使用四则运算符实现加法

考虑二进制下两个数相加的操作，其实分三步：
首先不考虑进位，完成两个数的加法运算，结果为sum；
然后只考虑进位，计算两个数相加之后的进位情况，结果为carryOver；
最后将sum和carryOver相加，注意这一步相当于递归调用，仍然是拆分成先不考虑进位计算加法，然后计算进位，最后二者相加这三步。递归的终止条件是carryOver的值是0。

那么如何用位操作实现第一步和第二步呢？
首先不考虑进位的情况下，0和0以及1和1都会得到0，而0和1以及1和0会得到1。这其实是二进制的异或运算。然后只考虑进位的情况下，只有1和1的情况下会进位，所以相当于是二进制的与运算之后左移一位。
我们可以列出表达式：a + b = (a ^ b) + ((a & b) << 1)。根据此表达式写出代码：

1
2
3
4
5
6
7
8
9
10
11
12

int Add(int num1, int num2)
{
  int sum;
  int carryOver;
  do{
      sum = num1 ^ num2;
      carryOver = (num1 & num2) << 1;
      num1 = sum;
      num2 = carryOver;
  }while(num2);
  return num1;
}

扩展：(x & y) + ((x ^ y) >> 1)是干什么用的？

思路与答案展开

总结

本篇文章总结了二进制和位运算的一些用途。其实，位运算还有很多其他的妙用，包括快速幂算法、树状数组等。有时间我会继续在博客上介绍这些内容。

评论