目录

bitset的接口函数总览

bitset的实现

构造函数

操作函数set、reset、test、flip的实现

set函数的实现

reset函数的实现

flip函数的实现

test函数的实现

统计函数size、count的实现

size的实现

count的实现

判断函数any、none、all的实现

any函数的实现

none函数的实现

all函数的实现

---

bitset的接口函数总览

代码如下：

namespace xywl {
    template <size_t N>
    class bitset {
        public:
            // 构造函数
            bitset();
            // 反转
            void flip(size_t pos);
            // 设置
            void set(size_t pos);
            // 清空
            void reset(size_t pos);
            // 获取
            bool test(size_t pos);
            // 获取位数
            size_t size();
            // 获取1的位数
            size_t count();
            // 判断是不是所有的位都没被设置
            bool none();
            // 判断位图中是不是所有的位都是被设置的
            bool all();
            // 判断是不是有位图里面有1
            bool any();
        private:
            vector<int> _bits; 
    };
}

我们这里的实现是相对简单的，并没有将我们的所有功能都实现了，只是实现了部分重要的功能。

bitset的实现

构造函数

我们在构造对象的时候，需要给出我们的位数N，并且默认将我们的位都设置成0。

我们一般的实现是使用unsigned int来存，这样可以避免int带来的负数问题，我们的32位都可以使用，所以我们的位图使用的是vector容器存unsigned int来实现的，但是我们这里开出来的大小需要使用N / 32 + 1来计算，因为我们的N有可能不是32的整数倍。

比如下面的情况：

当我们申请的位数N是35的时候，我们就需要开出来两个unsigned int类型了。

代码如下：

bitset() {
    _bits.resize(N / 32 + 1, 0);
}

操作函数set、reset、test、flip的实现

set函数的实现

set使用来设置pos位置为1的。

实现的方式如下：

1、先要计算出来我们在你个unsigned int块，在计算在块里的那个位置。

2、将我们的1左移指定位置和目标或运算即可。

图示：

代码如下：

// 设置
void set(size_t pos) {
    assert(pos < N);
    // 算出是那个int块的
    int i = pos / 32;
    // 算出是块里面的那个位置
    int j = pos % 32;
    // 使用或操作来调整
    _bits[i] |= (1 << j);
}

reset函数的实现

我们reset函数的实习方式如下：

1、和之前的操作一样，计算出我们的位置。

2、将我们的1左移指定位置取反和目标与运算即可。

图示：

代码如下：

// 清空
void reset(size_t pos) {
    assert(pos < N);
    int i = pos / 32;
    int j = pos % 32;
    _bits[i] &= (~(1 << j));
}

flip函数的实现

我们实现的步骤如下：

1、先还是找到我们的位置。

2、将我们的1左移指定位置后和目标异或运算即可。

图示：

代码如下：

// 反转
void flip(size_t pos) {
    assert(pos < N);
    // 算出是那个int块的
    int i = pos / 32;
    // 算出是块里面的那个位置
    int j = pos % 32;
    // 使用异或操作来调整
    _bits[i] ^= (1 << j);
}

test函数的实现

实现的方式如下：

1、我们还是先要找到我们的位置。

2、将1左移指定位置的值和我们的目标值与运算返回即可。

代码如下：

// 获取
bool test(size_t pos) {
    assert(pos < N);
    int i = pos / 32;
    int j = pos % 32;
    return _bits[i] & (1 << j);
}

统计函数size、count的实现

size的实现

size就是用来返回我们的容量的也就是我们最开始传入的值了。

代码如下：

// 获取位数
size_t size() {
    return N;
}

count的实现

我们的count的实现就是用来获取图中被设置了1的位的个数。

我们这里要获取所有的被设置了的1，要遍历我们的vector容器中的所有的unsigned int块。

实现方法如下：

1、获取在vector容器中的值。

2、用一个临时的变量来存一下这个值，然后让它与上我们的1，判断是不是true，是的话就计数加加，不是或者操作完了之后我们的值右移一位。

代码如下：

// 获取1的位数
size_t count() {
    size_t temp = 0;
    for(auto& s : _bits) {
        int t = s;
        while(t) {
            if(t & 1) {
                temp++;
            }
            t = t >> 1;
        }
    }
}

判断函数any、none、all的实现

any函数的实现

any函数是用来判断位图中的位是不是有被设置过大于等于一次。

我们这里的实现逻辑如下：

遍历我们的vector容器，判断当前值是不是不是0，不是就直接返回true即可；要是是0，就继续，最后我们返回false即可。

代码如下：

bool any() {
    // 只要有一个有值就返回true
    for(auto& s : _bits) {
        if(s) {
            return true;
        }
    }
    return false;
}

none函数的实现

我们的none函数就是用来判断我们的所有的位是不是都没有被设置过。

实现逻辑如下：

我们可以直接复用我们的any函数，返回对于any函数的取反操作。

代码如下：

// 判断是不是所有的位都没被设置
bool none() {
    // 复用我们的any
    return !any();
}

all函数的实现

我们all函数就是为了判断我们的所有位是不是都被设置了，是就返回true，不是就返回false即可。

我们实现的逻辑如下：

1、先检查比较好检查的前面n - 1个unsigned int块是不是全是1，只需要判断取反之后是不是0即可。

2、再判断我们的最后一个unsigned int块的前面N % 32个比特位是不是全是1即可。

图示：

代码如下：

// 判断位图中是不是所有的位都是被设置的
bool all() {
    size_t n = _bits.size();
    // 先判断整块的，再判断零散的
    for(size_t i = 0; i < n - 1; i++) {
        if(~_bits[i] != 0) {
            return false;
        }
    }
    // 零散的
    for(size_t i = 0; i < N % 32; i++) {
        if((_bits[n - 1] & (1 << i)) == 0) {
            return false;
        }
    }
    return true;
}