自定义Bitmap

使用场景

Bitmap 是一种使用位数组（bit array）来表示数据的结构，每一位（bit）表示一个值的状态。由于每个位只占用 1 bit，因此Bitmap 的存储效率非常高，特别适用于大数据去重、标记布尔值状态、稀疏数据存储等场景。

含义

Bitmap 的核心思想是用位（bit）来标记状态。
假设我们有一个整数数组需要存储 0 到 N-1 的数字，我们可以用位图来表示这些数字是否存在：
第 0 位表示数字 0 是否存在
第 1 位表示数字 1 是否存在
第 N 位表示数字 N 是否存在

前置知识

我们先来看看Java中的基本数据类型占用的字节数量

实现

public class Bitmap {
    private final byte[] bits;


    public Bitmap(int size) {
        bits = new byte[(size + 7) / 8];
    }

    // 设置第pos位为1
    public void set(int pos) {
        int index = pos / 8;           // 找到对应的byte索引
        int offset = pos % 8;          // 找到byte内的位偏移
        bits[index] |=  (1 << offset);  // 设置对应位为1
    }

    // 清除第pos位为0
    public void clear(int pos) {
        int index = pos / 8;           // 找到对应的byte索引
        int offset = pos % 8;          // 找到byte内的位偏移
        bits[index] &=  ~(1 << offset); // 将对应位清0
    }

    // 检查第pos位是否为1
    public boolean get(int pos) {
        int index = pos / 8;           // 找到对应的byte索引
        int offset = pos % 8;          // 找到byte内的位偏移
        return (bits[index] & (1 << offset)) != 0;
    }

    // 打印Bitmap的内容
    public void print() {
        for (int i = 0; i < bits.length; i++) {
            // 打印二进制字符串，前面补足 0
            String binaryString = String.format("%8s", Integer.toBinaryString(bits[i] & 0xFF)).replace(' ', '0');
            System.out.print(binaryString + " ");
        }
        System.out.println();
    }

测试

public class TestBitmap {
    @Test
    public void test() {

        Bitmap bitmap = new Bitmap(64);
        System.out.println("init:");
        bitmap.print();

        // 设置位
        bitmap.set(0);
        bitmap.set(10);
        bitmap.set(63);

        // 打印Bitmap
        System.out.println("After setting bits:");
        bitmap.print();

        // 清除位
        bitmap.clear(10);
        System.out.println("After clearing bit 10:");
        bitmap.print();

        // 检查位
        System.out.println("Is bit 0 set? " + bitmap.get(0));
        System.out.println("Is bit 10 set? " + bitmap.get(10));
        System.out.println("Is bit 63 set? " + bitmap.get(63));
    }
}