蓝书0x01

位运算

作用

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

彩蛋

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

初步认识

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

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

整数的存储与运算

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

补码

1. unsigned int
   直接把编码C看成32位二进制数S

2. 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填充，低位越界后舍弃。
一般的编译器均使用算数右移。

应用

1. 求$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}$级别的话，需要特殊处理

2. 运算$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;
}

本质：将除法转化成减法

3. 状态压缩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$位二进制数来表示

graph LR A[动态规划] A-->B[状态表示f] A-->C[状态计算]