位运算

作用

计算机底部实现方式是二进制，熟练运用并掌握位运算可以提高程序运行的时空效率

彩蛋

蓝书前言编号0xFF 为 -1，后记为0x7F 为 127（在有符号8位二进制数的条件下）

初步认识

与：and，&，∧（可以与集合运算联合起来记忆）
或：or，|，∨
非：not，~，¬
异或：xor，^

在 $m$ 位二进制数中，最低位通常为第 $0$ 位，从右往左递加，最高位为 $m-1$ 位

整数的存储与运算

下面以32位二进制数，即C++中的int和unsigned int 为例子介绍。

补码

unsigned int 直接把编码C看成32位二进制数S
int 最高位为符号位，0表示非负数，1表示负数。符号位为0的，直接把编码C看成32位二进制数S。符号位为1的，定义该编码C按位取反后得到的~C表示的数值为 $-1-S$

可发现，在补码下每个数值有唯一的表示方法并且任意两个数值做加减法时，都等价在32位补码下做最高位不进位（就是最高位溢出的话直接不管了1+1=0，但倒数第二位的进位要进，类似这种）的二进制加减法运算。溢出时，32位无符号整数相当于自动对 $2^{32}$ 取模。这也解释了“有符号整数”算数上溢时出现负数的现象。（然而并没看懂，有无dalao帮忙解答一下）

反码

略过，就是比补码少加1

简单表示

用二进制表示一个int要32位，比较繁琐，采用十进制又表现不出补码的每一位，所以常用十六进制表示一个常数。这样只用8个字符。常用数值：0x3F3F3F3F （2倍不会溢出，每个字节相同，方便赋值）

移位运算

左移：在二进制表示下把数字向左移动，低位补0，高位越界舍弃。

1 << n = 2^n

n << 1 = 2 \times n

算数右移：二进制补码表示下，把数字同时向右移动，高位以符号位填充，低位越界后舍弃。等同于除以2后向下取整。（ $(-3)>>1=-2$ ）逻辑右移：二进制补码表示下，把输出同时向右移动，高位以0填充，低位越界后舍弃。一般的编译器均使用算数右移。

应用

求 $a^b\mod p$

根据数学常识，每一个数都可以唯一表示为若干指数不重复的2的次幂的和（因为任何一个整数都可以转换成二进制），也就是说如果 $b$ 在简直表示下有 $k$ 位，其中第 $i（0\leq i\leq k）$ 位的数字为 $c_i$ ，那么

b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+......+c_02^0

于是

a^b=a^{c_{k-1}*2^{k-1}}*a^{c_{k-2}*2^{k-2}}*......*a^{c_0*2^0}

于是我们可以写出如下代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a = 0;
    int b = 0;
    int p = 0;
    int ans = 1;
    cin >> a >> b >> p;
    for(;b > 0;b >>= 1)
    {
        if(b & 1)
        {
            ans = (long long)ans * a % p;
        }
        a = (long long)a * a % p;
    }
    cout << ans % p;
    return 0;
}

在c++语言中，两个数值执行算术运算是，以参与运算的最高数值类型为基准，与保存结果的数值类型无关。

但是这里有一个问题。c++内置的最高整数类型是64位，如运算 $a*b \mod p$ 都在 $10^{18}$ 级别的话，需要特殊处理

运算 $a*b \mod p$ （ $1\leq a,b,p\leq 10^{18}$ ）

方法一：类似快速幂思想

b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+......+c_02^0

那么

a*b=c_{k-1}*a*2^{k-1}+c_{k-2}*a*2^{k-2}+......+c_0*a*2^0

这样做就不会超出64位，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll a = 0, b = 0, p = 0;
    cin >> a >> b >> p;
    ll ans = 0;
    for(;b > 0;b >>= 1)
    {
        if(b & 1)
        {
            ans = (ans + a) % p;
        }
        a = 2 * a % p;
    }
    cout << ans % p;
}

方法2：利用 $a*b \mod p=a*b-\lfloor a*b/p\rfloor *p$ 。记 $c=\lfloor a*b/p\rfloor$ 。如何计算 $c$ 呢。用浮点数(long double)计算。当浮点数的精度不足以保存到精确数位时，会舍弃低位。所以得到 $c.\_\ \_\ \_\ \_$ 。

（long double的作用是，让a*b可以成功的去计算而不会溢出出错，如果采用unsigned long long或long long根本都不能正确计算，更别提误差了，long double即使有误差，但在64位数*64位数乘法中，最大也就到128位，产生的误差也不会过大，也可以得到正确结果）

下面我们再算出 $a*b-c*p$ 就行了。因为 $a*b-c*p$ 实际上是 $a*b \mod p$ ，所以 $a*b-c*p \leq p < 2^{64}$ ，所以

a*b-c*p=(a*b-c*p)\mod 2^{64}=(a*b)\mod 2^{64} - (c*p) \mod 2^{64}

mod $2^{64}$ 就是unsigned long long的自然溢出，再用long long计算最后的结果就行（防止减出负数）

代码如下

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
int main()
{
    ull a, b, p;
    cin >> a >> b >> p;
    a %= p, b %= p;
    ull c = (long double)a * b / p;
    ull x = a * b, y = c * p;
    long long ans = (long long)(x % p) - (long long)(y % p);
    if(ans < 0) ans += p;
    cout << ans % p;
}

本质：将除法转化成减法

状态压缩dp

二进制状态压缩，指的是将一个长度为 $m$ 的bool数组用一个 $m$ 位的二进制表示并存储的方法。下列位运算可以实现对应的操作。

操作	运算
取出整数 $n$ 在二进制表示下的第 $k$ 位	$(n>>k)\&1$
取出整数 $n$ 在二进制表示下的后 $k$ 位	$n\&((1<<k)-1)$
把整数 $n$ 在二进制表示下的第 $k$ 位取反	$n\ xor\ (1<<k)$
把整数 $n$ 在二进制表示下的第 $k$ 位赋值为1	$n\vert (1<<k)$
把整数 $n$ 在二进制表示下的第 $k$ 位赋值为0	$n \& (~(1<<k))$

此方法可以节省大量空间。但当 $m$ 过大时，可选择stl里的bitset。

例题：最短Hamilton路径（Acwing91） “朴素算法”：枚举 $n$ 点的全排列，计算长度取最小值，枚举的复杂度 $O(n!)$ ，计算长度 $O(n)$ ，整体复杂度 $O(n*n!)$ ，使用状压dp可以优化到 $O(n^2*2^n)$ 。

我们用一个 $n$ 位二进制数来表示

{% mermaid %}

graph LR

A[动态规划]

A—>B[状态表示f]

A—>C[状态计算]

{% endmermaid %}