ビット演算学習ノート

ビット演算
適用

高速べき乗

タグ状態——動的計画

配偶者

を異種または実現する

lowbit演算

機能
例
ビット演算
演算子
最下位を外す
(101101->10110) x shr 1 x>>1
最後に0を追加
(101101->1011010) x shl 1 x<<1
最下位を1にする
(101100->101101) x or 1 x|1
最後の取反
(101101->101100) x xor 1 x^1
末尾3位をとる
(1101101->101) x and 7 x&7 1 << n 1左シフトnビット-->2 nn >> x n右シフトxビット-->n/2 x
高速べき乗
mk%pを求めて、時間の複雑度O(logk).

int qmi(int m, int k, int p) {
     
    int res = 1 % p, t = m;
    while (k) {
     
        if (k & 1) res = res * t % p * 1ll;
        // *1ll   int       long long
        t = t * 1ll * t % p;
        k >>= 1;
    }
    return res;
}

91.最短ハミルトン経路
n個の点の重み付き無方向図を1枚与え、点は0~n-1の符号から、始点0から終点n-1までの最短Hamilton経路を求める.Hamilton経路の定義は,0からn−1まで各点を繰り返して正確に1回通過する.
入力形式:
最初の行は整数nを入力します.
次に、n行毎にn個の整数があり、i行目j個目の整数は、点iからjまでの距離(a[i,j]と記す)を表す.
任意のx,y,zについて、データは、a［x,x］＝0,a［x,y］＝a［y,x］およびa［x,y］＋a［y,z］＞＝a［x,z］を保証する.
出力フォーマット:
最短Hamiltonパスの長さを表す整数を出力します.
データ範囲:
1 ≤ n ≤ 20 0 ≤ a [ i , j ] ≤ 107
サンプルを入力:

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

出力サンプル:

18

コード:

#include 
#include 
#include 

using namespace std;
const int N = 20, M = 1 << 20;
int mg[N][N], f[M][N];

int main() {
     
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> mg[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; ++i)   //         i 
        for (int j = 0; j < n; ++j)    //         j 
            if (i >> j & 1)            //   i  j    1
                for (int k = 0; k < n; ++k)
                    if ((i - (1 << j)) >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + mg[k][j]);
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

異種または配偶者を実現する

e[index]
e[index ^ 1]

lowbit演算

// lowbit(1110010000) = 10000
int lowbit(int n) {
     
  //return (~n + 1) & n;
    return (-n) & n;
}