🍻位运算🍻

转自：🔥【github】

只出现一次的数字

leetcode给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解题思路

  • 一种方法是先排序，因为两个相同的数一定在一起，两个数一起遍历，当发现不同的时候便找到结果
  • 当遍历到结尾时还没有发现则说明那一个数就出现在最后一位。
    cpp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0;  i + 2 < nums.size(); i+=2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.size()-1];
    }
  • 异或的性质：
  • 任何数和 0做异或运算，结果仍然是原来的数
  • 任何数和其自身做异或运算，结果是 0
  • 异或运算满足交换律和结合律，本题就是应用这一性质
    cpp
    1
    2
    3
    4
    5
    6
    7
    int singleNumber(vector<int>& nums) {
        int res = 0; 
        for (auto it : nums) {
            res ^= it;
        }
        return res;
    }

只出现一次的数字II

leetcode
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

解题思路

  • 位运算实在烧脑参考题解
  • 用哈希表还是香
  • 基本思想是，由于数字都是出现3次，所以这个数它的二进制任意位1的个数和都是3，当把所有的数字全部相加的和的二进制任意位1的个数一定是3的倍数，那么可以设计一种状态转换公式，使所有数字以二进制形式相加，各个位的1当出现第3次时变为0，这样最后剩下仍为1的位，就是只出现1次的数的二进制。
  • 但是二进制只能表达2中状态，所以需要2位二进制00-> 01-> 10 来表达任意位三种不同的状态。int数字有32位组成，所以需要两个整型变量one和two来状态转换。one表示1出现0次和1次，two表示1出现2次，因为出现第三次会变为0，所以最终的结果就是返回one

    异或运算：x ^ 0 = x​ ， x ^ 1 = ~x
    与运算：x & 0 = 0 ， x & 1 = x

    推导one的计算方式

    cpp
    1
    2
    3
    4
    5
    6
    7
    if two == 0:
      if n == 0:
        one = one
      if n == 1:
        one = ~one
    if two == 1:
        one = 0

通过异或运算简化

cpp
1
2
3
4
if two == 0:
    one = one ^ n
if two == 1:
    one = 0

与运算简化

cpp
1
one = one ^ n & ~two

代码

cpp
1
2
3
4
5
6
7
8
int singleNumber(vector<int>& nums) {
    int one = 0, two = 0;
    for (int num : nums) {
        one = ~two  & one ^ num);
        two = ~one  & two ^ num);
    }
    return one 
}

只出现一次的数字III

leetcode给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例

plaintext
1
2
输入: [1,2,1,3,2,5]
输出: [3,5]

解题思路

  • 全部异或就能得到只出现1次的数x和y的异或。然后想办法分离他俩。他俩异或的结果，任意位出现的1，这个1只属于是他俩的其中一个。所以在异或结果中，随便找一个为1的位就能区分他俩。
  • 所以通过 int diff = mask & (-mask);找到最右边的1那个位来区分他俩,
  • 依然对所有数字异或,但加了条件n & diff，这次只有那一位为1的数字才加入异或，通过这样就一定可以剔除掉另一个数字，
    cpp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    vector<int> singleNumber(vector<int>& nums) {
        int mask = 0;
        for (auto n : nums) {
            mask ^= n;
        }
        int diff = mask & (-mask);
        int x = 0;
        for (auto n : nums) {
            if (n & diff) {
                x ^= n;
            }
        }
        int y = mask ^ x;
        return {x, y};
    }

位1的个数

leetcode编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

解题思路

  • 方法一：定义掩码，逐位比较，掩码每次左移一位， mask <<= 1注意掩码必须使用无符号类型。
  • 方法二：或者原码每次右移一位，与1进行比较。
  • 方法三：每次反转原码的最后一位1，n &= (n - 1)，直到原码变为0，最后统计反转的次数
    cpp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int hammingWeight(uint32_t n) {
        uint32_t mask = 1;
        int cnt = 0;
        for (int i = 0; i < 32; ++i) {
            if (n & mask)  cnt++;
            mask <<= 1;
        }
        return cnt;
    }
    cpp
    1
    2
    3
    4
    5
    6
    7
    8
    int hammingWeight(uint32_t n) {
      int cnt = 0;
      while (n) {
          if (n & 1) cnt++;
          n >>= 1;
      }
      return cnt;
    }
    cpp
    1
    2
    3
    4
    5
    6
    7
    8
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while (n) {
            n &= n - 1;
            cnt++;
        }
        return cnt;
    }

比特位计数

leetcode给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例1

plaintext
1
2
输入: 2
输出: [0,1,1]

示例2

plaintext
1
2
输入: 5
输出: [0,1,1,2,1,2]

解题思路

  • 首先理解题意，返回的数组表示每个数字 i 的二进制数1的个数，数组大小一定是num+1,因为包含了数字0。
  • 奇数二进制表示最低位是1，偶数是0。
  • 奇数：二进制表示中，奇数一定比前面那个偶数多一个 1
  • 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多，因为偶数最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
  • 奇数偶数判断出了用 i % 2 == 0 还可以用i & 1 ==0来判断偶数。
    cpp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    vector<int> countBits(int num) {
        vector<int> dp(num + 1);
        dp[0] = 0;
        for (int i = 1; i <= num; i++) {
            if((i & 1) == 0) dp[i] = dp[i / 2];
            else dp[i] = dp[i - 1] + 1;
        }
        return dp;
    }

颠倒二进制位

leetcode颠倒给定的 32 位无符号整数的二进制位。

解题思路

  • 如果做过反转一个十进制数的题，这道题基本与之相似，反转十进制使用的算法是: 类似栈从后往前不断弹出数字，
    cpp
    1
    2
    3
    4
    5
    int rev = 0;
    while (n) {
        rev = rev * 10 + n % 10;
        n /=10;
    }
  • 而对于二进制数，实际上也可以,只是系数变为了2
    cpp
    1
    2
    3
    4
    5
    int rev = 0;
    while (n) {
        rev = rev * 2 + n % 2;
        n /=2;
    }
  • 但是需要考虑到整型溢出问题，还有二进制要考虑前导零的问题。所以我们可以替换为位操作。
    cpp
    1
    2
    3
    4
    5
    6
    7
    8
    uint32_t reverseBits(uint32_t n) {
        uint32_t rev = 0;
        for (int i = 0; i < 32; ++i) {
            rev = (rev << 1) + (n & 1);
            n >>= 1;
        }
        return rev;
    }