位相关

Posted on | Post modified: | In |
Words count in article: 762

数组中的重复数字

使用unsigned char 来标记8个数，这样每一个字节就能表示8个数，用每位上的0， 1来表示是否被标记。于是可以用1/8的空间和较高速率的位运算来实现对一定范围内数字的标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    unsigned char cnt[(100000 >> 3) + 1]={0};
    int findRepeatNumber(vector<int>& nums) {
        std::ios::sync_with_stdio(false);  // 读写效率
        for (const auto &n : nums) {
            if (cnt[n >> 3] & 0x1 << (n & 0x7))  // 数被映射到bit上
                return n;
            cnt[n >> 3] |= 0x1 << (n & 0x7);  // 以8（字节）为单位，将数压缩到bit上
        }
        return 0;
    }
};

比特位计数

最简单的方法是对每个数字都计算一次它的二进制1数量，通过$n \& (n - 1)$每次借位去掉一个1不断迭代得到。但是这里面包含了很多重复计算，因为计算的数字是连续的，并且在计算一个数字时它之前的数字结果已经计算过了，因此可考虑使用动态规划。根据二进制中1的变化特定，可以有三种考虑方向。

  1. 最高有效位

如图，在最高有效位相同的情况下，其后面的位可由之前的数字得到。比如2，3的最高有效位相同，它们后面的位可由0，1得到。而4，5, 6， 7后面的位可由0， 1， 2， 3得到。这个逐渐扩大的范围正是2的幂次。因此计算一个数二进制1的个数可通过最高有效位+之前对应的数。

1600415848299

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> countBits(int num) {
    vector<int> dp(num + 1);
    int base = 1, idx = 0;
    while (base <= num) { // 以2的幂为单位
        while (idx < base && idx + base <= num){
            dp[idx + base] = dp[idx] + 1;
            ++ idx;
        }
        idx = 0;
        base <<= 1;
    }
    return dp;
}
  1. 最低有效位

这个比较显然，一个数除2之后只有最低位变化，那么可得$dp[i] = dp[i >> 1] + (i \& 1)$ ；

1
2
3
4
5
6
7
vector<int> countBits(int num) {
    vector<int> dp(num + 1);
    for (int i = 1; i <= num; ++ i) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}
  1. 数量变动位

最开始说了通过$n \&(n - 1)$可以直接得到去掉一个1后的数，那么可以直接用该数的1数量 + 1得到当前的结果。

1
2
3
4
5
6
7
vector<int> countBits(int num) {
    vector<int> dp(num + 1);
    for (int i = 1; i <= num; ++ i) {
        dp[i] = dp[i & ( i - 1 )] + 1;
    }
    return dp;
}

数字压位与位运算

用字节中的8个位表示8位数是否出现，出现则该位为1. 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    unsigned char cnt[(100000 >> 3) + 1] = {0};
    int findRepeatNumber(vector<int>& nums) {
        std::ios::sync_with_stdio(false);
        for (const auto &n : nums) {
            if (cnt[n >> 3] & 0x1 << (n & 0x7))  // 数被映射到bit上
                return n;
            cnt[n >> 3] |= 0x1 << (n & 0x7);  // 以8（字节）为单位，将数压缩到bit上
        }
        return 0;
    }
};