STL bitset - 位运算优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 默认构造（全 0）
    bitset<8> b1;
    
    // 整数构造
    bitset<8> b2(42);  // 00101010
    
    // 字符串构造
    bitset<8> b3("10101010");
    
    // 拷贝构造
    bitset<8> b4(b2);
    
    // 移动构造
    bitset<8> b5(move(b4));
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    bitset<8> b;
    
    // 设置位
    b.set(0);     // 第0位设为1
    b.set(2, 1);  // 第2位设为1
    b.set();      // 所有位设为1
    
    // 清除位
    b.reset(0);   // 第0位设为0
    b.reset();    // 所有位设为0
    
    // 翻转位
    b.flip(1);    // 翻转第1位
    b.flip();     // 翻转所有位
    
    // 测试位
    bool is_set = b.test(0);
    bool any_set = b.any();    // 是否有位为1
    bool all_set = b.all();    // 是否所有位为1
    bool none_set = b.none();  // 是否所有位为0
    
    // 计数
    int count = b.count();  // 置位的位数
    
    // 大小
    size_t size = b.size();  // 总位数
    
    // 转换
    unsigned long ul = b.to_ulong();
    unsigned long long ull = b.to_ullong();
    string s = b.to_string();
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    bitset<4> a("1010");  // 10
    bitset<4> b("1100");  // 12
    
    // 按位与
    bitset<4> c = a & b;  // 1000 (8)
    
    // 按位或
    bitset<4> d = a | b;  // 1110 (14)
    
    // 按位异或
    bitset<4> e = a ^ b;  // 0110 (6)
    
    // 按位取反
    bitset<4> f = ~a;     // 0101 (5)
    
    // 左移
    bitset<4> g = a << 1;  // 0100 (4)
    
    // 右移
    bitset<4> h = a >> 1;  // 0101 (5)
    
    cout << "a: " << a << endl;
    cout << "b: " << b << endl;
    cout << "a & b: " << c << endl;
    cout << "a | b: " << d << endl;
    cout << "a ^ b: " << e << endl;
    cout << "~a: " << f << endl;
    cout << "a << 1: " << g << endl;
    cout << "a >> 1: " << h << endl;
    
    return 0;
}

1
2
3
4
5
6
7
8
9

bitset<8> a("10101010");
bitset<8> b("11001100");

// 复合赋值
a &= b;  // 等价于 a = a & b
a |= b;  // 等价于 a = a | b
a ^= b;  // 等价于 a = a ^ b
a <<= 2; // 等价于 a = a << 2
a >>= 2; // 等价于 a = a >> 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// 子集枚举
void enumerate_subsets(int n)
{
    for (int mask = 0; mask < (1 << n); mask++)
    {
        bitset<32> bits(mask);
        cout << "Mask " << mask << ": ";
        for (int i = 0; i < n; i++)
        {
            if (bits.test(i))
            {
                cout << i << " ";
            }
        }
        cout << endl;
    }
}

// 集合操作
bitset<100> set_union(const bitset<100>& a, const bitset<100>& b)
{
    return a | b;
}

bitset<100> set_intersection(const bitset<100>& a, const bitset<100>& b)
{
    return a & b;
}

bitset<100> set_difference(const bitset<100>& a, const bitset<100>& b)
{
    return a & ~b;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 位掩码表示方向
const int UP = 1 << 0;
const int DOWN = 1 << 1;
const int LEFT = 1 << 2;
const int RIGHT = 1 << 3;

// 检查是否可以移动
bool can_move(int directions, int dir)
{
    return (directions & dir) != 0;
}

// 添加方向
int add_direction(int directions, int dir)
{
    return directions | dir;
}

// 移除方向
int remove_direction(int directions, int dir)
{
    return directions & ~dir;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// 统计二进制中 1 的个数
int count_ones(int x)
{
    bitset<32> bits(x);
    return bits.count();
}

// 检查是否是 2 的幂
bool is_power_of_two(int x)
{
    if (x == 0)
    {
        return false;
    }
    bitset<32> bits(x);
    return bits.count() == 1;
}

// 查找最低位的 1
int find_lowest_set_bit(int x)
{
    bitset<32> bits(x);
    return bits._Find_first();
}

// 查找最高位的 1
int find_highest_set_bit(int x)
{
    bitset<32> bits(x);
    int pos = -1;
    for (int i = 31; i >= 0; i--)
    {
        if (bits.test(i))
        {
            pos = i;
            break;
        }
    }
    return pos;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// 旅行商问题 (TSP) 状态压缩 DP
int tsp(const vector<vector<int>>& dist)
{
    int n = dist.size();
    int full_mask = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    
    // 初始化：从各个城市出发
    for (int i = 0; i < n; i++)
    {
        dp[1 << i][i] = 0;
    }
    
    // 状态转移
    for (int mask = 0; mask < (1 << n); mask++)
    {
        for (int u = 0; u < n; u++)
        {
            if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX)
            {
                continue;
            }
            for (int v = 0; v < n; v++)
            {
                if (!(mask & (1 << v)) && dist[u][v] != INT_MAX)
                {
                    int new_mask = mask | (1 << v);
                    if (dp[new_mask][v] > dp[mask][u] + dist[u][v])
                    {
                        dp[new_mask][v] = dp[mask][u] + dist[u][v];
                    }
                }
            }
        }
    }
    
    // 找最小路径
    int result = INT_MAX;
    for (int i = 0; i < n; i++)
    {
        if (dp[full_mask][i] != INT_MAX)
        {
            result = min(result, dp[full_mask][i] + dist[i][0]);
        }
    }
    
    return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// 位图实现
class BitMap
{
private:
    bitset<1000000> bits;
public:
    void set(int x)
    {
        bits.set(x);
    }
    
    void clear(int x)
    {
        bits.reset(x);
    }
    
    bool test(int x)
    {
        return bits.test(x);
    }
    
    int count()
    {
        return bits.count();
    }
};

// 用于快速去重和存在性检查
void deduplicate(vector<int>& nums)
{
    bitset<1000000> seen;
    vector<int> result;
    
    for (int x : nums)
    {
        if (!seen.test(x))
        {
            seen.set(x);
            result.push_back(x);
        }
    }
    
    nums.swap(result);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    bitset<8> b("10101010");
    
    // 查找第一个置位的位
    size_t first = b._Find_first();
    cout << "第一个置位的位: " << first << endl;
    
    // 查找下一个置位的位
    size_t next = b._Find_next(first);
    cout << "下一个置位的位: " << next << endl;
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

// C++11 强类型枚举
enum class Direction : int
{
    UP = 1 << 0,
    DOWN = 1 << 1,
    LEFT = 1 << 2,
    RIGHT = 1 << 3
};

// 重载位运算符
Direction operator|(Direction a, Direction b)
{
    return static_cast<Direction>(static_cast<int>(a) | static_cast<int>(b));
}

Direction operator&(Direction a, Direction b)
{
    return static_cast<Direction>(static_cast<int>(a) & static_cast<int>(b));
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Direction dir = Direction::UP | Direction::RIGHT;
    bool can_go_up = (dir & Direction::UP) != static_cast<Direction>(0);
    cout << "Can go up: " << can_go_up << endl;
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 错误示范：使用循环进行位操作
int count_ones_slow(int x)
{
    int count = 0;
    while (x)
    {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

// 正确做法：使用 bitset
int count_ones_fast(int x)
{
    return bitset<32>(x).count();
}

// 更高效：使用内置函数
int count_ones_builtin(int x)
{
    return __builtin_popcount(x);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 错误示范：使用 vector<bool>
vector<bool> flags(1000000);  // 虽然节省空间，但访问慢

// 正确做法：使用 bitset
bitset<1000000> flags;  // 更高效的位操作

// 或者使用 bitset 数组处理更大的范围
const int MAX_SIZE = 10000000;
const int BITSET_SIZE = 1000000;
vector<bitset<BITSET_SIZE>> flags(MAX_SIZE / BITSET_SIZE + 1);

void set_bit(int x)
{
    int idx = x / BITSET_SIZE;
    int offset = x % BITSET_SIZE;
    flags[idx].set(offset);
}

bool test_bit(int x)
{
    int idx = x / BITSET_SIZE;
    int offset = x % BITSET_SIZE;
    return flags[idx].test(offset);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 利用位运算的短路特性
bool is_subset(bitset<32> a, bitset<32> b)
{
    // 检查 a 是否是 b 的子集
    return (a & b) == a;
}

// 快速计算交集大小
int intersection_size(bitset<100> a, bitset<100> b)
{
    return (a & b).count();
}

// 快速计算并集大小
int union_size(bitset<100> a, bitset<100> b)
{
    return (a | b).count();
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

// 子集枚举
void enumerate_subsets(int n)
{
    for (int mask = 0; mask < (1 << n); mask++)
    {
        bitset<32> bits(mask);
        cout << "Mask " << mask << ": ";
        for (int i = 0; i < n; i++)
        {
            if (bits.test(i))
            {
                cout << i << " ";
            }
        }
        cout << endl;
    }
}

// 快速统计二进制中 1 的个数
int count_ones(int x)
{
    return bitset<32>(x).count();
}

// 检查是否是 2 的幂
bool is_power_of_two(int x)
{
    if (x == 0)
    {
        return false;
    }
    return bitset<32>(x).count() == 1;
}

// 查找最低位的 1
int find_lowest_set_bit(int x)
{
    if (x == 0)
    {
        return -1;
    }
    bitset<32> bits(x);
    return bits._Find_first();
}

// 位图类
class BitMap
{
private:
    bitset<1000000> bits;
public:
    void set(int x)
    {
        bits.set(x);
    }
    
    void clear(int x)
    {
        bits.reset(x);
    }
    
    bool test(int x)
    {
        return bits.test(x);
    }
    
    int count()
    {
        return bits.count();
    }
};

// 旅行商问题 (TSP) 状态压缩 DP
int tsp(const vector<vector<int>>& dist)
{
    int n = dist.size();
    int full_mask = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    
    for (int i = 0; i < n; i++)
    {
        dp[1 << i][i] = 0;
    }
    
    for (int mask = 0; mask < (1 << n); mask++)
    {
        for (int u = 0; u < n; u++)
        {
            if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX)
            {
                continue;
            }
            for (int v = 0; v < n; v++)
            {
                if (!(mask & (1 << v)) && dist[u][v] != INT_MAX)
                {
                    int new_mask = mask | (1 << v);
                    if (dp[new_mask][v] > dp[mask][u] + dist[u][v])
                    {
                        dp[new_mask][v] = dp[mask][u] + dist[u][v];
                    }
                }
            }
        }
    }
    
    int result = INT_MAX;
    for (int i = 0; i < n; i++)
    {
        if (dp[full_mask][i] != INT_MAX)
        {
            result = min(result, dp[full_mask][i] + dist[i][0]);
        }
    }
    
    return result;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 测试子集枚举
    cout << "子集枚举 (n=3): " << endl;
    enumerate_subsets(3);
    
    // 测试位统计
    int x = 42;  // 101010
    cout << "\n二进制 " << bitset<8>(x) << " 中 1 的个数: " << count_ones(x) << endl;
    cout << "是否是 2 的幂: " << is_power_of_two(x) << endl;
    cout << "最低位的 1 的位置: " << find_lowest_set_bit(x) << endl;
    
    // 测试位图
    BitMap bm;
    bm.set(10);
    bm.set(20);
    bm.set(30);
    cout << "\n位图中 1 的个数: " << bm.count() << endl;
    cout << "测试位 10: " << bm.test(10) << endl;
    cout << "测试位 15: " << bm.test(15) << endl;
    
    // 测试 TSP
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    int tsp_result = tsp(dist);
    cout << "\nTSP 最短路径: " << tsp_result << endl;
    
    return 0;
}