当前位置：首页 > news >正文

【数据结构中的位运算】

news 2025/7/1 5:41:48

文章目录

前言
一、位运算是什么？
二、使用步骤
- 1. 引入库
- 2. 常用位运算示例
- - 2.1 奇偶判断
  - 2.2 翻转所有位
  - 2.3 交换两个整数（无临时变量）
  - 2.4 获取最低位的 1
  - 2.5 判断是否为 2 的幂
三、位运算在数据结构中的应用
- 1. 位图（Bitset）
- 2. 二进制索引树（Fenwick Tree）
总结

前言

在高性能算法与数据结构的设计中，位运算（Bitwise Operation）以其极低的时间常数和高效的空间利用，成为优化的利器。

一、位运算是什么？

位运算是直接对整数在 二进制位 级别进行的运算，常见操作符有：

&（按位与）
|（按位或）
^（按位异或）
~（按位取反）
<<（左移）
>>（右移）

与普通算术运算相比，位运算通常在 CPU 指令层面一条即可完成，性能极高。

二、使用步骤

1. 引入库

#include <iostream>
#include <bitset>   // 位图支持
#include <vector>
using namespace std;

2. 常用位运算示例

2.1 奇偶判断

如果 n & 1 == 0，则 n 为偶数；否则为奇数。

int n = 42;
if ( (n & 1) == 0 )cout << n << " 是偶数\n";
elsecout << n << " 是奇数\n";

2.2 翻转所有位

~n 对 n 的每一位取反（注意符号位）。

int n = 5;          // 二进制：0000...0101
int m = ~n;         // m = 1111...1010，若 int32 约为 -6
cout << m << endl;

2.3 交换两个整数（无临时变量）

使用异或交换法：

int a = 3, b = 7;
a ^= b;  // a = a ^ b
b ^= a;  // b = b ^ (a ^ b) = 原 a
a ^= b;  // a = (a ^ b) ^ a = 原 b
cout << "a=" << a << ", b=" << b << endl;  // a=7, b=3

2.4 获取最低位的 1

lowbit = x & -x

int x = 12;         // 二进制：1100
int lowbit = x & -x;  // 0100（二进制的最低位 1）
cout << "lowest bit: " << lowbit << endl;

2.5 判断是否为 2 的幂

如果 x > 0 && (x & (x - 1)) == 0，则 x 是 2 的幂。

bool isPowerOfTwo(int x) {return x > 0 && (x & (x - 1)) == 0;
}

三、位运算在数据结构中的应用

1. 位图（Bitset）

当需要高效存储大量布尔标记时，std::bitset 能以 1 bit/标记的方式节省空间，且支持所有位运算：

const int N = 1000;
bitset<N> vis;  // 初始化时全为 0// 标记 10, 20, 30 为已访问
vis.set(10);
vis.set(20);
vis.set(30);// 查询
if (vis.test(20)) cout << "20 已访问\n";// 清除标记
vis.reset(20);

2. 二进制索引树（Fenwick Tree）

Fenwick Tree 中最经典的技巧是使用 i & -i 获得当前节点所负责的区间长度（lowbit），进而实现 O(log n) 的区间和与单点更新。

class Fenwick {
private:int n;vector<long long> tree;// lowbit: 返回 i 最低位的 1 所对应的值inline int lowbit(int i) { return i & -i; }public:Fenwick(int _n): n(_n), tree(n + 1, 0) {}// 单点更新：index 增加 deltavoid update(int index, long long delta) {for (int i = index; i <= n; i += lowbit(i)) {tree[i] += delta;}}// 前缀和查询：[1..index]long long query(int index) {long long sum = 0;for (int i = index; i > 0; i -= lowbit(i)) {sum += tree[i];}return sum;}// 区间和查询：[l..r]long long rangeQuery(int l, int r) {return query(r) - query(l - 1);}
};int main() {Fenwick fw(10);// 初始化：将第 3 号位置加 5fw.update(3, 5);// 查询前缀和cout << "sum[1..3] = " << fw.query(3) << endl;// 区间和cout << "sum[2..5] = " << fw.rangeQuery(2, 5) << endl;return 0;
}