浅谈位运算及其应用（c++）

在 C++ 编程中，位运算是一种强大而高效的操作方式，它允许我们直接对数据的二进制位进行操作。这不仅能够提高程序的性能，还能在某些特定的场景下实现一些独特而精妙的功能。在这篇博客中，我们将深入研究 C++ 中的位运算。

一、位运算的基础

（一）位与（&）

位与运算将两个操作数的对应位进行与操作，如果两个位都为 1，则结果位为 1，否则为 0。

int a = 5;  // 0101
int b = 3;  // 0011
int result = a & b;  // 0001，结果为 1
1
2
3

（二）位或（|）

位或运算将两个操作数的对应位进行或操作，如果两个位中至少有一个为 1，则结果位为 1，否则为 0。

int c = 5;  // 0101
int d = 3;  // 0011
int result = c | d;  // 0111，结果为 7
1
2
3

（三）位异或（^）

位异或运算将两个操作数的对应位进行异或操作，如果两个位不同，则结果位为 1，否则为 0。

int e = 5;  // 0101
int f = 3;  // 0011
int result = e ^ f;  // 0110，结果为 6
1
2
3

（四）位取反（~）

位取反运算将操作数的每一位取反，即 1 变为 0，0 变为 1。

int g = 5;  // 0101
int result = ~g;  // 1010，结果为 -6（考虑符号位）
1
2

（五）左移（<<）

左移运算将操作数的所有位向左移动指定的位数，右侧补 0。

int h = 5;  // 0101
int result = h << 2;  // 010100，结果为 20
1
2

（六）右移（>>）

右移运算将操作数的所有位向右移动指定的位数，对于无符号数，左侧补 0；对于有符号数，左侧补符号位。

int i = 20;  // 10100
int result = i >> 2;  // 00101，结果为 5
1
2

二、位运算的应用

（一）设置、清除和检查特定位

通过位与、位或和位异或，可以方便地设置、清除或检查一个整数中的特定二进制位。

int num = 0x12;  // 0001 0010
// 设置第 3 位
num |= (1 << 3);  // 0001 1010

// 清除第 2 位
num &= ~(1 << 2);  // 0001 0010

// 检查第 4 位是否为 1
bool isSet = (num & (1 << 4))!= 0;
1
2
3
4
5
6
7
8
9

（二）压缩数据存储

在某些情况下，可以使用位运算来有效地压缩数据，减少存储空间的使用。
例如，用一个字节表示 8 个布尔值。

char flags = 0;
flags |= (1 << 0);  // 设置第 0 个布尔值为真
flags &= ~(1 << 1);  // 设置第 1 个布尔值为假
1
2
3

（三）快速计算乘除法

通过左移和右移可以实现快速的乘以 2 的幂和除以 2 的幂的运算。

int num = 5;
int multiplyBy8 = num << 3;  // 相当于乘以 8
int divideBy4 = num >> 2;  // 相当于除以 4
1
2
3

（四）权限控制和标志位

在系统编程和权限管理中，常常使用位运算来表示和处理各种权限和标志。

enum Permissions {
    READ = 1 << 0,
    WRITE = 1 << 1,
    EXECUTE = 1 << 2
};

int userPermissions = READ | WRITE;  // 用户具有读和写权限
1
2
3
4
5
6
7

（五）实现枚举类型的位标志组合

enum OptionFlags {
    OPTION_1 = 1 << 0,
    OPTION_2 = 1 << 1,
    OPTION_3 = 1 << 2
};

void handleOptions(int options) {
    if (options & OPTION_1) {
        // 处理 OPTION_1 相关逻辑
    }
    if (options & OPTION_2) {
        // 处理 OPTION_2 相关逻辑
    }
    // 以此类推
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、位运算的性能优势

位运算通常比普通的算术运算更高效，因为它们直接在硬件层面上操作二进制位，不需要进行复杂的数学计算。
例如，在处理大量数据或者对性能要求苛刻的场景中，使用位运算可以显著提高程序的执行速度。

// 比较使用乘法和左移的性能
#include <iostream>
#include <chrono>

void multiply(int n, int times) {
    for (int i = 0; i < n; ++i) {
        int result = i * times;
    }
}

void shiftLeft(int n, int times) {
    for (int i = 0; i < n; ++i) {
        int result = i << times;
    }
}

int main() {
    int n = 10000000;
    int times = 4;

    auto start1 = std::chrono::high_resolution_clock::now();
    multiply(n, times);
    auto end1 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed1 = end1 - start1;

    auto start2 = std::chrono::high_resolution_clock::now();
    shiftLeft(n, times);
    auto end2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed2 = end2 - start2;

    std::cout << "乘法运算耗时: " << elapsed1.count() << " 秒" << std::endl;
    std::cout << "左移运算耗时: " << elapsed2.count() << " 秒" << std::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

四、位运算的注意事项

（一）符号扩展问题

在有符号数的右移操作中，要注意符号扩展可能导致的结果不一致。

int signedNum = -5;
int shiftedSigned = signedNum >> 1;  // 结果取决于编译器的实现，可能不是预期的
1
2

（二）可移植性

不同的硬件平台和编译器可能对位运算的处理方式略有不同，尤其是涉及到有符号数的操作。

（三）可读性

位运算虽然高效，但可能会降低代码的可读性。在使用时，应添加足够的注释以说明其目的和逻辑。

五、总结

位运算在 C++ 中是一种强大而灵活的工具，掌握它可以让我们在编程中更加高效地处理数据、优化性能，并实现一些复杂而有趣的功能。但同时，我们也要注意其使用的场景和可能带来的潜在问题，以确保代码的正确性和可维护性。
希望通过这篇博客，您对位运算在 C++ 中的应用有了更深入的理解和认识，能够在实际编程中灵活运用，创造出更优秀的程序。

例题讲解

高低位交换

题目描述

给出一个小于 $2^{32}$ 的非负整数。这个数可以用一个 $32$ 位的二进制数表示（不足 $32$ 位用 $0$ 补足）。我们称这个二进制数的前 $16$ 位为“高位”，后 $16$ 位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。

例如，数 $1314520$ 用二进制表示为 $00000000000101000000111011011000$（添加了 $11$ 个前导 $0$ 补足为 $32$ 位），其中前 $16$ 位为高位，即 $0000000000010100$；后 $16$ 位为低位，即 $0000111011011000$。将它的高低位进行交换，我们得到了一个新的二进制数 $00001110110110000000000000010100$。它即是十进制的 $249036820$。

输入格式

一个小于 $2^{32}$ 的非负整数

输出格式

将新的数输出

样例 #1

样例输入 #1

1314520
1

样例输出 #1

249036820
1

思路

就是一个简单的位移运算

AC代码

#include <iostream>
using namespace std;
unsigned int n;

int main()
{
    cin>>n;
    cout<<(n >> 16) + (n << 16)<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10

异或积

题目背景

$\text{id: 4d7e}$

小 H 在课堂上学习了异或运算。

对于两个非负整数 $x,y$，它们的异或是指，将它们作为二进制数，对二进制表示中的每一位进行如下运算得到的结果：

• $x$ 和 $y$ 的这一位上不同时，结果的这一位为 $1$；
• $x$ 和 $y$ 的这一位上相同时，结果的这一位为 $0$。

$x$ 和 $y$ 的异或被记为 $x\mathrm{xor}y$ 或 $x\oplus y$。

在 C++ 中，你可以用 x ^ y 得到 $x$ 与 $y$ 的异或值。

另外，若干个数的异或称之为异或和。

题目描述

小 H 还了解到，一个长度为 $n$ 的数列 $a$ 的异或积是一个等长的数列 $b$，其中 $b_i$ 等于数列 $a$ 中除了 $a_i$ 以外其他元素的异或和，即

$$b_i=\underset{j=1}{\overset{n}{⨁}}[j\ne i]a_j$$

例如，数列 { 1 , 2 , 3 , 4 } \{1, 2, 3, 4\} {1,2,3,4} 的异或积为 { 5 , 6 , 7 , 0 } \{5, 6, 7, 0\} {5,6,7,0}。

异或积变换是指将一个数列用它的异或积替换的过程，由于异或积变换之后数列长度不变，所以异或积变换可以连续进行多次。

现在，小 H 有一个长度为 $n$ 的数列 $a$，他想请你帮他计算出 $a$ 经过 $k$ 次异或积变换之后得到的序列。

输入格式

本题单个测试点内有多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

对于每一组测试数据：

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_1,a_2,\cdots ,a_n$。

输出格式

对于每一组测试数据：

一行 $n$ 个整数，表示数列 $a$ 经过 $k$ 次异或积变换之后得到的数列。

样例 #1

样例输入 #1

1
4 1
1 2 3 4
1
2
3

样例输出 #1

5 6 7 0
1

样例 #2

样例输入 #2

1
4 2
0 0 0 1
1
2
3

样例输出 #2

0 0 0 1
1

样例 #3

样例输入 #3

见附件中的 samples/xor3.in
1

样例输出 #3

见附件中的 samples/xor3.ans
1

提示

样例 1 解释

此样例即为题目描述中的例子。

样例 2 解释

第 $1$ 次异或积变换： { 0 , 0 , 0 , 1 } → { 1 , 1 , 1 , 0 } \{0,0,0,1\}\to\{1,1,1,0\} {0,0,0,1}→{1,1,1,0}；

第 $2$ 次异或积变换： { 1 , 1 , 1 , 0 } → { 0 , 0 , 0 , 1 } \{1,1,1,0\}\to\{0,0,0,1\} {1,1,1,0}→{0,0,0,1}。

数据规模与约定

对于 $100\%$ 的测试数据，$1\le T\le 10$，$2\le n\le 10^5$，$1\le k\le 10^{18}$，$0\le a_i<2^{32}$。

提示

在 C++ 中，对于数据范围 $0\le x<2^{32}$，你可以：

• 使用 unsigned int x 来定义；
• 使用 cin >> x 或 scanf("%u", &x) 来输入；
• 使用 cout << x 或 printf("%u", x) 来输出。

思路

可以发现当 n 为偶数时，答案将会在 原来的式子 与 变换一次的式子 之间徘徊。

同样，我们也可以验证 n 是奇数的性质：除第一次外其他都是 变换一次的式子。

只需要特判 n 和 k 均为偶数时即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, n; ll k;
ll a[100007], b[100007];
inline void work() {
	ll sum = 0;
	for(int i = 1; i <= n; i++) sum ^= a[i];
	for(int i = 1; i <= n; i++) b[i] = sum ^ a[i];
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>n>>k;
		for(int i = 1; i <= n; i++)cin>>a[i];
		if(n % 2 == 0 && k % 2 == 0) {
			for(int i = 1; i <= n; i++)
				cout<<a[i]<<" ";
			cout<<endl;
			continue;
		}
		work();
		for(int i = 1; i <= n; i++)
			cout<<b[i]<<" ";
		cout<<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

「Daily OI Round 1」Xor

题目描述

给定一个长度为 $n$ 的序列，一共有 $q$ 次询问，每次询问给定正整数 $x$，然后依次执行以下操作：

• 把序列中所有数异或上 $x$。
• 求长度最大的区间 $[l,r]$（$l,r$ 是非负整数）满足区间中的每个整数在序列中出现，区间的长度定义为 $r-l+1$。

注意，在每个询问过后序列是发生变化的。

几个需要说明的地方：

1. “区间”指的是数的区间，比如区间 $[1,3]$ 中的整数有 $1,2,3$，与序列无关。
2. “序列”指的是修改后的序列，同时不包括之前的序列。

输入格式

第一行两个正整数 $n,q$ 表示序列长度和询问个数。

第二行 $n$ 个正整数 $a_i$ 表示一开始的序列。

接下来 $q$ 行，每行一个正整数 $x$ 表示一个询问。

输出格式

输出 $q$ 行，一行一个整数表示每个询问的答案。

样例 #1

样例输入 #1

5 2
1 2 3 4 5
1
1
1
2
3
4

样例输出 #1

4
5
1
2

样例 #2

样例输入 #2

10 10
5 9 8 3 5 7 10 19 5 24
10
56
19
14
18
53
52
57
96
1000
1
2
3
4
5
6
7
8
9
10
11
12

样例输出 #2

2
2
2
4
2
3
3
2
2
2
1
2
3
4
5
6
7
8
9
10

提示

样例解释

对于第一组样例，序列初始是 { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} {1,2,3,4,5}，第一次询问给定 $x=1$，则异或后的序列为 { 0 , 3 , 2 , 5 , 4 } \{0,3,2,5,4\} {0,3,2,5,4}。区间 $[2,5]$ 中的每个整数 $2,3,4,5$ 都在这个序列中，这是满足条件的最大区间，所以答案为 $5-2+1=4$。

数据范围

本题开启捆绑测试。

对于全部数据，保证：$1\le n,q,a_i,x\le 5\times 10^5$。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int M = 25, N = 1 << 19 | 5;
int m = 19, n = 1 << m, q, t, x, y;
struct node{
	int l, r, m, p;
}s[2][N];
inline void pushup(node &u, node &l, node &r)
{
	u.l = l.p ? l.l + r.l : l.l;
	u.r = r.p ? r.r + l.r : r.r;
	u.m = max(l.r + r.l, max(l.m, r.m));
	u.p = l.p & r.p;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>q>>t;
	while(q -- )cin>>x, s[0][x] = {1, 1, 1, 1};
	for(int i = 1, x = 1, y = 0; i <= m; i ++ , x ^= 1, y ^= 1)
		for(int j = 0; j < n; j ++ )
			pushup(s[x][j], s[y][j], s[y][j ^ (1 << i - 1)]);
	while(t -- )cin>>x, y ^= x, cout<<s[1][y].m<<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

这是我的第十三篇文章，如有纰漏也请各位大佬指正

辛苦创作不易，还望看官点赞收藏打赏，后续还会更新新的内容。