藍書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 %}