位图（Bitmap）是一种高效的，使用位来记录数据的结构，多用于存储和操作大量布尔值（通常是true或false）。位图通过使用位（bit）来表示布尔值，从而节省存储空间并提高操作效率。位（Bit）：位是计算机中最小的数据单位，可以是0或1。一个字节（byte）包含8个位。

位图怎么用？

假设我们要存储一个数组：5，1，7，15，0，4，6，10。怎么存储这个数组？

数组有8个数字，Java中常用的办法，List，在声明固定长度的时候，不算一个List本身的存储开销，至少需要8个int的存储空间。Integer是4个byte，此时需要32个字节。即便用byte，每个byte需要1个字节，此时仍需要8个字节，而且byte表达的范围太小，很多实际场景中不够用。如果用Integer存储，数组的长度是N，那么需要4N字节。

如果我要存储1000千万个数据呢，那就需要4000千万byte，4000万byte=4000*1000*10000/1024/1024/1024 G，大概是38G，超过很多小伙伴的笔记本电脑内存了。有没有省空间的存储方式？有，就是位图。

用位数组的序号表达实际值是否存在。如图我们把5，1，7，15，0，4，6，10对应序号的位置为1，那么就得到了一个1100-1111-0010-0001的位数组。

位图的真实场景？

1. 文件系统中的空闲块管理。文件系统需要高效地管理磁盘空间，知道哪些磁盘块是空闲的，哪些已被占用。使用位图来表示每个磁盘块的状态。每一位对应一个磁盘块，1 表示已被占用，0 表示空闲。通过位图，文件系统可以快速定位空闲块，减少搜索时间，提升存储管理效率。
2. 操作系统的内存管理。操作系统需要管理内存的分配和回收，跟踪哪些内存页是空闲的。使用位图记录每个内存页的状态，1 表示已被分配，0 表示空闲。位图提供了一种紧凑且高效的方式来管理内存，有助于优化内存使用，减少碎片化。
3. 数据库索引。数据库需要快速定位数据记录，提升查询性能。使用位图索引，每个位代表一条记录是否存在某个特定的属性值。例如，位图可以用于记录某个字段的值是否存在于特定范围。位图索引占用空间小，查询速度快，特别适用于需要频繁查询和过滤的场景。
4. 图形处理与计算机视觉。图像处理和计算机视觉中，需要高效地表示和操作图像数据。使用位图来表示图像的像素信息，每个位或字节代表一个像素的颜色或亮度。位图提供了紧凑的存储方式，便于进行图像压缩、处理和传输。
5. 分布式系统中的状态协调。分布式系统需要协调多个节点的状态，确保一致性。使用位图来表示各个节点的状态，例如是否已参与某个任务或是否可用。位图提供了一种高效的方式来同步节点状态，减少通信开销，提升系统的可用性和一致性。
6. 用户的关注列表。如抖音、头条等等用户关注列表，微信的好友关系。用位图存储关系列表十分节省存储空间，而且能快速判断用户B是否关注用户A。
7. 商品的库存状态。电商平台的商品库存状态可以使用位图来存储，0表示缺货，1表示有货。

代码实现

位图是非常常见的，其代码实现如下：

public class Bitmap {
    private byte[] bits;
    private int size;

    // 构造函数，指定位图大小（比特位数量）
    public Bitmap(int size) {
        this.size = size;
        this.bits = new byte[(size + 7) / 8]; // 1 byte = 8 bits
    }

    // 设置某一位为1
    public void set(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        bits[index / 8] |= (1 << (index % 8));
    }

    // 清除某一位，将其设置为0
    public void clear(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        bits[index / 8] &= ~(1 << (index % 8));
    }

    // 检查某一位是否为1
    public boolean get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        return (bits[index / 8] & (1 << (index % 8))) != 0;
    }

    // 获取位图的大小（比特位数量）
    public int getSize() {
        return size;
    }

    public static void main(String[] args) {
        Bitmap bitmap = new Bitmap(16); // 创建一个大小为16位的位图

        bitmap.set(3); // 将第3位设置为1
        bitmap.set(7); // 将第7位设置为1

        System.out.println(bitmap.get(3)); // 输出 true
        System.out.println(bitmap.get(7)); // 输出 true
        System.out.println(bitmap.get(4)); // 输出 false

        bitmap.clear(3); // 将第3位设置为0
        System.out.println(bitmap.get(3)); // 输出 false
    }
}

构造函数

BitMap的成员变量之一是int size，表示能存储的数据量。一般情况下数据最大值＝数据量，但也需要辩证的理解。假设size=100，那么表示0-100都有可能出现，每一个出现的概率是均等的，这种时候数据量才等于最大值。假设我们要存储0-100之间的偶数，那么最大值≠数据量，数据量理论值＝最大值/2。

BitMap的成员变量之二是byte[] bits，字节数组，表示真实存储的数据。注意1个byte有8个位，每个位可以是0或者1。那么一个byte可以存储0000-1111或者0101-1100这种数据。

注意byte最大值为0111-1111=127，最小值为1000-000=-127。

bits数组初始化为（size+7）/8。为什么是这个大小？

前文讲过位图存储数据，使用位数组的序号进行存储的，假设需要存储11个数据，就需要11位；假设11个数据都存在，那么位数组表达为111-1111-1111。位数组在代码里表达为字节数组，1个字节=8位，就是说每个字节能存储8个数据。11个数据，1个字节肯定少了，1个字节只有8为，只能存储8个数据，11个数据需要2个字节，然后11个数据用不完两个字节（剩余5位）。11个数据都存在的情况下，位数组表达为：0000-0111-1111-1111。所以字节数组大小，可以表述为：需要存储的数据量，除以8，然后向上取整。

至于为什么（size+7）/8用来初始化数组，在Java运算中，除法是自动向下取整的，（size+7）/8等价于size/8 向上取整。

set方法（或）

方法set用于设置某一值，操作体现在设置对应位为1。

这段方法中，13-15行很好理解，13行做了一个index取值范围的防御性编程的判断，如果设值非法就抛出异常。16行bits[index / 8] |= (1 << (index % 8))不好理解，我们慢慢分析。

假设我们初始化了一个2个字节的位数组，0000-0000-0000-0000，现在要将13设置为1，也就是结果为：0010-0000-0000-0000。

但是我们实际操作的是字节数组，1个字节=8位，所以我们需要先定位到变动的字节。index在0-7，操作的是bits[0]，此时bits[1]是没有变动的;index在8-15操作的是bit[1],此时bits[0]是没有变动的；往下推理，可以得出，设置index，操作的是bits[index/8]。

在index=13时，我们操作的是bits[1]，而且操作的是第5位。1个byte是8位，此时我们需要知道操作的是多少位，在1个字节内，操作的位数总是在1-8之间，通过观察很容易得出操作的位数等于index对8取余，即=index%8，13%8=5。将bits[1]表达的位数组第5位设置成1。

设置第index位为1，等价于bits[index/8]的位数组的index%8位设置成1，那么这个运算怎么实现？

注意 1 << (index % 8）在index=13的时候，表示1左移5位。1=0000-0001，左移5位得到0010-0000。然后|=是一个复合运算符，复合了或运算及等于运算，a|=b等价于a=a|b，或运算很好理解，a和b相同位置有一个1，最终位就是1。

再来看 bits[index / 8] |= (1 << (index % 8)) ， 其实可以表达为 bits[index / 8] =bits[index / 8] | (1 << (index % 8))。这个二进制运算，设置index时，操作bits[index / 8]，构造一个1 << (index % 8)的二进制数，这个二进制数将对8取余的位置设置成1，其他位是0。然后进行或运算，达到将 bits[index / 8] 的 index % 8 位设置成1的效果。总结set运算

1. 定位字节数组 bits[index / 8] 节点N
2. 定位节点N操作的位 index % 8 ，位置p
3. 得到中间操作二进制1 << (index % 8)，该二进制数为Q（8位，位置p位1，其他为0）
4. N 和 Q 做或运算，结果写入N

set方法很重要，理解了set方法，后面的clear，get方法很好理解。

get方法（与）

方法get用户获取某一值，操作体现在查看对应位是否为1。

对于get(index)，判断第index位是0还是1，按照上文set方法的思路，我们知道需要定位的是bits[index/8]的第index%8位的值。

1<<(index%8）左移运算，可以用一个第index%8位为1，其他位为0的一个8位数组，如index=13，得到0010-0000。

在此基础上，理解bits[index/8] &（1<<(index%8）)，&是与运算，两者都为1，结果就为1，否则为0。1&1=1，0&0=0，1&0=0，0&1=0。1<<(index%8）表示除了第index%8位，其他都是0，所以这个结果除了第index%8位，其他位肯定是0。第index%8位还是1，取决于bits[index/8]的第index%8是0还是1。假设index=13，bits[index/8]的第index%8是0，整体结果就是0000-0000；bits[index/8]的第index%8是1，整体结果为0010-0000。

clear方法（与非）

方法clear与方法set作用相反，用于设置某一值所处位为0。

设置index位为0，代表操作bits[index/8]的第index%8位为0。上述代码怎么操作的呢？

1. 1<<(index%8）除了第index%8位是1，其他都是0。
2. ~（1<<(index%8）)表示非，即反过来，1变成0，0变成1，即除了第index%8位是0，其他都是1。假如index=13，那么~（1<<(index%8）)表示为：1101-1111
3. bits[index / 8] &= ~(1 << (index % 8))即将原来的bits[index/8]与第2步的结果做与操作。第2步的结果：第index%8位是0，其他都是1。那么可以得出，bits[index/8]的第index%8位将变成0，其他位不变（1&1=1,1&0=0）。

小结

位图的代码看起来比一般的要难懂一些，现在使用二进制操作符的程序员还是不多，看不懂很正常，没看懂的时候，就写几个二进制的例子，逐步推理，慢慢就能明白。

掌握位图，首先掌握其基本原理：用位记录数据的状态；使用场景：批量数据状态管理（内存管理、磁盘管理等）。

其次要掌握其实现框架：set（或）、get（与）、clear（与非）3个方法，以及如何定位到index数据到bits[]，如何操作index所对应的位数据。

最后列几个问题，大家可以对照看看是否能流畅回答

1. 讲述一下bitmap的基本原理和使用场景
2. 手写一下bitmap的set方法的实现
3. 手写一下bitmap的clear方法的实现
4. 手写一下bitmap的get方法的实现
5. 解释一下 1<< (index%8)
6. 解释一下二进制操作符 | & ~ << >>