位运算快速枚举用二进制表示的集合的所有子集(来自训练指南

大概就是做训练指南遇到了一个压缩dp题然后需要用到把二进制表示的这种集合的所有子集很快的枚举出来(⊙﹏⊙)

当然据聚聚说这只是常规操作所以可能是我太蠢了之前没有遇到过emm

正题:有的题目需要我们把一个集合的所有子集都枚举出来,一般来说是有点小难,但是因为我们用的二进制表示的集合,那么也就有用二进制的操作简化运算的方法啦

首先可以确定一点就是A表示的二进制集合的子集变成十进制之后一定比A小,因为子集只是把其中的一些1换成了0,所以不管怎么样都不可能比A大。所以如果我们想暴力的话就可以直接每次都-1,然后检查是不是A的子集。

但是这样的方法显然太慢太暴力,有什么快速的方法?很简单,想办法把多余的状态剔除掉。操作就是每次-1 后跟A相与一下!这个&其实就是把原来A中有的1一定保存了下来,然后我们已经知道每次都-1肯定是对的了。。复杂度就成了A的子集数了。

for (int i=x;i;i=(i-1)&x)
    {
        //对i进行的其他操作  
    }

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据