Bitmap学习笔记

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

使用场景：快速查找，删除，判重。
基本思想：使用 bit 数组来表示某些元素是否存在。

问题1：某个文件包含一些电话号码，每个号码为8位数字，统计不同的号码的个数。
分析：
最小号码：00000000
最大号码：99999999
将每个电话号码映射到 bitmap 中不同的位置，将该位置设为1，否则为0。
总共有100,000,000（1亿）个电话号码，每个号码需要一位，即需要长度为1亿的 bitmap。
预估内存空间 100M bit ≈ 12.5M byte

如何申请12.5M的内存空间？
利用数组：int[] bitmap = new int[SIZE];
由于一个 int 占用 4 个字节，因此数组长度 SIZE = 12.5M / 4 = 3M = 3 * 1024 * 1024

如何将某一个号码 num 映射到特定的 bitmap 中特定的位：

• 电话号码00000000为最低位的标记，也就是0x0000.......000001。
• 电话号码00000001就应该是 0x0000.....0000010。
• 电话号码00000002就是0x0000....0000100。
  可以看出：电话号码就是1这个数字左移所对应的次数。

// 一个 int 占用 4 个字节，即 32 位。num / 32 可以得到该号码在 bitmap 中的下标位置
int pos = num / 32;

// 1这个数字左移所对应的次数
int mod = num % 32;
int mark = 1<<mod;

// 标记 bitmap 中特定的位置
bitmap[pos] = bitmap[pos] | mark

可以看出：

• 电话号码00000000对应的 pos = 0, mod = 0, mark = 1。
• 电话号码00000001对应的 pos = 0, mod = 1, mark = 10。
• 电话号码00000002对应的 pos = 0, mod = 2, mark = 100。

问题2：在2.5亿个整数中找出不重复的整数的个数。假设内存不足以同时容纳2.5亿个整数。

• 方案1：
  整数个数为 2^32，也就是，我们可以将这 2^32 个数，划分为 2^8 个区域（比如2^8 个文件），然后将数据分离到不同的区域，然后不同的区域在利用 bitmap 就可以直接解决了。
• 方案2：
  采用 2-bitmap，每个数分别 2 个bit，00 表示出现 0 次，01 表示出现 1 次，11 表示出现多次。
  需要内存 2.5 亿 * 2 = 5亿 bit = 0.5G bit = 0.07G byte = 70M。
  依次扫描2.5亿个整数：
  • 00 变 01
  • 01 变 11
  • 10 不变