焦点滚动:位运算与集合
时间:2023-06-17 10:00:00来源:博客园

前言

在刷 LeetCode 的时候,我们常常碰到需要枚举同时选择几个元素,或者说枚举选择一个集合的情况,即同时选择 $\lbrace0, 1, 2\rbrace$ 或者 $\lbrace0, 1,3\rbrace$ 等,这里集合中的数字表示要选择的元素的索引。

通常情况下,我们往往会使用哈希表来表示集合,好处在于可以方便的在 $O(1)$ 时间内确定元素是否处于集合中,坏处则是当我们需要做集合之间的运算,例如求交集或者并集,那么就需要 $O(n)$ 时间才能实现;另一个缺陷就是,当递归函数的可变实参中存在哈希表(或者对哈希表的引用)时,无法通过添加 $cach$ 数组实现记忆化搜索。


(相关资料图)

于是,我们需要想一个新的办法来表示集合,由于集合可以由全集(包含所有元素的集合)中每个元素的选或者不选来表示,因此,很容易联想到二进制上每一位的 $0$ 和 $1$,例如 $101 = 5$ 表示集合中只有第 $0$ 个元素和第 $2$ 个元素。

使用数学化一点的语言,即集合可以以如下方式压缩成二进制下的一个数字:

$$f(S)=\sum\limits_{i\in S}2^i$$

其中 $i$ 表示集合中的元素在原数组中的索引。$\lbrace a[0], a[1], a[3]\rbrace$ 即可由 $2^0+2^1+2^3 = 13$ 即二进制数 $1101$ 表示。

集合与元素

根据上面提到的二进制表示集合的方法,我们可以在 $O(1)$ 的时间内实现集合与元素之间的运算。

具体运算表格参见灵神的 从集合论到位运算,常见位运算技巧分类总结!。无需记忆,自己做题的时候很容易就能推导出来。

集合与集合

集合与集合之间的运算也可以在用二进制数表示集合的情况下,在 $O(1)$ 时间内完成计算。

具体运算表格同样参见灵神的 从集合论到位运算,常见位运算技巧分类总结!。

同样无需记忆,自己做题的时候很容易就能推导出来。

遍历集合

在集合用二进制数 $mask$ 表示的情况下,集合中的元素个数可以由 C++ 库函数 __builtin_popcount(mask)计算出来。

设元素范围从 $0$ 到 $n - 1$,挨个判断元素是否在集合 $s$ 中:

for (int i = 0; i < n; ++i) {    if ((s >> i) & 1) { // i 在 s 中,注意 == 运算优先级高于 &        //     }}

枚举集合

重头戏来了:设集合为 $s$,从大到小枚举 $s$ 的所有非空子集 $sub$:

for (int mask = s; mask != 0; mask = ((mask - 1) & s)) {    // 处理子集 sub 的逻辑}

暴力的枚举集合的办法是从 $s$ 出发,不断减一直到 $0$,但是这样中途会有很多并不是 $s$ 的子集的情况。

假设集合 $s = 10101$,那么它的子集从大到小依次为:

$$\lbrace 10101, 10100, 10001, 10000, 00101, 00100, 00001\rbrace$$

如果忽略掉 $10101$ 中间的两个 $0$,即忽略第一位和第三位的 $0$(位索引从 $0$ 开始),那么它的子集的数字变化与普通的二进制减法是一样的,即:

$$\lbrace 111, 110, 101, 100, 011, 010, 001\rbrace$$

因此,当我们执行 $(mask - 1)$ & $s$ 时,以 $10100$ 为例,相当于强制跳过了 $10100$ 到 $10001$ 中间那些第一位和第三位数字不为 $0$ 的数。

套用灵神的说法,以 $10100$ 为例,普通的二进制减法会把最低位的 $1$ 变成 $0$,把这个最低位的 $1$ 右边的 $0$ 都变成 $1$,即 $10100\rightarrow 10011$,我们这个压缩版的二进制减法,也是把最低位的 $1$ 变成 $0$,但对这个最低位的 $1$ 右边的 $0$,并不会全都变成 $1$,而是只保留 $s = 10101$ 中存在的 $1$,其他的会依旧是 $0$。

Gosper"s Hack

Gosper"s Hack 算法是生成 $n$ 元集合中所有包含 $k$ 个元素的子集的算法。

这里先给出 Gosper"s Hack 算法的代码

while (x < uplimit) {    int lowbit = x & (-x);    int left = x + lowbit;    int right = ((x ^ (x + lowbit)) / lowbit) >> 2;    x = left | right;}

接下来讲一下 Gopser"s Hack 算法的思想:

对一个二进制数,例如 $110110$,我们需要找到它从左往右的最后一个 $01$,然后把这个 $01$ 变成 $10$,再把它右边的 $1$ 全部集中到最右边(这里右边的 $1$ 显然都是连续的,否则与最后一个 $01$ 矛盾),即 $110110\rightarrow 111001$。

在举了例子之后,Gosper"s Hack 算法的思想其实很好理解。

我们利用 $x + lowbit(x)$ 得到的结果,就是将 $x$ 的第一个 $01$ 变成 $0$,同时右边的数全都变成 $0$,即 $110110\rightarrow 111000$,如果我们使用 $x \oplus (x + lowbit(x))$,即可得到 $x$ 从最后一个 $01$ 起的右边的数,即 $110110\rightarrow 001110$,我们再除以 $lowbit$,即可去掉 $x \oplus (x + lowbit(x))$ 的最右边的连续的 $0$,又因为 $x + lowbit(x)$ 会将这个最后一个的 $01$ 变成 $10$,$01 \oplus 10 = 11$,因此 $(x \oplus(x + low)) / lowbit(x)$ 的 $1$ 的个数比 $x$ 的最后一个 $01$ 的右边的 $1$ 的个数还多了 $2$ 个,于是我们再右移两位,即得到了我们需要 $right$。

参考

从集合论到位运算,常见位运算技巧分类总结!

算法学习笔记(75): Gosper"s Hack

标签:

生活指南
  • 主打“大动力”+实用的工具皮卡,试驾江西五十铃全新瑞迈

    全新瑞迈搭载的2 5T柴油涡轮增压发动机+6速手动变速箱动力组合,以及作

  • 打造开放高地 江西赣州国际陆港“融湾”再加速

    近日,一列装载着赣州本地家具、服装、日用品等货物的班列从赣州国际陆

  • 国少闪电战开场5分钟王钰栋潇洒内切破门!孙康博送精妙直塞

    直播吧6月16日讯U17男足亚洲杯C组第一轮,中国U17男足vs塔吉克斯坦U17

  • 天天看热讯:青岛新增3家国家级博士后科研工作站 为高技术人才与企业搭起桥梁

    近日,全国博士后管委会办公室公布了2022年度第二批次博士后科研工作站

  • 安克创新拟发行可转债募资不超过11亿元

    App6月16日消息,安克创新公告,拟发行可转债募资不超过11亿元,用于便

  • 解码5月车市3大特点

    作者:大众侃车 张娜排版:橘子洲头图片:来源于网络,侵删千城数智(

  • 绿色动力环保(01330)将于7月26日派末期股息每股0.1316港元

    绿色动力环保(01330)发布公告,将于2023年7月26日派发截至2022年12

  • 当前观点:普京:俄罗斯放弃了对石油的依赖

    普京:俄罗斯放弃了对石油的依赖

  • 【独家焦点】终于赢了!国足结束18个月不胜纪录,此前9场4平5负

    直播吧6月16日讯国足4-0大胜缅甸,结束了上一次赢球是2021年10月的12强

  • 曹耀民(关于曹耀民介绍)-新要闻

    来为大家解答以上的问题。曹耀民,耀民介绍这个很多人还不知道,现在让

  • 6月20日起,郑州地铁3号线压缩行车间隔

    为进一步满足市民乘客出行需求,自6月20日起,郑州中建深铁3号线提升运

  • 郑东新区豫兴路办事处举办“乡村振兴 河南专场”企业募捐活动

    中原网讯(记者刘梦琳通讯员张震马亚楠)为助力乡村振兴飞速发展,推进豫

  • 每日讯息!“这是在济南,一定会有人赶来施救的”!记者对话四位“水库救人”的济南英雄

    01:506月15日,媒体报道了多位热心市民在孟家水库接力救援落水母女的感

  • 北上资金今日净买入三一重工8.79亿元、宁德时代7.85亿元

    北上资金今日净买入三一重工(600031)8 79亿元、宁德时代(300750)7 85亿

  • 东湖高新: 根据证监会行业分类,公司属于“土木工程建筑业”企业_世界热闻

    东湖高新60013306月16日在投资者关系平台上答复了投资者关心的问题投资

  • 五部门:完善农村产权确权颁证、抵押登记、流转交易、评估处置机制,推动融资配套要素市场改革-全球简讯

    证券时报网讯,据央行消息,中国人民银行、金融监管总局、中国证监会、

  • 民生
    • 每日资讯:梅赛德斯-奔驰与微软合作,将ChatGPT整合进MBUX语音助手【附中国AI语音产业链】

    • 天天速递!昂达声卡驱动_昂达声卡驱动

    • 【天天播资讯】世体:巴萨正在寻找中场引援,能给莱万喂球&低价可顶替佩德里

    • 四川:扫除未成年人消费"盲区" 消费维权知识进校园 速读