########################################
位运算
########################################

一般而言，编程语言中提供了六种位运算：与、或、异或、左移、右移和取反。有以下几个简单结论：

- A 对 B 异或两次得到的依然是 A
- A 异或 A 得到零
- 左移 x 位相当于乘以 2 的 x 次幂
- 右移 x 位相当于除以 2 的 x 次幂
- 获取第 n 位：

   .. code-block:: cpp

      int getBit(int a, int n){
         return (a >> n)&1;
      }

- 设置第 n 位为零：

   .. code-block:: cpp

      int unsetBit(int a, int n){
         return a &~(1 << n);
      }

- 设置第 n 位为 1：

   .. code-block:: cpp

      int setBit(int a, int n){
         return a | (1 << n);
      }

- 将第 n 位取反：

   .. code-block:: cpp

      int flapBit(int a, int b){
         return a ^ (1 << n);
      }

从上面也可以看到 | 用于打开位，&~ 用于关闭位

位图
****************************************

.. admonition:: 摘自《编程珠玑（第二版）》P7

   该数据结构描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有其它任何数据与该元素相关联。即使这些条件没有完全满足，也可以用有限定义域内的键作为一个更复杂的表格的索引

位图或者位向量是一种节省内存的数据结构，位图相比位向量显著的特点是不再要求内存连续。在《编程珠玑》第一章就介绍了使用位图排序的一个例子。

这里有两个深信服面试时的题目：

- 一亿范围、一千万数字中节省内存地查找某一个数字

   设置一个一亿比特大小的位图，并将所有位置零。然后对这一千万数字进行一次遍历，并将所有出现的数字的相关位置 1。然后直接输出目的数字相关位是否为 1 即可

- 一亿数字进行节省内存地排序，要求预处理后时间复杂度为 :math:`O(n)`

   设置一个一亿比特大小的位图，并将所有位置零。然后对这一亿数字进行一次遍历，并将所有出现的数字的相关位置 1。之后从第一位开始检查位，将位为 1 的位输出即完成了排序

有时候我们需要对位图进行泛化，例如：

448. 找到所有数组中消失的数字 [#missnum]_

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

使用位图的话时间复杂度可以达到 O(n)，但是空间复杂度达不到题意：

.. code-block:: c++

   class Solution {
   public:
      vector<int> findDisappearedNumbers(vector<int>& nums) {
         int n = nums.size();
         // bitmap 初始化
         char* bitmap = new char[n + 1];
         for(int i = 1; i <= n; ++i){
               bitmap[i] = 0;
         }
         //
         for(auto i : nums){
               bitmap[i] = 1;
         }
         vector<int> res;
         for(int i = 1; i <= n; ++i){
               if(bitmap[i] == 0)
                  res.push_back(i);
         }
         return res;
      }
   };

我们可以将位图进行泛化，不再使用 0/1 判断，而是以正负判断。

对原数组进行一次遍历，将 nums[i] 对应的位设置为负数，那么最后留下的为正数的位置就是缺失的数字：

.. code-block:: c++

   class Solution {
   public:
      vector<int> findDisappearedNumbers(vector<int>& nums) {
         int n = nums.size();
         // bitmap 初始化
         for(int i = 0; i < n; ++i){
               int val = abs(nums[i]) - 1;
               nums[val] = -abs(nums[val]);
         }
         vector<int> res;
         for(int i = 0; i < n; ++i){
               if(nums[i] > 0) res.push_back(i+1);
         }
         return res;
      }
   };

.. [#missnum] `找到所有数组中消失的数字 <https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array>`_