C++ 位圖去重排序：自定義 Bitset 實現 O(N) 時間 O(1) 空間

背景

對於已知範圍（如 0~600）的整數去重並升序輸出，位圖是極佳選擇：時間 O(N+M)，空間 O(M/32)。本文展示一個模板化的 Bitset 實現。

核心設計

• 以 long（32 位）為存儲單元，數組大小 _W = (_N-1)/32 + 1。
• 提供 set(pos) 置位、test(pos) 測試、printf() 遍歷輸出所有置位下標。

完整代碼

#include <iostream>
using namespace std;

template <int _N>
class Bitset {
    static const int _W = (_N - 1) / 32 + 1;
    long A[_W] = {0};
public:
    void set(int pos) {
        A[pos / 32] |= (1L << (pos % 32));
    }
    bool test(int pos) const {
        return (A[pos / 32] >> (pos % 32)) & 1L;
    }
    void printf() const {
        for (int i = 0; i < _N; ++i)
            if (test(i)) cout << i << ' ';
    }
};

int main() {
    Bitset<600> bs;
    int data[] = {1,1,1,1,2,2,3,3,34,2,423,42,34,23,1,1,3,213,123,21,3,3,4,32,543,5,46,3,45,35,23,42,3};
    for (int x : data) bs.set(x);
    bs.printf(); // 輸出: 1 2 3 4 5 21 23 32 34 35 42 45 46 123 213 423 543
    return 0;
}

優勢分析

當最大值 ≤ 10⁷ 時，Bitset 通常是最快且最省內存的方案。