小编典典

集的位向量实现

algorithm

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

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给出示例(或代码) )进行三个操作中的任何一个。


阅读 319

收藏
2020-07-28

共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
2020-07-28