AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 商店
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

(一)基础算法.位运算技巧

作者: 作者的头像   nut96 ,  2022-01-15 16:36:10 ,  所有人可见 ,  阅读 99


2


(一)在状压dp中,对于二进制状态,我们可以通过多种方式提取,改变,以下是操作规则
1.取出整数n在二进制下表示下的第k位 :(n >> k) & 1
2.取出整数n在二进制表示下的第0~k - 1位(后k位):n & ((1 << k) - 1)
3.把整数n在二进制表示下的第k位取反 :n xor (1 << k)
4.把整数n在二进制表示下的第k位赋值1 :n | (1 << k)
5.把整数n在二进制表示下的第k位赋值0 :n & (~(1 << k))
也可以用bitset实现.
(二)lowbit的实现:
n & (~n + 1):推导:~后面的的0都变成1,最后一个1变成0,+1变成1000…
获取每一位1:n = n - lowbit(n)
(三)成对变换
通过计算可以发现,对于非负整数n:
n为偶数时,n xor 1等于n + 1,
n为奇数时,n xor 1等于n - 1,
0与1,1与2,2与3,..n与n + 1构成”成对变换”.
(四)如果进行位运算的时候不进位,那么每一位就是相互独立的,就可以分成每一位分别解决

2 评论


用户头像
燚淼叕鑫鱻   7个月前     回复

给个关注呗,本人无条件互粉

用户头像
nut96   6个月前     回复

好的哦


你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息