蓝书0x01 - histcat

位运算#

作用#

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

彩蛋#

蓝书前言编号 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：
利用 $ab \mod p=ab-\lfloor a*b/p\rfloor p$。记 $c=\lfloor ab/p\rfloor$。
如何计算 $c$ 呢。用浮点数 (long double) 计算。当浮点数的精度不足以保存到精确数位时，会舍弃低位。所以得到 $c._\ _\ _\ _$。

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

下面我们再算出 $ab-cp$ 就行了。因为 $ab-cp$ 实际上是 $ab \mod p$，所以 $ab-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 (nn!)$，使用状压 dp 可以优化到 $O (n^22^n)$。

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

{% mermaid %}

graph LR

A [动态规划]

A-->B [状态表示 f]

A-->C [状态计算]

{% endmermaid %}