位图的原理及实现

我们可以使用boolean[] visited 这样的布尔数组，来记录已经被访问过的元素。

// 假设 nums 是一个包含 1000 个整数的数组
int[] nums = {...}

// 我们在写算法时
// 可能会用一个布尔数组来记录 nums 中那些元素已经被访问过
boolean[] visited = new boolean[nums.length];
visited[10] = true;
visited[100] = true;

但其实还是有更狠的优化方式，布尔类型我们都知道他是有false 和 true两种状态的。所以其实通过0和1就可以表示这两个意思，大部分的编程语言中在内存中一个布尔类型的值一般为一个字节（byte），也就是8 bit。所以，编程语言内置的布尔数组实际上只需要1/8的位置来达到这个visited数组的效果。所以我们优化的方式也就很明显了，通过比特位来表示是否访问过。

其实在实际算法题中，直接使用布尔数组就可以了，这种位图只是在一些特定的题目以及要求下才使用的一种结构，在处理超大规模的数据时可能才需要用到这个结构。

位图的原理和实现

我们可以使用long[] words来作为存储数组。就是把索引的方式更改一下。我们可以知道一个long类型的数据是8个字节，就是64bit （8*8），假设我们需要第135个比特位，那么：

1、目标比特位在words数组的第几个元素？ 135/64=2 所以在words[2]这个元素里。

2、在对应元素的第几个比特位呢？ 135%64 = 7，得到在第七位。

所以我们的目标比特位就在words[2]的元素里的第七个bite位。

你可以把它幻想成一个二维数组，每一行是一个元素，每个元素里有64个bite位，那这么看的话我们就 可以通过几个方法让用户可以访问这个对应bite位：

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

class MyBitSet {
private:
    // 使用 unsigned long 数组作为位图的底层存储
    vector<unsigned long long> words;
    // 位图能够存储的最大元素值 + 1
    int size;

public:
    MyBitSet(int size) : size(size) {
        // 根据 size 计算需要多少个 unsigned long long 来存储
        int arraySize = size / 64 + 1;
        words.resize(arraySize, 0);
    }

    // 判断指定比特位是否为 1
    bool get(int bitIndex) {
        if (bitIndex < 0 || bitIndex >= size) {
            throw out_of_range("bitIndex must be between 0 and " + to_string(size - 1));
        }
        // 找到 bitIndex 在 words 数组中的索引
        int wordIndex = bitIndex / 64;
        // 找到 bitIndex 在 unsigned long long 值中的具体 bit 位
        int bitOffset = bitIndex % 64;
        // 使用 & 操作判断该位是否为 1
        return (words[wordIndex] & (1ULL << bitOffset)) != 0;
    }

    // 将指定比特位设置为 1
    void set(int bitIndex) {
        if (bitIndex < 0 || bitIndex >= size) {
            throw out_of_range("bitIndex must be between 0 and " + to_string(size - 1));
        }
        // 找到 bitIndex 在 words 数组中的索引
        int wordIndex = bitIndex / 64;
        // 找到 bitIndex 在 unsigned long long 值中的具体 bit 位
        int bitOffset = bitIndex % 64;
        // 使用 | 操作将该位置 1
        words[wordIndex] |= (1ULL << bitOffset);
    }

    // 将指定比特位设置为 0
    void clear(int bitIndex) {
        if (bitIndex < 0 || bitIndex >= size) {
            throw out_of_range("bitIndex must be between 0 and " + to_string(size - 1));
        }
        int wordIndex = bitIndex / 64;
        int bitOffset = bitIndex % 64;
        // 使用 & 和 ~ 操作将该位置 0
        words[wordIndex] &= ~(1ULL << bitOffset);
    }
};

int main() {
    MyBitSet bitSet(1000);

    bitSet.set(10);
    bitSet.set(100);
    bitSet.set(500);

    cout << "Get 10: " << (bitSet.get(10) ? "true" : "false") << endl;     // true
    cout << "Get 100: " << (bitSet.get(100) ? "true" : "false") << endl;   // true
    cout << "Get 200: " << (bitSet.get(200) ? "true" : "false") << endl;   // false

    bitSet.clear(100);
    cout << "Get 100 after clear: " << (bitSet.get(100) ? "true" : "false") << endl; // false

    return 0;
}