算法竞赛-基础算法-位运算

ops/2025/3/18 16:37:38/

1.快速幂

2.快速乘

3.lowbit(n)

4.其他

5.相关题目

6.小结

引言：位运算的主要特点之一是在二进制表示下不进位，一下为一些基础的位运算操作：

与	或	非	异或
and,&	or,\|	not,~	xor

1.快速幂

快速幂的计算原理就是基于位运算，把阶乘的数当作二进制一个个拆分掉

//快速幂
long long quick_pow(long long a, long long n, long long p)//相当于计算(a ^ b) mod p
{long long res = 1;while (n){if (n & 1) res = (res * a) % p;n /= 2;a = (a * a) % p;}return res % p;
}

每次n都会向左移位，如果这位是1的话就将这个数乘到res中，再让基数进行平方，每次运算后要进行取模，这样就是一个很完整的快速幂

2.快速乘

如果遇上a*b%p，其 $1\leq a,b\leq10^{18}$ ,这时候就要用到快速乘了，如果直接进行运算的话会导致超过long long最大的限制

//快速乘，64位
long long mul(long long a, long long n, long long p)//相当于计算(a * n) mod p
{long long res = 0;while (n){if (n & 1) res = (res + a) % p;n /= 2;a = (a * 2) % p;}return res;
}

这个代码的写法同上，都是利用的位运算来进行乘法

3.lowbit(n)

位运算还有一个最重要的就是lowbit(n)，lowbit(n)定义为n在二进制表示下"最低位的1以及后边所有的0。

#define lowbit(x) x&-x

因为lowbit(n)=n&(~n+1)=n&(-n),所以就可以利用以上定义

lowbit(n)运算配合hash可以找到整数二进制表示下所有是1的位。

//任意k属于[0,35],2的k次方mod37互不相等，且恰好取遍整数1-36
int H[37];
int n;
for (int i = 0; i < 36; i++) H[(1ll << i) % 37] = i;
while (cin >> n)
{while (n > 0){cout << H[(n & -n) & 37] << " ";n -= n & -n;}cout << endl;
}

这个效率十分高效，几乎相当于o(1)。

lowbit(n)运算也是树状数组中一个基本运算，这个之后再讲、

4.其他

位运算还有一些相关的库函数，不过并非C语言标准，最好不要随便使用

int __builtin_ctz(unsigned int x);
int __builtin_ctzll(unsigned long long x);
//返回x的二进制表示下最低位的1后边有多少0int __builtin_popcount(unsigned int x);
int __builtin_popcountll(unsigned long long x);
//返回x的二进制表示下有多少位为1

5.相关题目

快速幂的模板题

P1226 【模板】快速幂 - 洛谷

快速乘的模板题

P10446 64位整数乘法 - 洛谷

还有一道位运算相关的题目

P2114 [NOI2014] 起床困难综合症 - 洛谷

这个题目就单独考虑每一位，这样时间复杂度就是O(30*n)，以下是代码和解释

#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
string b[N];
int n, m;
int calc(int bit, int now)//计算所有运算后对这意味的影响
{for (int i = 1; i <= n; i++){int x = a[i] >> bit & 1;if (b[i] == "AND") now &= x;else if (b[i] == "OR") now |= x;else now ^= x;}return now;
}
int main()
{cin >> n >> m;int sum = 0, ans = 0;for (int i = 1; i <= n; i++)cin >> b[i] >> a[i];for (int bit = 30; bit >= 0; bit--){int res0 = calc(bit, 0);int res1 = calc(bit, 1);if (sum + (1 << bit) < m && res0 < res1)//如果超过m并且取1比取0有用sum += 1 << bit, ans += res1 << bit;else ans += res0 << bit;}cout << ans << endl;
}