位运算有关小技巧

基本运算

以下a指一个二进制位。

NOT

  • ~1 = 0
  • ~0 = 1

如果智商正常应该不会不能理解取反运算吧

AND

  • 1&a = a
  • 0&a=0

由此可见善加利用AND运算,可以保证某个二进制数的特定位为0,其余的位保持原样。

OR

  • 1|a=1
  • 0|a=0

由此可见善加利用OR运算,可以保证某个二进制数特定位为1,其余位维持原样。

XOR

XOR/异或运算具有重要性质:

  • a^a = 0
    XOR可以代替等于
  • 0^a = a
    0是XOR运算的单位元
  • 1^1=0 1^0=1
    用1去做XOR运算可以实现“开关”某个二进制位的效果
  • abs(a^1-a)=1
    用1对一个数去做XOR可以实现求与这个数相邻的数的效果
    比如2^1=3 3^1=2
  • 1^1 = 0;1^1^1 = 1;1^1^1^1 = 0
    XOR与奇偶性紧密相连

SHL/SHR

左移运算相当于除以2,右移运算相当于乘2.

运算技巧

scanf

while(~scanf(” %d”,&n)){}
while(scanf(” %d”,&n) != EOF){}

两种形式等价

判断奇偶性

if a&1 == 1 then a is odd
if a&1 == 0 then a is even

取出最低位

lowbit(x) = x&(-x)

制作全1掩码

mask = (1 << n) – 1

理论最大最小值

INTMAX = ~(1 << 31)
LLMAX = ~(1ll << 63)

INTMIN = 1 << 31
LLMIN = 1ll << 63

常用最大值

memset(dp,0x3f,sizeof(dp))

装逼

swap

a= a ^ b
b = a ^ b
a = a ^ b

绝对值

abs(n) = (n ^ (n >> 31)) – (n >> 31)

最大值

max(a,b) = b & ((a-b) >> 31) | a & (~(a-b) >> 31)

最小值

min(a,b) = a & ((a-b) >> 31) | b & (~(a-b) >> 31)

集合

表示集合

用二进制位表示集合是很简单也是很直观的,直接举个例子:假设全集是{a,b,c,d,e,f,g,h},这样我们一共有8种不同的元素,怎么表示{a,c,e}这个集合呢,很简单,我们拿出8个二进制位,从左到右分别表示“a,b,c,d,e,f,g,h”,那么{a,c,e}就可以用二进制”10101000″ 表示。

操作用二进制表示的集合

加入元素:使用“或等”运算

删除元素:使用“和等”运算

确认元素是否在内:使用“和”运算

并集:使用“或”运算

交集:使用“和”运算

补集:先使用“取反”运算,再使用“和”运算

开关:使用“异或”运算

枚举

枚举全部的集合形态:从0枚举至11111111…

枚举某个集合的自己:-1,然后和求子集的集合做“和等”

图论

获取反向边

i i^1互为反向边,要求插边时必须同时插入正边和反边,边数组编号从2的倍数或0开始。

数据结构

二叉树

令根节点为1

编号x的节点的左儿子编号: (x << 1)
编号x的节点的右儿子编号: (x << 1) + 1
编号x的节点的父亲编号: (x >> 1)
编号x的节点的兄弟编号: (x ^ 1)

二叉树两个节点节点是否相邻

使用堆存储,根节点编号为1,如果a^b=1,则两个点必定同属一个父亲

二叉堆

先坑着,看需求

动态规划

滚动数组

模运算很慢,所以我们用XOR代替mod2。

int tick = 0;
for(){
dp[tick^1] = dp[tick];
tick ^= 1;
}

快速幂

这里暂时不详细提供代码了。

 

Leave a Reply

Scroll to top