集合的位向量实现
在阅读 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，如果不是数组的成员，则为 0...所以成员、插入和删除操作可以在恒定的时间内执行... .但是谁能告诉我如何执行交集、并集和差集摘录中所述的单个逻辑操作...请为这三个操作中的任何一个给出一个示例（或代码）...
while reading the chapter on basic operations on sets from the book of data structures by aho i came across the following line in the topic bit vector implementation of sets...
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..
a bit vector implementation of sets implies that a set is denoted by an array whose subscripts denote the elements of the set and the content of a subscript is one if it is the member of an array and zero if not....so member, insert and delete operations can be performed in a constant amount of time....but can anyone show me how intersection, union and difference can be performed by single logic operations as stated by the excerpt...plz give an example(or code) for any one of the three operations....
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
假设您有一台具有 32 位字的计算机，并且您想要在具有 32 个元素的域上表示集合。例如 {0...31} 的子集。
集合用单个整数表示，其中当且仅当 x 在集合中时，位# x 才为 1。因此，按照惯例，集合 {0, 1, 17, 30} 将是
从 31 到 0，从左到右对位进行编号。
使用以下表示形式：
x & y)x | y)x & ~y)x ^ y)Lets suppose you have a computer with a 32-bit word and you want to represent sets over a domain with 32 elements. For example subsets of {0...31}.
Sets are represented with a single integer in which bit# x is 1 if and only if x is in the set. So the set {0, 1, 17, 30} would be
We number bits from 31 to 0, left to right, by convention.
With this representation:
x & y)x | y)x & ~y)x ^ y)给定集合
s1和s2，s1 和s2。 s2s1 | s2 的Given sets
s1ands2,s1 & s2s1 | s2s1 & ~s2