二进制

位运算的优先级比较奇怪,请加括号使用

C/C++语言提供的位运算符

用$x$表示一个10进制数,记其二进制展开从最右边开始为第$0、1、2…$位

操作

功能 语句 描述
获取$x$的第$i$位 x&(1<<i) 若$x$的第$i$位为$1$,值为$2^i$
bar bar bar
查询$x$中$1$的个数 __builtin_popcount(x) GCC内建函数
提取lowbit(x) x&(-x) 可以遍历$x$中所有$1$

技巧

功能 语句 描述
判断奇偶性 x&1 值为$1$则$x$为奇数
乘除$2$ << & >> 根据实际意义
对$2$的幂取模 __builtin_popcount(x) GCC内建函数
交换两个数 a^=b,b^=a,a^=b 根据实际意义

集合

用二进制数表示集合,设单个二进制数最大位宽为$w$

修改&查询&删除

直接上……

$O(1)$

集合交&并&差&补

x&y
x|y
x^(x&y)
~x

$O(\frac{n}{w})$

性质

位运算每一位相互独立,互不干扰,可以按位考虑,进行dp/贪心

分享到: