位运算

发布于 2019-10-22  328 次阅读


这篇是为接下来的状压DP合集做准备

运算

位运算有四种基本运算,分别是与& ,或| ,非~,异或xor / ^

注意非并不是!而是~,是因为!是逻辑运算符非,而不是位运算符。

运算法则的可以像条件语句的判断

&

按位与的运算法则如下

$0 \& 0 =0, 1 \&0 =0, 0 \&1 = 0, 1 \&1 = 1$

逻辑运算符中&&两边同时成立(值为1)即为成立,同理,按位与法则也是全 11, 有 00

|

按位与的运算法则如下

$0 | 0 =0, 1 | 0 =1, 0 |1 = 1, 1 | 1 = 1$

逻辑运算符中||两边有一边成立(值为1)即为成立 ,同理,或运算法则也是有 11, 全 00

~

最简单的运算

01 , 有 10

异或 xor / ^

特殊一点点(Latex公式中的异或用\bigoplus表示,在C++中用^表示)

$0 \bigoplus 0 = 0, 0 \bigoplus 1 =1, 1 \bigoplus 0 = 1, 1 \bigoplus 1 = 0$

总结就是相同为0, 不同为1

取出第 k

取出 n 在二进制下的第 k

(n >> k) & 1

首先将 n 右移 k 位,现在我们要取出的原数的第 k 位已经移到了第一位,对于 1 进行按位与,原位是 1 则取出的是1,原位是 0 则取出的仍是 0

取出第0k-1

取出 n 的后 k

n & ((1<<k) - 1)

1 右移 k 位(相当于在 1 后面插入 k0 )后减 1 (到这里相当于k1),之后与 n 进行按位与操作

跟上面的理解差不多,读者自证不难。

将第 k 位取反

n ^ (1 << k)

1 后插入 k0 后跟 n 进行异或操作。

这里没有减1的原因是,第 k 位是 1 与原来 n 的第 k 位按异或的运算规则比较之后后取反值。

将第 k 位赋成 1

n | (1 << k)

1 后插入 k0 后跟 n 进行或操作。

如果原数的第 k 位是 1,那么与1 或起来还是1,原位是 0 则变为 1

将第k位赋为0

n | (~ (1 << k))

是上面的操作的反操作


朴实沉毅