0x01 位运算

基本操作

1
2
3
4
与	&	都为真为真
或 | 有一个为真就为真
非 ! 真的变假,假的变真
异或 ^ 如果相同为0,不同为1

补码

int 32位 首位符号位,如果是0为正数,为1为负数。

1
2
3
1: 0000000000...01
2: 0000000000...10
3: 0000000000...11

补码:

1
2
3
4
5
6
7
8
1 + x = 000000000...00
x = 1111111111...11
1 + 1111111111...11 = 0000000000...00
2 + 1111111111...10 = 0000000000...00
x + ??????????...?? = 0000000000...00
? = ~x + 1
~x + 1 是 x 的补码
-n = ~n + 1

小技巧

  • 数组初始化memset(f,0x3f,sizeof(f))
  • 左移运算符 <<
1
2
3
二进制 : 1 -> 10 -> 100 -> 1000
十进制 : 1 -> 2 -> 4 -> 8
综上所述:1 << n == 2^n
  • 右移运算符>>
1
2
3
二进制 : 1000 -> 100 -> 10 -> 1
十进制 : 8 -> 4 -> 2 -> 1
综上所述: n >> x == n / (2^x)

例题1a^b快速幂

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p,在同一行用空格隔开。

输出格式

输出一个整数,表示a^b mod p的值。

数据范围

$1≤a,b,p≤10^9$

输入样例:

1
3 2 7

输出样例:

1
2

题解:

按照朴素算法就是把a连乘b次,这样一来时间复杂度是O(b)也即是O(n)级别,快速幂能做到O(logn)。

$a^b$,那么其实b是可以拆成二进制的,该二进制数第i位的权为$2^{(i-1)}$,例如当b==11时,$a^{11}=a^{(2^0+2^1+2^3)}$ 。

11的二进制是1011,11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1,因此,我们将a¹¹转化为算 $a^(2^0)a^(2^1)a^(2^3) $ 。

由于是二进制,很自然地想到用位运算这个强大的工具: & 和 >> ,&运算通常用于二进制取位操作,例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶,x&1==1为奇。>>运算比较单纯,二进制去掉最后一位 。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

int a,b,mod;

int main(void)
{
cin >> a >> b >> mod;

int res = 1 % mod;

while(b)
{
if(b&1) res = 1ll * res * a % mod;

a = 1ll * a * a % mod;
b >>= 1;
}

cout << res;
return 0;
}

例题2:64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式

第一行输入整数aa,第二行输入整数bb,第三行输入整数pp。

输出格式

输出一个整数,表示a*b mod p的值。

数据范围

1≤a,b,p≤10181≤a,b,p≤1018

输入样例:

1
2
3
3
4
5

输出样例:

1
2

题解:

1
2
3
4
5
6
7
a * b
a + a + a + a + a + a +...+ a
a * 1 = a
a * 2 = 2a
a * 3 = 3a
...
a * (2^k) = 2^k * a

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

long long a,b,mod;

int main(void)
{
cin >> a >> b >> mod;
long long ans;
while(b)
{
if(b&1) ans = (ans + a) % mod;
a = a * 2 % mod;
b >>= 1;
}
cout << ans << endl;

return 0;
}
本站文章除注明转载外均为原创,未经允许不要转载哇. ヾ(゚ー゚ヾ) http://chicago01.top/2019/01/30/0x01-位运算/index.html
Compartir