:::info 这里所说的位图并不是像素图片的位图，而是内存中连续的二进制位（bit）所组成的数据结构，该算法主要用于对大量整数做去重和查询操作。 :::

    举个例子，假设给出一块长度为10bit的内存空间，也就是Bitmap，想要依次插入整数4、2、1、3，需要怎么做呢？
    很简单，具体做法如下。
    第1步，给出一块长度为10的Bitmap，其中的每一个bit位分别对应着从0到9的整型数。此时，Bitmap的所有位都是0（用紫色表示）。
    image.png
    第2步，把整型数4存入Bitmap，对应存储的位置就是下标为4的位置，将此bit设置为1（用黄色表示）。
    image.png
    第3步，把整型数2存入Bitmap，对应存储的位置就是下标为2的位置，将此bit设置为1。
    image.png
    第4步，把整型数1存入Bitmap，对应存储的位置就是下标为1的位置，将此bit设置为1。
    image.png
    第5步，把整型数3存入Bitmap，对应存储的位置就是下标为3的位置，将此bit设置为1。
    image.png
    如果问此时Bitmap里存储了哪些元素。显然是4、3、2、1，一目了然。Bitmap不仅方便查询，还可以去掉重复的整数。

    为了帮助公司精准定位用户群体，咱们需要开发一个用户画像系统，实现用户信息的标签化。
    用户标签包括用户的社会属性、生活习惯、消费行为等信息，例如下面这个样子。
    image.png

    为了满足用户标签的统计需求，利用关系型数据库设计了如下的表结构，每一个维度的标签对应着数据库表中的一列。
    image.png
    我们现在可以使用 SQL 来查询需要的数据，但是当数据量变大以后，性能会越来越差。

    我们可以对表进行修改，从之前的以用户为中心变成以标签为中心，让每一个标签存储包含此标签的所有用户ID，就像倒排索引一样。
    第1步，建立用户名和用户ID的映射。
    image.png
    第2步，让每一个标签存储包含此标签的所有用户ID，每一个标签都是一个独立的Bitmap。
    image.png
    这样一来，每一个用户特征都变得一目了然。
    例如程序员和“00后”这两个群体，各自的Bitmap分别如下。
    image.png
    不仅如此，Bitmap在对用户群做交集和并集运算时也有极大的便利。我们来看看下面的例子。

    1. 如何查找使用苹果手机的程序员用户

    image.png

    1. 如何查找所有男性用户或“00后”用户

    image.png
    这就是Bitmap算法的另一个优势——高性能的位运算。
    如何利用Bitmap实现反向匹配呢？例如我想查找非“90后”的用户 ，如果简单地做取反运算操作，会出现问题。
    会出现什么问题呢？我们来看一看。
    “90后”用户的Bitmap如下。
    image.png
    如果想得到非“90后” 的用户，能够直接进行非运算吗？
    image.png
    显然，非“90后”用户实际上只有1个，而不是图中所得到的8个结果，所以不能直接进行非运算。
    这个问题提得很好，但是也不难解决，我们可以借助一个全量的Bitmap。
    同样是刚才的例子，我们给出“90后”用户的Bitmap，再给出一个全量用户的Bitmap。最终要求出的是存在于全量用户，但又不存在于“90后”用户的部分。
    image.png
    如何求出这部分用户呢？我们可以使用异或 运算进行操作，即相同位为0，不同位为1。
    image.png

    1. public class Bitmap {
    3.     // 每一个 word 是一个 long 类型元素，对应一个 64 位二进制数据
    4.     private long[] words;
    5.     // Bitmap 的位数大小
    6.     private int size;
    8.     public Bitmap(int size) {
    9.         this.size = size;
    10.         this.words = new long[(getWordIndex(size - 1) + 1)];
    11.     }
    13.     // 判断 Bitmap 某一位的状态
    14.     public boolean getBit(int bitIndex) {
    15.         if (bitIndex < 0 || bitIndex > size - 1) {
    16.             throw new IndexOutOfBoundsException("超过 Bitmap 有效范围");
    17.         }
    18.         int wordIndex = getWordIndex(bitIndex);
    19.         return (words[wordIndex] & (1L << bitIndex)) != 0;
    20.     }
    22.     // 把 Bitmap 某一位设置为 True
    23.     public void setBit(int bitIndex) {
    24.         if (bitIndex < 0 || bitIndex > size - 1) {
    25.             throw new IndexOutOfBoundsException("超过 Bitmap 有效范围");
    26.         }
    27.         int wordIndex = getWordIndex(bitIndex);
    28.         words[wordIndex] |= (1L << bitIndex);
    29.     }
    31.     // 定位 Bitmap 某一位所对应的 word
    32.     private int getWordIndex(int bitIndex) {
    33.         // 右移 6 位，相当于除以 64
    34.         return bitIndex >> 6;
    35.     }
    37.     public static void main(String[] args) {
    38.         Bitmap bitmap = new Bitmap(128);
    39.         bitmap.setBit(126);
    40.         bitmap.setBit(75);
    41.         System.out.println(bitmap.getBit(126));
    42.         System.out.println(bitmap.getBit(78));
    43.     }
    44. }

    在上述代码中，使用一个命名为words的long类型数组来存储所有的二进制位。每一个long元素占用其中的64位。
    如果要把Bitmap的某一位设为1，需要经过两步。

    1. 定位到words中的对应的long元素。
    2. 通过与运算修改long元素的值。

    如果要查看Bitmap的某一位是否为1，也需要经过两步。

    1. 定位到words中的对应的long元素。
    2. 判断long元素的对应的二进制位是否为1。

    深入研究Bitmap算法的读者，可以看一下JDK中BitSet类的源码。