Лекция 3 побитовые операции

Множества.

Существуют разные подходы к представлению множества:

1.Хранится каждый элемент, присутствующий в множестве. Это может быть смежное представление (например, массив элементов) или связанное размещение элементов в памяти (в дальнейшем рассмотрим организацию связанных списков).

2.Определяются все потенциально возможные злементы множества А: А={а₀, а_1,.....а_n_-2, а_n_-1}. Всего n элементов. Затем для каждого подмножества X из А определяется для каждого элемента, принадлежит ли он этому подмножеству. Для этого каждому множеству сопоставляется бинарная (т.е. состоящая из 0 и 1) последовательность b₀,b₁,…b_n_-1, определяемая так:

i=0,1,2,...n-1

Наилучший метод представления множеств существенно зависит от операций, которые планируется выполнять над множествами. Это типичные операции: выяснить, имеется ли конкретный элемент в данном множестве, добавить в множество новые элементы, удалить из множества элементы, выполнить обычные теоретико-множественные операции, например объединение или пересечение двух множеств.

Вектор b= {b₀,b₁,…b_n_-1} называется характеристическим вектором из n элементов. Это представление удобнее тем, что основные операции над множествами можно выполнять как побитовые операции над двоичными векторами. Однако для больших n использование таких векторов практически невыполнимо.

Рассмотрим задачу формирования различных подмножеств заданного массивом множества А={а₀, а_1,.....а_n_-2, а_n_-1}. Заводят некоторую строку битов и устанавливают взаимно-однозначное соответствие между битами строки b и числами из А: b_i <=> а [i].

b: а[n-1] а[n-2].... а[2] а[1] а[0]

.......

n-1 n-2 2 1 0

Описать переменную b можно, например, так

unsigned int b; // если n<32

или

unsigned char b [NN]; // если n<NN*8

Рассмотрим такое описание b:

unsigned int b;

Пусть в переменной b записана информация о некотором подмножестве С⋤А:

i=0,1,2,...n-1