2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

位运算的原理及应用（C++）_c++位运算

作者：2023面试高手 | 2024-06-15 09:28:52

踩

c++位运算

位运算的原理及应用（C++）

1. 位运算的基本原理

计算机中的数据都以二进制形式存储和处理，位运算直接对二进制位进行操作。常见的位运算符包括与（&）、或（|）、异或（^）、取反（~）和左移（<<）、右移（>>）等。

与（&）：两个位都为1时，结果为1；否则为0。
或（|）：两个位只要有一个为1时，结果为1；否则为0。
异或（^）：两个位相同时，结果为0；不同时，结果为1。
取反（~）：将每个位上的0变为1，1变为0。
左移（<<）：将二进制位向左移动指定位数，相当于乘以2的指定次方。
右移（>>）：将二进制位向右移动指定位数，相当于除以2的指定次方。

2. 位运算的应用

a. 位运算的常用应用

位运算在计算机科学和工程中具有广泛的应用，下面介绍其中一些常见的应用场景。

1) 位运算处理标志位

在计算机系统中，常常使用二进制的位来表示各种开关或状态，例如操作系统中的权限标志位、硬件设备的状态等。通过位运算可以有效地设置、清除或检查这些标志位，从而实现对系统或设备的控制。

2) 位运算进行快速计算

位运算可以在某些情况下替代算术运算，从而提高代码执行效率。例如，通过位运算可以快速判断一个整数是奇数还是偶数（使用位与运算符&，奇数的二进制表示的最后一位一定为1），或者快速计算一个整数的二进制表示中有多少个1（使用位与运算符&和右移运算符>>）。

3) 位运算进行位操作

位运算可以对一个整数的某些特定位进行操作，例如将某一位设置为1或0，或者获取某一位的值。这在某些场景下非常有用，例如可以通过位运算来实现对图像数据的位操作，如图像的亮度调节、像素值的提取等。

b. 位运算的例子

下面通过几个具体的例子，来展示在C++语言中如何使用位运算。

例一：判断一个整数是否为奇数


bool isOdd(int num) {
    return (num & 1) == 1;
}

例二：将一个整数的某一位设置为1


int setBit(int num, int pos) {
    return num | (1 << pos);
}

例三：获取一个整数的某一位的值


int getBit(int num, int pos) {
    return (num >> pos) & 1;
}

3.C++竞赛题中的位运算

在很多编程刷题网站、编程比赛平台都有位运算相关的题目，下面举一例并作详细讲解：

a. 按位与

评测地址（需登录）

特别要注意的是：本题限时5ms！

分析：

由于时间要求过高，暴力枚举只能得5分。

考虑优化：

把0~15的二进制列举出来，如下表：

行↓列<-	3	2	1	0
0	0	0	0	0
1	0	0	0	1
2	0	0	1	0
3	0	0	1	1
4	0	1	0	0
5	0	1	0	1
6	0	1	1	0
7	0	1	1	1
8	1	0	0	0
9	1	0	0	1
10	1	0	1	0
11	1	0	1	1
12	1	1	0	0
13	1	1	0	1
14	1	1	1	0
15	1	1	1	1

纵向观察，发现右数第0列，01交替；右数第1列，2个0与2个1交替；右数第n列， $2^{n}$ 个0与 $2^{n}$ 个1交替。

事实上，对于上数第m行、右数第n列的格，它的布尔值为： $[\frac{m}{2^{n}}] (mod 2)$ ，我们定义MyFind函数为这个公式。

因为是按位与，所以对于给定的l,r，只要有一列包含0，则结果的这一位也一定是0.具体来说，若 $r-l+1>2^{n}$ ，则意味着r-l跨了超过 $2^{n}$ ，那此列一定包含0，此时直接把结果的二进制该位设为0，否则若MyFind(l)与MyFind(r)都为1，则意味着[l,r]区间对于此列的值全部是1，此时将该位设为1，否则为0。

代码如下：


#include <bits/stdc++.h>
#define LL unsigned long long
using namespace std;
LL MyPow[63]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904};
bool bitans[63];
bool MyFind(LL x,LL y)
{
	return x/MyPow[y]%2;
}
int w(LL x)
{
	int a=0;
	while(x)
	{
		x/=2;
		a++;
	}
	return a;
}
int main()
{
	LL l,r,ans=0; 
	cin>>l>>r;
	for(int i=0;i<w(r);i++)
	{
		if(r-l+1>MyPow[i])
			bitans[i]=false;
		else if(MyFind(l,i)&&MyFind(r,i))
			bitans[i]=true;
		else
			bitans[i]=false;
	}
	for(int i=0;i<w(r);i++)
	{
		ans+=bitans[i]*MyPow[i];
	}
	cout<<ans;
	return 0;
}

上述代码为了减小耗时，使用了打表大法，将 $2^{n}$ 预先存储。

提交上去以后，AC了：

从上面的例子可以看出，虽然有些时候没有使用任何位运算的运算符，但是仍然需要位运算的思想。

4. 总结

位运算是计算机底层操作中十分重要的一部分，掌握位运算的基本原理和常见应用场景可以提高代码的执行效率和可读性。在C++中，我们可以使用位运算符进行位运算操作，并灵活应用于不同的场景中。

通过深入理解位运算的原理和使用技巧，我们可以更好地利用位运算在程序开发中解决问题，并进一步提升代码的质量和性能。

希望本文能够帮助读者加深对位运算的理解，并在实际的C++开发中灵活应用位运算，为开发高效、优质的程序做出贡献！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/721746