青い本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$ です。

補数では、各数値には唯一の表現方法があり、任意の 2 つの数値の加減算は、32 ビットの補数で最高位の繰り上がりを無視する（最高位がオーバーフローした場合は直接無視する、1+1=0 だが、倒数第二位の繰り上がりは考慮する、こういったもの）二進数の加減算演算と同等です。オーバーフロー時、32 ビットの無符号整数は自動的に $2^{32}$ でモジュロを取ります。これにより、「符号付き整数」が算術的にオーバーフローした際に負数が現れる現象が説明されます。（しかし、理解できていません。どなたか助けていただけますか？）

反数#

略しますが、補数より 1 を少なく加えます。

簡単な表現#

int を二進数で表すには 32 ビットが必要で、比較的面倒です。十進数を使用すると補数の各ビットを表現できないため、通常は定数を 16 進数で表現します。これにより、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++ 言語では、2 つの数値が算術演算を実行する際、演算に参加する最高の数値タイプを基準にし、結果を保存する数値タイプには関係ありません。

しかし、ここに問題があります。C++ の組み込み最高整数タイプは 64 ビットであり、$a*b \mod p$ の演算が $10^{18}$ レベルである場合、特別な処理が必要です。

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

方法 1：高速累乗の考え方に似ています。

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 の役割は、ab を計算する際にオーバーフローせずに成功させることです。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 を選択できます。

例題：最短ハミルトンパス（Acwing91）
「素朴なアルゴリズム」：$n$ 点の全順列を列挙し、長さを計算して最小値を取る。列挙の複雑度は $O (n!)$、長さの計算は $O (n)$、全体の複雑度は $O (nn!)$ です。状態圧縮 dp を使用すると $O (n^22^n)$ に最適化できます。

$n$ ビットの二進数を用いて表現します。

{% mermaid %}

graph LR

A [動的計画法]

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

A-->C [状態計算]

{% endmermaid %}