一些位运算

位运算

逻辑运算

& ：两都为1则为1， 否则为0

| ：有一为1则为1

~ ：取反，将每一位都取反（符号位也取反了），因为是补码表示，所以 ~x 为 $ -x -1 $

^ ：异或，两不一样时为1，否则为0

十六进制一些有用的数

\(0x3F3F3F3F\) 两倍不超过 \(int\) 能表示的最大整数；每个字节都是相同的。

\(0x7FFFFFFF\) \(int\) 能表示的最大整数，使用时注意可能有算数溢出（会成负数）

移位运算

<< ：左移

>> ：右移

在二进制下左移右移。

左移

二进制下同时向左移动，低位以0填充，高位越界舍去

例如：\(1 << n = 2^n\) ; \(n << 1 = 2n\)

注意 ：会占符号位

如：\((1 << 31) = -2147483648\) ，因为有 \(0\) 占着 int 类型最多到 \(2^{31}- 1\) ，这种情况下如果我们想要表示 int 下最大的整数只要减一让它溢回去就行了。

右移

右移分为算术右移和逻辑右移，两者区别在于高位以什么填充

算术右移： 低位越界舍去，高位以符号位填充

逻辑右移：低位越界舍去，高位以 0 填充

现在的编译器一般都使用算术右移，算术右移的好处负数不会出问题，如 -2 逻辑右移后会是：2147483647

二进制拆分思想

二进制拆分思想最经典的应用是快速幂

int ksm(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1) {
        ans = (long long) ans * a % p;
        a = (long long) a * a % p;
    }
}

二进制状压思想

将状态压成二进制数。

如：最短Hamilton路径

可以将哪些点走过了，哪些点没走过压成一个状态。

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
int G[25][25], n;
int f[1 << 21][20];
signed main() {
    n = read();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            G[i][j] = G[j][i] = read();
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    for (int i = 1; i < (1 << n); i++)
        for (int j = 0; j < n; j++) if (i >> j & 1)
            for (int k = 0; k < n; k++) if ((i ^ 1 << j) >> k & 1)
                f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + G[k][j]);
    cout << f[(1 << n) - 1][n - 1];

}

成对变化技巧

0、1； 2、3等关于 xor 1 构成成对变换。

lowbit运算

lowbit(x) = x & (-x)