位运算： & （与） eg:
| （或） eg:
^ （异或） 运算规则：（不进位加法） 1 2 3 4 0 0 ——> 0 1 0 ——> 1 0 1 ——> 1 1 1 ——> 0
不进位的加法 1 ^ 1 ==> 0 正常的话：1 + 1 = 20b,但是只看个位, 因此, 取0
运算法则：
交换律
结合律
即$(a^b)^c == a^{b^c}$
对于任何数x, 都有
$x^x=0, x^0=x$
自反性：
A XOR B XOR B = A xor 0 = A
~ （取反）
<< （左移） eg:
1 2 1101 << 1 ===> 11010 1 << n <==> 2^n （向上取整）
>> （右移） eg:
技巧： x + (-x)
经验：
将数组无穷大：memset(nums, 0x3f, sizeof(nums))
竞赛中少使用 #include <bits/stdc++.h> // 原因：编译的时间过长,时间会超时
转化成 long long 的形式：乘以 1ll,例子见——>快速幂算法模板—求 $a^b%p$
将大数组放到全局变量中
快速幂算法模板
求 $a^b$
1 2 3 4 5 6 7 8 9 10 11 long long quickPower (int a, int b) long long res = 1 ; while (b) { if (b & 1 ) res *= 1ll * a; a *= a; b >>= 1 ; } return res; }
求 $a^b%p$
1 2 3 4 5 6 7 8 9 10 11 12 int quickPowerMod (int a, int b, int p) int res = 1 % p; while (b) { if (b & 1 ) res = res * 1ll * a % p; a = a * 1ll * a % p; b >>= 1 ; } return res; }
模运算法则 1 2 3 4 5 6 7 (a + b) % p = (a % p + b % p) % p (a - b) % p = (a % p - b % p) % p (a * b) % p = (a % p * b % p) % p (a^b) % p = ((a % p)^b) % p
位运算常用技巧 用异或来实现配偶 即(把每个整数异或一个1, 就可以得到他的配偶)
1 2 3 4 0 ^ 1 = 1, 1 ^ 1 = 0 2 ^ 1 = 3, 3 ^ 1 = 2 …… 2k ^ 1 = 2k + 1, (2k + 1) ^ 1 = 2k
用法 一般在图论里面, 写最小费用流时, 我们会存一个编的正向编和反向编, 会需要快速求出来一个数的反向编是什么
lowbit运算(树状数组的基础) 定义 快速的求出来整数n, 在二进制表示里面, 最低的一位1是哪个(或者说：n的二进制表示中最右边一个1)
效果 lowbit(1110011000) ——> 1000
实现 1 2 3 4 5 首先, 假设n的二进制是1110011000 然后, 对n取反, 得到：~n = 0001100111 接着, ~n+1 ===> 0001101000 紧接着, (~n + 1) & n ===> 0000001000 ===> 1000 最后, 由于-n = ~n + 1,所以lowbit就是：(-n) & n
代码实现 1 2 3 4 int lowbit (int n) return (-n) & n; }
拓展
复杂度和1的个数有关和
可以快速求出来一个整数里面有多少个1
求n是2的整次方幂
解析:
$$
$$
原码、反码、补码 正数 原码, 反码, 补码均相等。
负数
反码求法：
符号位不变。
其他位取反。
补码求法：
例子 以123和-123为例：
[123] 原码：01111011。 反码：01111011。 补码：01111011。
[-123]原码：11111011。 反码：10000100。 补码：10000101。
二进制转换成10进制
如果为正数, 则直接求即可
如果为负数, 取反+1, 然后求出数值前面加个负号。
