知识点总结

补码
- 计算机中 -x = ~x + 1
- memset(a, 0x3f, sizeof a) 将a的每个字节初始化为0x3f，由于int的最大值是0x7fffffff，这样可以避免加法溢出
基本运算
- 与 &
- 或 |
- 非 ~
  - for (int i = n; ~i; i--) 表示for (int i = n; i >= 0; i--)
- 异或 ^
- 移位
  - 左移
  - 算术右移
    - 高位以符号位填充，低位越界后舍弃
    - C++编译器大多采用算术右移，并且整数/2具体实现是“向零取整”，如(-3) / 2 = -1而非-2
二进制状态压缩
- 将一个长度为m的bool数组用一个m位二进制整数表示并存储
- 常用位运算
  - 取出n的第k位：(n >> k) & 1
  - 取出n的第0~k - 1位：n & ((1 << k) - 1)
  - 第k位取反：n ^ (1 << k)
  - 第k位赋值为1：n | (1 << k)
  - 第k位赋值为0：n ^ (~(1 << k))
- m较大时，可以用一个int数组，也可以直接利用bitset（待补充）
优先级
- 加减》移位》比较大小》按位与》异或》按位或
成对变换
- 当n >= 0时
  - n为偶数时，n xor 1 = n + 1
  - n为奇数时，n xor 1 = n - 1
- 用于邻接表中获取当前边和反向边
lowbit
- lowbit(n) = 非负整数n在二进制表示下最低位的1及其后边所有0
- lowbit(n) = n & (~n + 1) = n & -n
- 结合Hash可以找出整数二进制表示下所有是1的位，花费的时间与1的个数相同
  - 模板 ```cpp // n 较小时 const int N = 1 << 20; int h[N]; for (int i = 0; i <= 20; i++) h[1 << i] = i;

while (cin >> n) { while (n) { cout << h[n & -n] << endl; n -= n & -n; } cout << endl; }

// n 较大时 int h[37]; for (int i = 0; i < 36; i++) h[(1ll << i) % 37] = i;

while (cin >> n) { while (n) { cout << h[(n & -n) % 37] << ‘ ‘; n -= n & -n; } cout << endl; }

<a name="zhcEf"></a>
# 例题
<a name="iXHeL"></a>
## 快速幂
将整数改写成二进制表示，然后将整个表达式展开
<a name="JHJ39"></a>
### [a^b](https://www.acwing.com/problem/content/91/)
```cpp
#include <iostream>
typedef long long LL;
using namespace std;
int main() {
    int a, b, p;
    cin >> a >> b >> p;
    int res = 1 % p;    //防止b=0
    while (b) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    cout << res;
    return 0;
}

64位整数乘法

#include <iostream>
using namespace std;
typedef unsigned long long ULL;
int main() {
    ULL a, b, p;
    cin >> a >> b >> p;
    ULL res = 0;
    if (a < b) swap(a, b);
    while (b) {
        if (b & 1) res = (res + a) % p;    //将乘法改写成加法
        a = a * 2 % p;
        b >>= 1;
    }
    cout << res;
    return 0;
}

状压DP

最短Hamilton路径

暴力做法枚举n个点的全排列，计算路径长度取最小值，时间复杂度O(n*n!)
状压DP可以优化到位运算 - 图3
状态 f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j])

i：二进制表示的路径，1经过，0未经过
j：目前所在的结点
枚举倒数第二个经过的点k ```cpp
include
include

using namespace std;

const int N = 20, M = 1 << N;

int g[N][N]; int f[M][N];

int main() { int n; cin >> n;

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        scanf("%d", &g[i][j]);
memset(f, 0x3f, sizeof f);
f[1][0] = 0;    //起点为0
for (int i = 0; i < 1 << n; i++)
    for (int j = 0; j < n; j++)
        if (i >> j & 1)    //确保经过j
            for (int k = 0; k < n; k++)
                if (i >> k & 1)    //确保经过k
                    f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);
cout << f[(1 << n) - 1][n - 1];    //终点为n-1,所有点都经过
return 0;

}

<a name="cCa1Q"></a>
## 位运算性质
二进制表示下不进位，参与位运算的各个位是独立的，因此可以枚举每个位的取值
<a name="wgUgu"></a>
### [起床困难综合症](http://uoj.ac/problem/2)
```cpp
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const int N = 1e5 + 10;
pair<string, int> a[N];
int n, m;
int cal(int bit, int now) {
    for (int i = 0; i < n; i++) {
        int x = a[i].second >> bit & 1;
        if (a[i].first == "OR") now |= x;
        else if (a[i].first == "AND") now &= x;
        else now ^= x;
    }
    return now;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        char op[5];
        int t;
        scanf("%s%d", op, &t);
        a[i] = make_pair(op, t);
    }
    int ori = 0, res = 0;
    for (int i = 30; ~i; i--) {
        int t0 = cal(i, 0);
        int t1 = cal(i, 1);
        if (ori + (1 << i) <= m && t1 > t0) {
            ori += 1 << i;
            res += t1 << i;
        } else {
            res += t0 << i;
        }
    }
    cout << res;
    return 0;
}