BitMap - leetcode [位运算]

时间:2021-12-02 05:00:15

136. Single Number

因为A XOR A = 0,且XOR运算是可交换的,于是,对于实例{2,1,4,5,2,4,1}就会有这样的结果:

(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5
异或:异为1

137. Single Number II

这道题是之前那道 Single Number 单独的数字的延伸,那道题的解法就比较独特,是利用计算机按位储存数字的特性来做的,这道题就是除了一个单独的数字之外,数组中其他的数字都出现了三次,那么还是要利用位操作 Bit Operation 来解此题。我们可以建立一个32位的数字,来统计每一位上1出现的个数,我们知道如果某一位上为1的话,那么如果该整数出现了三次,对3去余为0,我们把每个数的对应位都加起来对3取余,最终剩下来的那个数就是单独的数字。代码如下:

BitMap - leetcode [位运算]
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i < 32; ++i) {
int sum = 0;
for (int j = 0; j < nums.size(); ++j) {
sum += (nums[j] >> i) & 1;
}
res |= (sum % 3) << i;
}
return res;
}
};

190. Reverse Bits

basic bit manipulation problem

用mask每次检查一位是0还是1,然后向左位移,依次从n的最右向左检查。

Let's say n = 43261596,  the binary format is: 00000010100101000001111010011100
In order to get the binary bits, mask is used here.
The idea of using mask to check 1 bit each time, using AND operation.

Mask moves 1 bit each time using << operation.
Mask can be computed and saved before to speed up the reverse function.

E.g. 
iteration 1:  mask = 0000...00001,  then mask & n  = 0
iteration 2:  mask = 0000...00010, then mask & n  = 0
iteration 3:  mask = 0000...00100,  then mask & n  = 1
iteration 4:  mask = 0000...01000, then mask & n  = 1
...
iteration 32:  mask = 1000...00000, then mask & n  = 0

In this way, binary bits can be obtained from 32 iterations.
Reverse thus becomes pretty easy when using this looping.

201. Bitwise AND of Numbers Range

再来看一个范围[26, 30],它们的二进制如下:

11010  11011  11100  11101  11110

发现了规律后,我们只要写代码找到左边公共的部分即可,我们可以从建立一个32位都是1的mask,然后每次向左移一位,比较m和n是否相同,不同再继续左移一位,直至相同,然后把m和mask相与就是最终结果

231. Power of Two

这道题让我们判断一个数是否为2的次方数,而且要求时间和空间复杂度都为常数,那么对于这种玩数字的题,我们应该首先考虑位操作 Bit Operation。在LeetCode中,位操作的题有很多,比如比如Repeated DNA Sequences 求重复的DNA序列Single Number 单独的数字,  Single Number II 单独的数字之二 ,Grey Code 格雷码Reverse Bits 翻转位Bitwise AND of Numbers Range 数字范围位相与Number of 1 Bits 位1的个数和 Divide Two Integers 两数相除等等。那么我们来观察下2的次方数的二进制写法的特点:

1     2       4         8         16   ....

1    10    100    1000    10000 ....

那么我们很容易看出来2的次方数都只有一个1,剩下的都是0,所以我们的解题思路就有了,我们只要每次判断最低位是否为1,然后向右移位,最后统计1的个数即可判断是否是2的次方数,

260. Single Number III

整个算法的具体思路,假设数组中两个不同的数字为 A 和 B;

  1. 通过遍历整个数组并求整个数组所有数字之间的 XOR,根据 XOR 的特性可以得到最终的结果为 AXORB = A XOR B

  2. 通过某种特定的方式,我们可以通过 AXORB 得到在数字 A 和数字 B 的二进制下某一位不相同的位;因为A 和 B 是不相同的,所以他们的二进制数字有且至少有一位是不相同的。我们将这一位设置为 1,并将所有的其他位设置为 0,我们假设我们得到的这个数字为 bitFlag;

  3. 那么现在,我们很容易知道,数字 A 和 数字 B 中必然有一个数字与上 bitFlag 为 0;因为bitFlag 标志了数字 A 和数字 B 中的某一位不同,那么在数字 A 和 B 中的这一位必然是一个为 0,另一个为 1;而我们在 bitFlag 中将其他位都设置为 0,那么该位为 0 的数字与上 bitFlag 就等于 0,而该位为 1 的数字与上 bitFlag 就等于 bitFlag

  4. 现在问题就简单了,我们只需要在循环一次数组,将与上 bitFlag 为 0 的数字进行 XOR 运算,与上 bitFlag 不为 0 的数组进行独立的 XOR 运算。那么最后我们得到的这两个数字就是 A 和 B

vector<int> singleNumber(vector<int>& nums) {
  int AXORB = 0;
  for (int num : nums) {
    AXORB ^= num;
  }
  // pick one bit as flag
  int bitFlag = (AXORB & (~ (AXORB - 1)));
  vector<int> res(2, 0);
  for (int num : nums) {
    if ((num & bitFlag) == 0) {
      res[0] ^= num;
    } else {
      res[1] ^= num;
    }
  }
return res;
}