位矢量实现集 [英] bit vector implementation of sets

问题描述

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

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..  

集合的位向量实现意味着一组被表示通过一个数组，其下标表示集合的元素，下标的内容是一个，如果它是数组的成员，则为零，如果不是，则为零。因此，成员，插入和删除操作可以以恒定的时间....但任何人都可以告诉我交点，联合和差异可以通过单片逻辑操作执行，如摘录所述... plz给出了三个操作中的任何一个的示例（或代码）....

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....

推荐答案

假设你有一个32位字的计算机，并且想要在一个32个元素的域上表示集合。例如{0 ... 31}的子集。

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}.

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

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

01000000000000100000000000000011

按照惯例，我们从31到0，从左到右编号。

We number bits from 31 to 0, left to right, by convention.

代表：

• 交点是二进制AND（ x& y ）
• 
  
• 联盟是一个二进制OR（ x | y ）


• 设置差异是一个二进制AND NOT （ x&〜y ）


• 对称集的差异是二进制XOR（ x ^ y ）



• Intersection is a binary AND (x & y)
• Union is a binary OR (x | y)
• Set difference is a binary AND NOT (x & ~y)
• Symmetric set difference is a binary XOR (x ^ y)

这篇关于位矢量实现集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！