andyli

有关状压dp的一些技巧
我们知道,在状压dp中,存储状态时一般都要借助位操作。位操作是一种速度非常快的基本运算,包括左移、右移、与、或、异...
扫描右侧二维码阅读全文
24
2019/11

有关状压dp的一些技巧

我们知道,在状压dp中,存储状态时一般都要借助位操作。位操作是一种速度非常快的基本运算,包括左移、右移、与、或、异或、非等运算。

  1. 左移
    左移一位,相当于把某数乘$2$,比如$110_{(2)}$左移$1$位变成$1100_{(2)}\Leftrightarrow \ 6$变为$12$,表示为$110_{(2)}<<1=1100_{(2)}$。因此左移$x$位,相当于该数乘$2^x$。
  2. 右移
    右移一位,相当于某数除以$2$,比如$110_{(2)}$右移$1$位变为$11_{(2)}\Leftrightarrow \ 6$变为$3$,表示为$110_{(2)}<<1=011_{(2)}$。因此左移$x$位,相当于该数除以$2^x$。
  3. 与运算
    按位进行“与”运算,两数同一位都为$1$时结果为$1$,否则为$0$。例如:$101_{(2)}\&110_{(2)}=100_{(2)}$。
  4. 或运算
    按位进行“或”运算,两数同一位都为$0$时结果为$0$,否则为$1$。例如:$101_{(2)}|110_{(2)}=111_{(2)}$。
  5. 异或运算
    按位进行“异或”运算,两数同一位相同时结果为$0$,否则为$1$。可以形象地理解为$2$进制下的不进位加法。例如:$101_{(2)}$ ^ $110_{(2)}=11_{(2)}$。
  6. 非运算
    按位取反。例如$\sim 101_{(2)}=010_{(2)}$。

若当前状态为$S$时,对$S$有下列操作:

  1. 判断第$i$位是否为$0/1$
    $(S>>i)\&1 == 0/1$
  2. 将第$i$位设置为$0$
    $S|=(1<<i)$
  3. 将第$i$位设置为$1$
    $S\& \sim (1<<i)$
  4. 将第$i$位取反
    $S$^=$(1<<i)$

例如,$S=1010101_{(2)}, i=5$。
$(S>>i)\&1$:$(1010101_{(2)}>>5)\&1=0000000_{(2)}$
$S|(1<<i)$: $1010101_{(2)} |0100000_{(2)}=1110101_{(2)}$
$S\& \sim (1<<i)$:$1010101_{(2)}\&1011111_{(2)}=1010101_{(2)}$
$S$^=$(1<<i)$:$1010101_{(2)}$^$0100000_{(2)}=1110101_{(2)}$

Last modification:November 24th, 2019 at 02:21 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment