位运算例题

位运算例题

tags: 位运算 快速幂 算法

一、a^b

题目

求a的b次方对p取模的值，其中 1<=a,b,p<=10^9
输入描述:
第一行a，第二行b，第三行p。
输出描述:
一个整数，表示a^bmodp的值。

思路

a^16 = (a⁸⁾2 = ((a⁴⁾2)^2 = (((a²⁾2)²⁾2
循环16次 vs 循环3次

eg：
a^26 = a^16 * a^8 *a^2=(((a2)²⁾2)^2 + ((a²⁾2)^2 + (a^2)
26 =16+8+2
26的二进制为11010

11010&1 = 0
a
ans=1
11010>>1 --> 1101
1101&1 = 1
a^2
ans*=a^2
1101>>1 --> 110
110&1 = 0
a^4
110>>1 --> 11
11&1 = 1
a^8
ans*=a^8
11>>1 --> 1
1&1 = 1
a^16 ans*=a^16 1>>1 -->0
意思就是通过位运算减少循环次数，从而避免程序超时

接下来是a^b mod b做法

#include<iostream>
#include<cstdio>
//这里用了scanf和printf也是为了节约时间
using namespace std;
#define ll long long
int main(){
ll a,b,p;
scanf("%lld %lld %lld",&a,&b,&p);
int ans=1;
while(b){
if(b&1) ans = ans*a%p;
//当b的最后一位为1 ，则将此时的a乘上
b>>=1;
//每次b向右移动一位，表示整除2
a=a*a%p;
//每次让a翻倍
}
printf("%lld",ans%p);
return 0;
}

二、64位整数乘法

题目（和上一题很类似）

求a*b对p取模的值，其中 1<=a,b,p<=10^18
输入描述:
第一行a，第二行b，第三行p。
输出描述:
一个整数，表示a * b modp的值。

思路

这道题是要先算出a*b再对其结果进行求模（取余），因为a和b的最大值为1e+18，我们知道乘法有的时候会溢出，即使是 longlong 也可能在乘法时爆掉。所以我们寻找一种能高效完成乘法操作并且不会爆 longlong 的算法，也就是快速乘。

代码原理

可以把 a * b这样算：
a * b = a + a + a + …+ a
而
a * 1 = a
a * 2 = 2a
a * 4 = 4a
a * 8 = 8a
…
所以可以推出：
a * (2 ^ k) = 2 ^ k * a

完整代码

#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
ll a, b, p;
ll ans = 0;//初始化最终的答案
cin >> a >> b >> p;
while (b)
//因为当b为0时将结束循环
{
if (b & 1)//若b二进制的第一位为1时执行，否则不执行，一旦遇到0，就将之前累积的a加上
ans = (ans + a) % p;
//eg: b=5 二进制写法为101
第一次循环ans=a a=2a
第二次ans=a a=4a 第三次ans=a+4a a=8a 此时b=0 循环结束
a = (a * 2) % p;
b >>= 1;//将b的二进制去掉第一位，同b = b >> 1这样写是为了方便
}
cout << ans << endl;
return 0;
}

先就这两题，后面有再补充

详细内容可以去我的个人博客观看，请戳这里

最后

以上就是友好面包为你收集整理的位运算例题的全部内容，希望文章能够帮你解决位运算例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。