|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sashka Yackubtchick 2:5054/29.54 24 Apr 2002 05:09:12
To : Sergey Kabikov
Subject : задача про xor
--------------------------------------------------------------------------------
18 Apr 02 10:01, Sergey Kabikov писАл(а) к Max Alekseyev:
SK> Следовательно, если в наборе S присутствуют два числа, отличающиеся только
SK> одним битом, обязательно найдется решение, в котором одно из M равно тому
SK> самому биту.
Я описал это решение как:
x = or всех элементов S ;если хоть в одном элементе из S nый бит = 1
;то и в x он будет равен одному
y = and всех элементов S ;если хоть в одном элементе из S nый бит = 0
;то и в y он будет равен нулю
Z = y Xor x ;биты несовпадающие в x и y будут = 1
Z - это весь набор необходимых однобитовых масок.
Hапример если Z = 10010 (двоичная система)
то необходимы две маски 10000 ; 10
если учесть ещё что нужно сделать так чтобы при данном колличестве массок
колличестов действий над базой было минимальным для получения чисел, то
база может быть вычеслена как
b = x and (not Z)
однако если наборы в S не равномерные последовательности есть возможность
более экономных решений где число масок будет меньше колличества битов
которые хотя бы в одной паре из S не совпадают.
Могу привести пример где при восьми несовпадющих битах из 32 чисел в S
понадобится лишь 5 масок вместо 8и.
Пока!
Sashka, The Svin.
--- GoldED/W32 3.00.Beta1+
* Origin: Svin, Perm, Russia (2:5054/29.54)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
