子集枚举/二进制/位运算 技巧小结 （带例题）C++

本文主要是介绍子集枚举/二进制/位运算 技巧小结 （带例题）C++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

假如对一个拥有n个元素的集合，它的子集有2^n个。为了方便理解，不妨取n=3，元素为{1，2，3}来举例说明。下表中，0代表该元素在子集中未出现，1代表出现了。

 观察此表可发现，各元素在子集中的出现与否，0和1可组成的二进制数，都和唯一的十进制数一一对应着。并且对应的十进制数的范围正好是2^n-1至0。即2^n个数，这些数每一位比特位的1和0都对应着元素的是否出现。所以只需要从全集对应的十进制数枚举到0，就相当于枚举了所有子集了。关键就是如何快速表示全集，以及如何得到每一比特位，又如何修改每一比特位。下面对这些方法进行小结。

先说明，下列例子都是此类，如三个元素的集合{1、2、3}，的出现情况，在数组中存储时，是由最高位表示首元素出现情况。如全集1 1 1，在数组中对应的下标为2 1 0。即都是倒着标号，因为这样方便取得每一位的情况，下面会说明。

一、表示全集U=2^n-1/U=(1<<n)-1

全集即所有的元素都出现，如3个元素时，全集即都出现，二进制为111，对应十进制数为7=2^3-1=(1<<3)-1。一般写成后者，通过位运算快速得到全集。

二、得到每一位比特位，即得到每一位元素的出现情况 （s>>i)&1

假设子集为s，要得到的下标为i，即第i+1个的比特位，即（s>>i)&1。拿集合{1，2，3}的子集{1，3}举例。对应的二进制为101，即s的二进制为101。想得到元素2在此子集中的出现情况，即i=1，s先右移i=1，使原来的第2位到了第1位，成了010，而1的二进制是除了首位为1，其他的都为0，这里只取三位说明，即为001，&操作的特点是，&1则不变，&0都变成0。因为&操作要两对应比特位都为1才为1，即1&1=1，0&1=0，0&0=0。所以除了第1位其他位都变成0，&后的结果除了0就是1，并且不会改变此位的情况，从而得到了相应的下标为i的元素的比特位。

也可以通过s&（1<<i)来判断下标为i的元素是否在子集中，但得到的结果往往不会只是0和1，可自行举例验证。

三、统计该子集中的元素个数  ——利用__builtin_popcount()函数

__builtin_popcount()函数是GCC编译器内置的一个函数，用来统计某数中对应的二进制数有多少个1，而我们利用时，正好就是1便代表该位的元素在子集中出现了，因此可用来统计子集中的元素个数。假设子集为s,则__builtin_popcount(s)将返回该子集中的元素个数。

四、修改某比特位的情况——位运算

如对于某子集s，要修改第i+1位，即下标为i的元素的状态。如果要修改为1

则 s|=(1<<i)。与上同理，1初始时只有第1位为1其他位都为0，左移动i位后，第i+1为变为1，其他位都为0，再拿集合{1，2，3}的子集{1，3}举例。对应的二进制为101，即s的二进制为101。想修改元素2在此子集中的出现情况，即i=1，1先左移i=1位，变成010，再和s=101进行|运算，而|运算的规则是俩对应的二进制位只要有1个为1则变为1。即1|1=1，1|0=1，0|0=0。所以101|010=111。所以s变为111，所以我们不难发现，|0运算是是不变的，此运算只将我们想修改的第i+1位修改为1。那么要修改为0呢？

即s&=~(1<<i)。与上同理，再拿上述例子，i=1，s的二进制为101。先对1左移1再取反，则变成除了第i+1位为0其他位都变为1，即成了101。而&运算要求都为1结果才为1，即1&1=1，0&1=0，0&0=0。所以我们不难总结&运算的特点，即&1不变，&0则变为0。所以101&101=101。所以成功修改相应i+1位（对应下标为i）的值为0。

五，连续元素复原

上述例子都是从i=0且逆序存储各元素的，所以在复原的时候需要倒过来，且此类复原只适用于集合中的元素是连续且从1开始的。如集合{1，2，3，4}的子集{1、3、4}，此时s的二进制是1011，对应的下标为3 2 1 0 通过技巧2，如果是1代表存在就记录下标，为3 1 0，复原时是4-3，4-1，4-0，即是全集元素个数-下标对应原元素。

下面给出三个例题，都充分利用了上述技巧，充分体现了此种表现法的威力所在，多尝试利用自然融会贯通。

洛谷P1157 组合的输出 子集枚举 C++_Prudento的博客-CSDN博客https://blog.csdn.net/Prudento/article/details/122722009?spm=1001.2014.3001.5502洛谷P1036 [NOIP2002 普及组] 选数 利用位运算进行子集枚举 C++_Prudento的博客-CSDN博客https://blog.csdn.net/Prudento/article/details/122721349?spm=1001.2014.3001.5502openjudge 熄灯问题 利用二进制和强大的位运算进行子集枚举 C++_Prudento的博客-CSDN博客https://blog.csdn.net/Prudento/article/details/122710619?spm=1001.2014.3001.5502

这篇关于子集枚举/二进制/位运算 技巧小结 （带例题）C++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！