15、重载位运算符：重载&、|、^、~、<<、>>，实现位集合（bitset）类

位运算，说白了就是直接操作内存里的每一个比特位。很多刚入行的朋友觉得这东西离自己很远，其实不然。我在做网络协议栈的时候，一个数据包的状态标志位就靠它来搞定。你想想看，一个 uint32_t 就能存32个开关状态，省内存又高效，多划算。

今天我们就自己动手，写一个简单的位集合类，把 &、|、^、~、<<、>> 这些位运算符全给它重载一遍。嗯，这里要注意：重载不是炫技，是为了让代码读起来像自然语言。

为什么需要位集合？

标准库里其实有 std::bitset，但它的长度是编译期固定的。我当年做嵌入式项目时，需要动态大小的位图来标记内存块的使用情况。标准库帮不上忙，只能自己造轮子。

自己实现的好处很明显：

• 你可以控制底层存储（比如用 std::vector）
• 你可以添加自定义操作（比如统计连续0的个数）
• 你可以完全理解位运算的底层原理

基础框架：存储与构造

我们先搭个架子。底层用 std::vector，每个 uint64_t 存64个位。

#include <vector>
#include <cstdint>
#include <stdexcept>

class BitSet {
public:
    // 构造一个能容纳 n 个位的集合，默认所有位为 0
    explicit BitSet(size_t n)
        : bits_((n + 63) / 64, 0), size_(n) {}

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

    // 设置/获取某一位
    void set(size_t pos, bool val = true) {
        check(pos);
        if (val)
            bits_[word_index(pos)] |= (1ULL << bit_offset(pos));
        else
            bits_[word_index(pos)] &= ~(1ULL << bit_offset(pos));
    }

    bool test(size_t pos) const {
        check(pos);
        return (bits_[word_index(pos)] >> bit_offset(pos)) & 1;
    }

private:
    std::vector<uint64_t> bits_;
    size_t size_;

    size_t word_index(size_t pos) const { return pos / 64; }
    size_t bit_offset(size_t pos) const { return pos % 64; }

    void check(size_t pos) const {
        if (pos >= size_)
            throw std::out_of_range("BitSet index out of range");
    }
};

这段代码里，word_index 和 bit_offset 是两个辅助函数。我个人习惯把它们写成内联的，因为位运算操作本身就很频繁，函数调用开销能省则省。

重载位运算符：&、|、^、~

这些运算符的语义很直观：对两个位集合的对应位做逻辑运算。注意，两个集合的长度必须一致，否则没法做。

BitSet operator&(const BitSet& other) const {
    check_size_match(other);
    BitSet result(size_);
    for (size_t i = 0; i < bits_.size(); ++i)
        result.bits_[i] = bits_[i] & other.bits_[i];
    return result;
}

BitSet operator|(const BitSet& other) const {
    check_size_match(other);
    BitSet result(size_);
    for (size_t i = 0; i < bits_.size(); ++i)
        result.bits_[i] = bits_[i] | other.bits_[i];
    return result;
}

BitSet operator^(const BitSet& other) const {
    check_size_match(other);
    BitSet result(size_);
    for (size_t i = 0; i < bits_.size(); ++i)
        result.bits_[i] = bits_[i] ^ other.bits_[i];
    return result;
}

BitSet operator~() const {
    BitSet result(size_);
    for (size_t i = 0; i < bits_.size(); ++i)
        result.bits_[i] = ~bits_[i];
    // 注意：取反后，超出 size_ 的高位可能被置1，需要掩码清除
    if (size_ % 64 != 0) {
        size_t last = bits_.size() - 1;
        size_t shift = 64 - (size_ % 64);
        result.bits_[last] &= ~((1ULL << shift) - 1);
    }
    return result;
}

这里有个细节：~ 操作符取反后，最后一个 uint64_t 里超出实际位数的那些高位会被置1。如果不处理，后续做 & 运算时会得到错误结果。我刚开始写的时候漏了这一步，调试了半小时才发现。

重载移位运算符：<< 和 >>

移位操作在位集合里意味着整体左移或右移。比如左移3位，所有位都往高位方向移动3格，低位补0。

实现起来比想象中复杂一点，因为要跨 uint64_t 边界搬运数据。

BitSet operator<<(size_t shift) const {
    BitSet result(size_);
    if (shift >= size_) return result;  // 全部移出

    size_t word_shift = shift / 64;
    size_t bit_shift  = shift % 64;

    for (size_t i = 0; i < bits_.size(); ++i) {
        uint64_t val = 0;
        // 从源位置取数据
        if (i >= word_shift)
            val |= bits_[i - word_shift] << bit_shift;
        if (bit_shift != 0 && i > word_shift)
            val |= bits_[i - word_shift - 1] >> (64 - bit_shift);
        result.bits_[i] = val;
    }

    // 清除尾部高位
    if (size_ % 64 != 0) {
        size_t last = bits_.size() - 1;
        size_t shift = 64 - (size_ % 64);
        result.bits_[last] &= ~((1ULL << shift) - 1);
    }
    return result;
}

BitSet operator>>(size_t shift) const {
    BitSet result(size_);
    if (shift >= size_) return result;

    size_t word_shift = shift / 64;
    size_t bit_shift  = shift % 64;

    for (size_t i = 0; i < bits_.size(); ++i) {
        uint64_t val = 0;
        if (i + word_shift < bits_.size())
            val |= bits_[i + word_shift] >> bit_shift;
        if (bit_shift != 0 && i + word_shift + 1 < bits_.size())
            val |= bits_[i + word_shift + 1] << (64 - bit_shift);
        result.bits_[i] = val;
    }
    return result;
}

这段代码的核心逻辑是：先算跨了几个 uint64_t（word_shift），再算内部偏移（bit_shift）。然后从源数组里「拼」出目标值。说白了就是手工模拟一个超大整数的移位。

知识体系总览

下面这张图把本章的核心知识点串起来了。你可以看到，位集合的底层是数组，上层通过重载运算符提供类整数的操作体验。

完整示例：把位集合用起来

光说不练假把式。我们写个 main 函数，看看这些运算符到底好不好用。

#include <iostream>

int main() {
    BitSet a(16), b(16);
    
    a.set(0); a.set(2); a.set(4);  // 二进制：...00010101
    b.set(1); b.set(2); b.set(3);  // 二进制：...00001110
    
    BitSet c = a & b;  // 只有第2位同时为1
    BitSet d = a | b;  // 第0~4位全为1
    BitSet e = a ^ b;  // 第0,1,3,4位为1
    BitSet f = ~a;     // 除了0,2,4位，其余全为1（注意高位掩码）
    
    BitSet g = a << 3; // 左移3位，第3,5,7位为1
    BitSet h = a >> 1; // 右移1位，第0,1,3位为1
    
    std::cout << "a & b 的第2位: " << c.test(2) << "\n";
    std::cout << "a | b 的第0位: " << d.test(0) << "\n";
    std::cout << "a << 3 的第5位: " << g.test(5) << "\n";
    
    return 0;
}

输出结果应该全是 1。如果你跑出来有 0，八成是尾部掩码没处理好。嗯，我当年第一次跑这个测试时，~a 的结果就多出来几个奇怪的1，排查了半天才发现是最后一个 uint64_t 的高位没清掉。

避坑指南

最后总结几个我踩过的坑，你写的时候留个心眼：

• 移位运算符的优先级：a << 3 & b 会被解析成 (a << 3) & b 还是 a << (3 & b)？答案是前者。但为了代码可读性，我建议永远加括号。
• 复合赋值运算符：如果实现了 operator&，别忘了实现 operator&=。用户会期望 a &= b 也能用。
• const 正确性：所有不修改对象的成员函数都要加 const。我见过太多人漏掉这个，导致无法在 const 对象上调用 test()。
• 异常安全：如果 operator& 里 new 分配内存失败，要保证不会泄露。用 std::vector 已经帮你处理好了，但如果你自己管理内存，一定要小心。

---

公众号：蓝海资料掘金营，微信 deep3321