位运算例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
意思就是通过位运算减少循环次数，从而避免程序超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}