Нахождение набора на основе появления битов

Question

Я пытаюсь найти столбец битов, который появляется более одного раза.Позвольте мне представить вам пример:

       X Y Z   
Set A  0 1 0
Set B  0 0 1
Set C  0 1 0
Set D  0 0 0

С помощью операции UNION я могу узнать, какой столбец COLUMN из списка наборов имеет значение 1. Если я это сделаюA UNION B UNION C UNION D, тогда мы получим 0 1 1 , что означает, что в столбце X нет битов, установленных в 1, а в столбцах Y и Z по крайней мере 1 бит установлен в 1.

Моя проблема в том, что я пытаюсь найти правильную операцию установки, чтобы найти столбцы, биты которых установлены в 1 более одного раза.В приведенном выше примере в столбце Y 2 бита установлены в 1. Таким образом, результат должен быть 0 1 0 .

Я попытался сделать пересечения, что является наиболее логичным, но производитдругой результат.

Я ценю, что кто-то может подсказать мне, какую комбинацию операций набора я должен выполнить, чтобы получить желаемый результат.Заранее спасибо.

Answer 1

Моя проблема в том, что я пытаюсь найти правильную операцию установки, чтобы найти столбцы, биты которых установлены в 1 более одного раза.

Вот один из способов:

(A ∩ B) ∪ (A ∩ C) ∪ (A ∩ D) ∪ (B ∩ C) ∪ (B ∩ D) ∪ (C ∩ D)

Тем не менеематематика довольно гибкая;Вы можете буквально просто сказать «набор, содержащий все элементы, которые появляются по крайней мере в двух наборах A , B , C , D", и математики примут это для большинства целей.

Answer 2

Это немного веселее, когда вы пытаетесь сделать это эффективно.

Назначайте номера последовательно каждому набору, начиная с 0.

Затем, если есть столбец, который находится впо крайней мере, два разных набора, тогда номера этих двух наборов должны быть разными, а если числа разные, то двоичное представление этих чисел будет отличаться по крайней мере в одной позиции бита.

Итак:

1. Для каждой позиции бита b в заданных номерах (имеется их журнал (number_of_sets)):

   1. Создатьобъединение всех наборов, у которых бит b установлен в своих номерах;

   2. Создать объединение всех наборов, которые не имеют бит b установить в свои номера;

   3. Пересечь эти два набора.

2. Создать объединение извсе эти пересечения.

Готово.Результатом является набор всех столбцов, которые отображаются как минимум в двух разных наборах.

Например, если столбец находится в обоих наборах 5 и наборе 7 , тоэто будет в пересечении для позиции бита b = 1 (значение места 2), потому что двоичные представления 5 (101) и 7 (111) отличаются в этой битовой позиции.Столбец будет объединять все наборы с номерами, у которых бит 1 выключен, и в объединении всех наборов, у которых бит 1 включен.

Общее количество требуемых операций набора: N * log (N) , где N - количество наборов.

Answer 3

Пусть USet_0 := 0 0 0 и DSet_0 := 0 0 0.Затем мы определяем

USet_(k+1) := USet_k UNION Set_k | forall 0 <= k < n

и

DSet_(k+1) := DSet_k UNION (USet_k INTERSECT Set_k) | forall 0 <= k < n

. Операция поиска объединения всех ваших n наборов приводит к USet_n.Любые столбцы, для которых установлено несколько битов, затем представляются DSet_n.