集合的位向量实现

Question

在阅读关于数据结构的书中关于集合的基本操作的章节时,我在主题的位向量实现中遇到了以下几行...

if the universal set is sufficiently small so that a bit vector fits in one computer word,
then union, intersection and difference can be performed by single logical operations in
the language of the underlying machine..  

集合的一个位向量实现意味着一个集合由一个数组表示,其下标表示集合的元素,如果它是数组的成员则下标的内容为1,如果不是则为零....所以成员,插入和删除操作可以在一段时间内执行....但任何人都可以告诉我如何通过摘录中所述的单个逻辑操作来执行交集,并集和差异... plz给出一个示例(或代码) )对于三个操作中的任何一个....

Answer 1

让我们假设您有一台32位字的计算机,并且您希望在具有32个元素的域上表示集合.例如{0 ... 31}的子集.

集合用单个整数表示,当且仅当x在集合中时,位#x为1.所以集合{0,1,17,30}将是

01000000000000100000000000000011

按惯例,我们从31到0,从左到右编号.

有了这种表示:

• 交点是二进制AND(x & y)
• 联盟是二元OR(x | y)
• 设置差异是二进制AND NOT(x & ~y)
• 对称集差异是二进制XOR(x ^ y)